14/08/2018, 12:28

Cấu trúc dữ liệu danh sách liên kết (Linked List)

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 dãy các cấu trúc dữ liệu được kết nối với nhau thông qua các liên kết (link). Hiểu một cách đơn giản thì Danh sách liên kết là một cấu trúc dữ liệu bao gồm một nhóm các nút (node) tạo thành một chuỗi. Mỗi ...

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

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

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 như là một chuỗi các nút (node). Mỗi nút sẽ trỏ tới nút kế tiếp.

Cấu trúc dữ liệu Danh sách liên kết (Linked List)

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

Các loại Danh sách liên kết (Linked List)

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

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

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

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ỉ là một hoạt động thêm đơn giản như trong các cấu trúc dữ liệu khác (bởi vì chúng ta có dữ liệu và có link). Chúng ta sẽ tìm hiểu thông qua sơ đồ dưới đây. Đầu tiên, tạo một nút bởi sử dụng cùng cấu trúc và tìm vị trí để chèn nút này.

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

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

NewNode.next −> RightNode;

Hình minh họa như sau:

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

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

LeftNode.next −> NewNode;
Hoạt động chèn trong Danh sách liên kết

Quá trình trên sẽ đặt nút mới vào giữa hai nút. Khi đó danh sách mới sẽ trông như sau:

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

Các bước tương tự sẽ được thực hiện nếu chèn nút vào đầu danh sách liên kết. Trong khi đặt một nút vào vị trí cuối của danh sách, thìnút thứ hai tính từ nút cuối cùng của danh sách sẽ trỏ tới nút mới và nút mới sẽ trỏ tới 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 Danh sách liêt kết trong C.

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 phức tạp hơn trong cấu trúc dữ liệu khác. Đầu tiên chúng ta cần định vị nút cần xóa bởi sử dụng các giải thuật tìm kiếm.

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

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

LeftNode.next −> TargetNode.next;
Hoạt động xóa trong Danh sách liên kết

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

TargetNode.next −> NULL;
Hoạt động xóa trong Danh sách liên kết

Nếu bạn cần sử dụng nút đã bị xóa này thì bạn có thể giữ chúng trong bộ nhớ, nếu không bạn có thể xóa hoàn toàn hẳn nó khỏi bộ nhớ.

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

Để 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 Danh sách liêt kết trong C.

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 cẩn thận. Chúng ta cần làm cho nút đầu (head) trỏ tới nút cuối cùng và đảo ngược toàn bộ danh sách liên kết.

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

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

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

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

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

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

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

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

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

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

Để 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 Danh sách liêt kết trong C.

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.

Bài học Cấu trúc dữ liệu và giải thuật phổ biến tại code24h.com:

0