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

Bài này sẽ giới thiệu về cấu trúc dữ liệu danh sách liên kết (Linked List). Đây là một trong những cấu trúc dữ liệu kinh điển thường được nhắc đến. Linked List có nhiều loại khác nhau. Hãy cùng nhau tìm hiểu các đặc điểm của từng loại Linked List nào nhé!

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

Một danh sách liên kết (Linked List) là một cấu trúc dữ liệu tuyến tính, bao gồm một chuỗi các node kết nối với nhau. Mỗi node có thể xem như một phần tử trong danh sách. Mỗi node sẽ lưu trữ dữ liệu (data) của node đó và địa chỉ (address) của node kế tiếp. Bên dưới là minh họa cấu trúc dữ liệu danh sách liên kết.

Danh sách liên kết phải có node bắt đầu, được gọi là HEAD. Node cuối cùng được gọi là TAIL. Mỗi node có nhiều nhất 1 phần tử đứng trước cũng như có nhiều nhất 1 phần tử đứng sau.

Có nhiều trường hợp trong thực tế có thể được lưu trữ bằng cách sử dụng Linked List như:

• • Danh sách học sinh
  • Danh mục sách trong thư viện
  • Danh bạ điện thoại
  • Danh sách các nhân viên trong công ty
  • …

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

Có nhiều loại danh sách liên kết như danh sách liên kết đơn (singly linked list), danh sách liên kết kép (doubly linked list), danh sách liên kết vòng (circular linked list).

Danh sách liên kết đơn (singly linked list)

Mỗi phần tử chỉ liên kết với phần tử đứng sau nó trong danh sách.

Danh sách liên kết kép (doubly linked list)

Mỗi phần tử liên kết với phần tử đứng trước và đứng sau nó trong danh sách.

Danh sách liên kết vòng (circular linked list)

Đặc điểm của Circular Linked List là phần tử cuối danh sách liên kết với phần tử đầu danh sách. Có 2 loại danh sách liên kết vòng là:

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

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

Ở những bài sau, chúng ta sẽ tìm hiểu về cách xây dựng các loại danh sách liên kết cũng như những thao tác cơ bản trên chúng.