Chi tiết bài học danh sách liên kết đơn

Danh sách liên kết đơn(Single linked list) là ví dụ tốt nhất và cơ bản nhất về cấu trúc dữ liệu động dùng con trỏ để thiết lập. Vì thế, kiến thức con trỏ là cực kì quan trọng để biết cách danh sách liên kết công việc, vì lẽ đó nếu như bạn chưa có chuyên môn về con trỏ thì bạn nên học về con trỏ trước. Bạn cũng cần hiểu một tí về cấp phát bộ nhớ động. Để đơn giản và dễ hiểu, phần thông tin cài đặt danh sách liên kết của bài viết này sẽ chỉ giải thích về danh sách liên kết đơn.

Mục lục

Lý thuyết về danh sách liên kết

Về bản chất, danh sách liên kết có công dụng như một mảng, có thể thêm và xóa các phần tử ở bất kỳ vị trí nào khi không thể thiếu. Một vài sự khác nhau giữa danh sách liên kết và mảng:

Nội dung	Mảng	Danh sách liên kết
Kích thước	Kích thước cố định Cần chỉ rõ kích thước trong khi khai báo	Kích thước thay đổi trong lúc thêm/ xóa phần tử Kích thước tối ưu dựa vào bộ nhớ
Cấp phát bộ nhớ	Tĩnh: Bộ nhớ được cấp phát trong quá trình biên dịch	Động: Bộ nhớ được cấp phát trong lúc chạy
Thứ tự & sắp đặt	Được lưu trữ trên một dãy ô nhớ liên tục	Được lưu trữ trên các ô nhớ ngẫu nhiên
Truy xuất	Truy cập tới phần tử ngẫu nhiên trực tiếp bằng việc dùng thông số mảng: O(1)	Truy xuất tới phần tử ngẫu nhiên luôn phải duyệt từ đầu/cuối đến phần tử đó: O(n)
Tìm kiếm	Tìm kiếm tuyến tính hoặc tìm kiếm nhị phân	Chỉ có thể tìm kiếm tuyến tính

Lưu ý: Ở bảng phía trên, các phần in nghiêng biểu hiện đấy là ưu điểm so với đối thủ còn lại.

>>>Xem thêm: Mã nguồn mở là gì? Tổng hợp các mã nguồn mở tốt nhất hiện nay

Danh sách liên kết là gì?

Danh sách liên kết đơn là một tập hợp các Node được phân bố động, được sắp xếp theo bí quyết sao cho mỗi Node chứa “một giá trị”(Data) và “một con trỏ”(Next). Con trỏ sẽ trỏ đến phần tử tiếp theo của danh sách liên kết đấy. Nếu con trỏ mà trỏ tới NULL, có nghĩa là đó là phần tử cuối cùng của linked list.

Danh sách các kiểu danh sách liên kết:

Danh sách liên kết đơn(Single linked list): Chỉ có mối quan hệ từ phần tử phía trước tới phần tử phía sau.
Danh sách liên kết đôi(Double linked list): Có sự kết nối 2 chiều giữa phần tử phía trước với phần tử phía sau
Danh sách liên kết vòng(Circular Linked List): Kết hợp thêm sự kết nối giữa 2 phần tử trước tiên và phần tử cuối cùng để hình thành vòng khép kín.

Các vấn đề mạnh và điểm yếu của danh sách liên kết so sánh với mảng:

Cả danh sách liên kết và mảng đều có thể được sử dụng để chứa các dữ liệu cùng kiểu. Nhưng chúng lại có nhiều đặc điểm riêng, và điểm tốt nhất của thứ này lại là nhược điểm của cái còn lại.

Điểm mạnh:

Danh sách liên kết có kích thước động, có thể mở rộng hay thu hẹp cực kì dễ ràng.
Việc chèn hay xóa một phần tử trong danh sách liên kết là rất giản đơn, ta chỉ cần điều chỉnh vị trí trỏ của các con trỏ thay vì phải dịch tất cả phần dữ liệu còn lại. Coi ví dụ sau khi ta mong muốn chèn node C vào giữa node A và B:

Điểm yếu:

Danh sách liên kết mang yếu điểm của cấp phát động về hiệu suất. Điều này cũng dễ hiểu vì mảng có vị trí bộ đệm vượt trội hơn (là các khối các ô nhớ liên tiếp) so sánh với danh sách liên kết.
Ta không thể truy cập ngẫu nhiên một phần tử trong danh sách liên kết ngay tức thì, mà phải hành động duyệt từ đầu danh sách cho tới khi gặp phần tử đấy. Do vậy ta không thể hành động tìm kiếm nhị phân với các danh sách liên kết.
Cần thêm không gian bộ nhớ cho con trỏ trong mỗi phần tử của danh sách liên kết.

Xây dựng danh sách liên kết đơn với C/C++

Để tạo ra một danh sách sách liên kết trước hết ta cần hiểu được danh sách liên kết cần gồm có những thành phần nào và các thực hành các bước mà ta có khả năng thực hiện với danh sách liên kết:

Các thành phần của danh sách liên kết đơn bao gồm:

Các node: Mỗi node bao gồm hai thành phần: phần dữ liệu và phần liên kết là một con trỏ để trỏ tới vị trí của node kế tiếp, Theo một cách khác, con trỏ này có giá trị là địa chỉ của node tiếp theo. Node cuối cùng của danh sách liên kết sẽ trỏ tới NULL, tức là không trỏ tới đâu cả.
Con trỏ head để trỏ tới vị trí đầu tiên của danh sách liên kết.

>>>Xem thêm: Mã UTM code là gì? Cách đo lường hiệu quả chiến dịch quảng cáo

Ứng dụng của danh sách liên kết đơn trong thực tế:

Danh sách liên kết đơn chủ yếu được dùng để xây dựng các loại cấu trúc dữ liệu khác như ngăn xếp hoặc hàng đợi hoặc đồ thị …

Đôi lúc ta cần biết node ở vị trí trước. Nhưng với danh sách liên kết đơn thì không làm được. Để biết được vị trí của cả các node trước và sau node hiện tại, ta phải lưu cả vị trí của node trước và node sau. Lúc này cấu trúc của một node sẽ có dạng như sau.

Bài viết trên, mình đã chia sẻ tới các bạn chi tiết bài học danh sách liên kết đơn. Cảm ơn các bạn đã theo dõi bài viết nhé!