Cấu trúc dữ liệu và thuật toán - Danh sách được liên kết

Danh sách liên kết là một chuỗi 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.

Danh sách liên kết là một chuỗi các liên kết chứa các mục. Mỗi liên kết chứa một kết nối đến một liên kết khác. Danh sách liên kết là cấu trúc dữ liệu được sử dụng nhiều thứ hai sau mảng. Sau đây là các thuật ngữ quan trọng để hiểu khái niệm về Danh sách liên kết.

Link - Mỗi liên kết của danh sách liên kết có thể lưu trữ một dữ liệu gọi là phần tử.
Next - Mỗi liên kết của một danh sách liên kết chứa một liên kết đến liên kết tiếp theo được gọi là Next.
LinkedList - Một Danh sách được Liên kết chứa liên kết kết nối đến liên kết đầu tiên được gọi là Đầu tiên.

Trình bày danh sách được liên kết

Danh sách được liên kết có thể được hình dung như một chuỗi các nút, nơi mọi nút đều trỏ đến nút tiếp theo.

Theo minh họa ở trên, sau đây là những điểm quan trọng cần được xem xét.

Danh sách được Liên kết chứa một phần tử liên kết được gọi là đầu tiên.
Mỗi liên kết mang (các) trường dữ liệu và một trường liên kết được gọi là tiếp theo.
Mỗi liên kết được liên kết với liên kết tiếp theo của nó bằng cách sử dụng liên kết tiếp theo của nó.
Liên kết cuối cùng mang một liên kết là null để đánh dấu phần cuối của danh sách.

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

Sau đây là các loại danh sách liên kết.

Simple Linked List - Điều hướng mục chỉ được chuyển tiếp.
Doubly Linked List - Các mục có thể được điều hướng về phía trước và phía sau.
Circular Linked List - Mục cuối cùng chứa liên kết của phần tử đầu tiên là tiếp theo và phần tử đầu tiên có liên kết đến phần tử cuối cùng như trước.

Hoạt động cơ bản

Sau đây là các hoạt động cơ bản được hỗ trợ bởi một danh sách.

Insertion - Thêm một phần tử vào đầu danh sách.
Deletion - Xóa một phần tử ở đầu danh sách.
Display - Hiển thị danh sách đầy đủ.
Search - Tìm kiếm một phần tử bằng cách sử dụng khóa đã cho.
Delete - Xóa một phần tử bằng cách sử dụng khóa đã cho.

Thao tác chèn

Thêm một nút mới trong danh sách liên kết là một hoạt động nhiều hơn một bước. Chúng ta sẽ tìm hiểu điều này với các sơ đồ ở đây. Đầu tiên, tạo một nút bằng cách sử dụng cùng một cấu trúc và tìm vị trí mà nó phải được chèn vào.

Hãy tưởng tượng rằng chúng ta đang chèn một nút B (NewNode), giữa A (LeftNode) và C(RightNode). Sau đó trỏ B.next vào C -

NewNode.next −> RightNode;

Nó sẽ trông như thế này -

Bây giờ, nút tiếp theo ở bên trái sẽ trỏ đến nút mới.

LeftNode.next −> NewNode;

Điều này sẽ đặt nút mới ở giữa hai nút. Danh sách mới sẽ trông như thế này -

Các bước tương tự nên được thực hiện nếu nút đang được chèn vào đầu danh sách. Trong khi chèn nó vào cuối, nút cuối cùng thứ hai của danh sách sẽ trỏ đến nút mới và nút mới sẽ trỏ đến NULL.

Thao tác xóa

Xóa cũng là một quá trình nhiều hơn một bước. Chúng ta sẽ học bằng cách biểu diễn bằng hình ảnh. Đầu tiên, xác định vị trí nút đích sẽ bị xóa bằng cách sử dụng các thuật toán tìm kiếm.

Nút bên trái (trước đó) của nút đích bây giờ sẽ trỏ đến nút tiếp theo của nút đích -

LeftNode.next −> TargetNode.next;

Thao tác này sẽ xóa liên kết đã trỏ đến nút đích. Bây giờ, bằng cách sử dụng đoạn mã sau, chúng ta sẽ xóa những gì mà nút đích đang trỏ đến.

TargetNode.next −> NULL;

Chúng ta cần sử dụng nút đã xóa. Chúng ta có thể giữ nó trong bộ nhớ nếu không chúng ta có thể đơn giản phân bổ bộ nhớ và xóa hoàn toàn nút đích.

Hoạt động ngược lại

Hoạt động này là một trong những triệt để. Chúng ta cần làm cho nút cuối cùng được trỏ đến bởi nút đầu và đảo ngược toàn bộ danh sách được liên kết.

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

Chúng ta phải đảm bảo rằng nút cuối cùng không phải là nút cuối cùng. Vì vậy, chúng ta sẽ có một số nút tạm thời, trông giống như nút đầu trỏ đến nút cuối cùng. Bây giờ, chúng ta sẽ làm cho tất cả các nút bên trái lần lượt trỏ đến các nút trước của chúng.

Ngoại trừ nút (nút đầu tiên) được trỏ bởi nút đầu, tất cả các nút phải trỏ đến nút tiền nhiệm, biến chúng thành nút kế nhiệm mới của chúng. Nút đầu tiên sẽ trỏ đến NULL.

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

Danh sách liên kết hiện đã được đảo ngược. Để xem triển khai danh sách liên kết bằng ngôn ngữ lập trình C, vui lòng nhấp vào đây .