Danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết

Trong bài viết này, codehow sẽ giới thiệu các bạn danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết trong C / C++. Đây là một khái niệm khá lạ đối với các bạn vừa mới học lập trình, tuy nhiên đừng lo lắng, hãy cùng mình tìm hiểu qua bài viết này.

Chúng ta sẽ cùng nhau tìm hiểu về khái niệm danh sách liên kết (Linked List) là gì? Có bao nhiêu loại danh sách liên kết. Sự khác nhau giữa danh sách liên kết và mảng trong C / C++.

Danh sách liên kết (Linked List) là gì?

Hay nói cách khác thì danh sách liên kết là một cấu trúc dữ liệu bao gồm các node. Các node này chứa dữ liệu data và con trỏ trỏ đến node tiếp theo.

Một số tính chất của danh sách liên kết:

• Dùng để lưu trữ các phần tử rời rạc có thể co giãn một cách linh hoạt.
• Không giới hạn số lượng phần tử.
• Không cần định nghĩa trước kích thước của danh sách, khi các phần tử thay đổi thì kích thước tự động thay đổi.
• Dễ dàng thực hiện các thao tác như thêm, sửa, xóa.
• Truy xuất dữ liệu kiểu tuần tự.

Mỗi phần tử con của danh sách được gọi là một node. Mỗi node đều có hai phần đó là dữ liệu của phần tử (data) và con trỏ trỏ đến vị trí tiếp theo (pNext).

Có hai cách quản lý danh sách liên kết (Linked List). Cách thứ nhất là quản lý danh sách liên kết dựa vào node đầu (pHead) hoặc node đầu và cuối (pHead & pTail).

Các loại danh sách liên kết

Trong danh sách liên kết, có 3 loại danh sách liên kết dưới đây mà chúng ta hay sử dụng:

• Danh sách liên kết đơn.
• Danh sách liên kết đôi.
• Danh sách liên kết vòng.

Thông thường chúng ta sử dụng danh sách liên kết đơn và danh sách liên kết đôi nhiều hơn. Bởi đây là hai loại danh sách liên kết phổ biến và dễ sử dụng, dễ quản lý. Danh sách liên kết vòng thì ít được sử dụng hơn.

Danh sách liên kết đơn

Danh sách liên kết đơn là một danh sách liên kết, mỗi phần tử trong danh sách liên kết đơn được liên kết với phần tử ngay sau đó trong danh sách. Nói cách khác thì danh sách liên kết đơn bao gồm các node, mỗi node này được liên kết với node kế tiếp ngay sau nó.

Như các bạn đã thấy trên hình, các node được nối với nhau thông qua pNext. Node thứ nhất được nối với node thứ hai và node thứ hai được nối với node thứ ba. Cứ như vậy cho đến hết danh sách liên kết.

Danh sách liên kết đôi

Danh sách liên kết đôi là danh sách bao gồm các node, mà mỗi node này được liên kết với phần tử trước và sau nó.

Ví dụ như hình trên, mỗi node đều được liên kết với các node trước và sau nó. Tuy nhiên, node đầu và node cuối sẽ nối với NULL, còn phần bên kia sẽ được nối với node trước và sau nó.

Danh sách liên kết vòng

Về cơ bản thì danh sách liên kết vòng cũng như danh sách liên kết đôi. Các node đều được liên kết với các node phía trước và phía sau nó. Tuy nhiên, node đầu tiên (pHead) phải được nối với node cuối (pTail) để tạo thành một vòng tròn.

Sự khác nhau giữa danh sách liên kết và mảng

Qua hai phần trên chúng ta cũng đã hiểu sơ qua về danh sách liên kết là gì? Công dụng của danh sách liên kết và các loại danh sách liên kết. Vậy nó có khác gì so với mảng, bởi vì cả hai đều được sử dụng để lưu trữ dữ liệu.

Vậy trong trường hợp nào chúng ta nên sử dụng danh sách liên kết và trường hợp nào chúng ta nên sử dụng mảng. Hãy xem bảng so sánh dưới đây để hiểu rõ hơn.

Vậy khi nào chúng ta nên sử dụng danh sách liên kết thay cho mảng? Đó là khi chúng ta muốn lưu trữ một tập dữ liệu lớn, chưa biết trước kích thước và giới hạn của dữ liệu. Cần thao tác thêm, sửa, xóa nhiều với danh sách.

Kết luận

Như vậy chúng ta đã tìm hiểu xong về danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết trong C / C++. Qua bài viết này, các bạn cần nắm rõ các kiến thức sau đây:

• Khái niệm danh sách liên kết.
• Các loại danh sách liên kết.
• Sự khác nhau giữa mảng và danh sách liên kết.
• Khi nào nên dùng danh sách liên kết

Ở bài viết tiếp theo, mình sẽ đưa ra cấu trúc của danh sách liên kết. Cách quản lý và cài đặt danh sách liên kết trong C / C++. Các bạn chú ý theo dõi nhé, cảm ơn các bạn rất nhiều !!!