Trang chủ > Khác > Cấu trúc dữ liệu và giải thuật > Danh sách liên kết - Linked List (Cấu trúc dữ liệu và giải thuật)

Danh sách liên kết - Linked List (Cấu trúc dữ liệu và giải thuật)

Một Danh sách liên kết (Linked List) - là một dãy các cấu trúc dữ liệu được kết nối với nhau bàng các liên kết (link). Hiểu theo cách đơn giản thì Danh sách liên kết là một cấu trúc dữ liệu gồm một nhóm những nút (node) tạo nên một chuỗi. Mỗi nút bao gồm dữ liệu ở nút đó và tham chiếu tới nút kế tiếp trong chuỗi.

Danh sách liên kết là cấu trúc dữ liệu được dùng khá phổ biến đứng thứ hai sau mảng. Dưới đây là những khái niệm cơ bản liên quan đến Danh sách liên kết:

  • Link (liên kết): mỗi một link của một Danh sách liên kết có thể lưu giữ một dữ liệu còn được gọi là một phần tử.

  • Next: Mỗi một liên kết của một Danh sách liên kết có chứa một link tới next link còn được gọi là Next.

  • First: một Danh sách liên kết bao gồm các link kết nối đến first link còn được gọi là First.

Biểu diễn Danh sách liên kết (Linked List)

Danh sách liên kết có thể được biểu diễn giống như là một chuỗi những nút (node). Mỗi nút sẽ trỏ đến nút kế tiếp.

Sau đây là một số điểm cần ghi nhớ về Danh sách liên kết:

  • Danh sách liên kết có chứa một phần tử link thì còn được gọi là First.
  • Mỗi một link mang một trường dữ liệu và một trường link còn được gọi là Next.
  • Mỗi một link được liên kết với link kế tiếp bởi dùng link kế tiếp của nó.
  • Link cuối cùng có một link là null để đánh dấu điểm cuối cùng của danh sách.
Các loại Danh sách liên kết (Linked List)

Sau đây là các loại Danh sách liên kết (Linked List) đa dạng:

  • Danh sách liên kết đơn (Simple Linked List): chỉ duyệt những phần tử theo chiều trở về trước.

  • Danh sách liên kết đôi (Doubly Linked List): những phần tử có thể được duyệt theo chiều về sau hoặc về trước.

  • Danh sách liên kết vòng (Circular Linked List): phần tử cuối cùng có chứa link của phần tử đầu tiên giống như là next và phần tử đầu tiên có link đến phần tử cuối cùng giống như là prev.

Các hoạt động cơ bản trên Danh sách liên kết

Sau đây là các hoạt động cơ bản có thể được thực hiện thông qua một danh sách liên kết:

  • Hoạt động chèn: thêm 1 phần tử vào đầu của danh sách liên kết.

  • Hoạt động xóa (phần tử đầu): xóa 1 phần tử vào vị trí đầu danh sách liên kết.

  • Hiển thị: hiển thị tất cả danh sách.

  • Hoạt động tìm kiếm: tìm kiếm phần tử thông qua việc sử dụng khóa (key) đã cung cấp.

  • Hoạt động xóa (bởi sử dụng khóa): xóa 1 phần tử thông qua việc dùng khóa (key) đã cung cấp.

Hoạt động chèn trong Danh sách liên kết

Việc thêm một nút mới vào trong danh sách liên kết không chỉ đơn thuần là hoạt động thêm như trong các cấu trúc dữ liệu khác (bởi vì chúng ta có link và có dữ liệu). Chúng ta sẽ tìm hiểu bằng sơ đồ sau đây. Đầu tiên, tạo một nút thông qua cùng cấu trúc và tìm vị trí phù hợp để chèn nút này.

Giả sử trường hợp chúng ta cần chèn một nút B vào giữa nút C (nút phải) và A (nút trái). Do đó: B. next trỏ đến C.

NewNode. next − > RightNode;

Hình minh họa như dưới đây:

Bây giờ, next của nút bên trái sẽ trở đến nút mới.

LeftNode. next − > NewNode;

Quá trình trên sẽ đặt nút mới vào vị trí giữa 2 nút. Khi đó danh sách mới sẽ trông như hình dưới đây:

Các bước tương tự sẽ được thực hiện nếu ta thực hiện thao tác chèn nút vào đầu danh sách liên kết. Trong khi thực hiện thao tác đặt một nút vào vị trí cuối của danh sách, thì nút thứ 2 tính từ nút cuối cùng của danh sách sẽ trỏ về nút mới và nút mới sẽ trỏ về NULL.

Để tìm hiểu cách để triển khai giải thuật trong ngôn ngữ C, mời bạn click chuột.

Hoạt động xóa trong Danh sách liên kết

Hoạt động xóa trong Danh sách liên kết cũng khá phức tạp so với cấu trúc dữ liệu khác. Đầu tiên chúng ta cần phải định vị nút cần xóa thông qua việc sử dụng các giải thuật tìm kiếm.

Bây giờ, nút bên trái (prev) của nút cần xóa nên trỏ đến nút kế tiếp (next) của nút cần phải xóa.

LeftNode. next − > TargetNode. next;

Quá trình này sẽ giúp xóa hết link trỏ tới nút cần xóa. Bây giờ chúng ta sẽ thực hiện xóa những gì mà nút cần xóa đang trỏ tới.

TargetNode. next − > NULL;

Nếu bạn cần dùng nút đã bị xóa này thì bạn có thể lữu giữ chúng trong bộ nhớ, nếu không bạn có thể xóa nó vĩnh viễn khỏi bộ nhớ.

Để tìm hiểu cách để triển khai giải thuật trong ngôn ngữ C, mời bạn click chuột.

Hoạt động đảo ngược Danh sách liên kết

Với hoạt động này, bạn cần phải hết sức cẩn thận. Chúng ta cần phải làm cho nút đầu (head) trỏ đến nút cuối cùng và đảo ngược tất cả danh sách liên kết.

Đầu tiên, chúng ta cần duyệt tới phần cuối của danh sách đó. Nút này sẽ trỏ đến NULL. Bây giờ chúng ta điều cần làm là làm cho nút cuối này trỏ đến nút phía trước của nó.

Chúng ta phải chắc chắn rằng nút cuối cùng này sẽ không bị thất lạc, do đó chúng ta sẽ dùng các nút tạm (temp node – giống như những biến tạm trung gian để lưu giữ các giá trị). Tiếp theo, chúng ta sẽ làm cho từng nút ở bên trái sẽ trỏ đến nút trái của chúng.

Sau đó, nút đầu tiên sau nút head sẽ trỏ đến NULL.

Chúng ta sẽ làm cho nút head trỏ đến nút đầu tiên mới bởi dùng các nút tạm.

Bây giờ Danh sách liên kết đã bị đảo ngược.