Trong hướng dẫn này, bạn sẽ tìm hiểu về cấu trúc dữ liệu danh sách liên kết và cách triển khai nó bằng Python, Java, C và C ++.
Cấu trúc dữ liệu danh sách liên kết bao gồm một loạt các nút được kết nối. Tại đây, mỗi nút lưu trữ dữ liệu và địa chỉ của nút tiếp theo. Ví dụ,
Cấu trúc dữ liệu LinkedList
Bạn phải bắt đầu ở đâu đó, vì vậy chúng tôi đặt cho địa chỉ của nút đầu tiên một cái tên đặc biệt là HEAD.
Ngoài ra, nút cuối cùng trong danh sách được liên kết có thể được xác định vì phần tiếp theo của nó trỏ đến NULL.
Bạn có thể đã chơi trò chơi Truy tìm kho báu, trong đó mỗi manh mối bao gồm thông tin về manh mối tiếp theo. Đó là cách hoạt động của danh sách liên kết.
Đại diện của LinkedList
Hãy xem từng nút của LinkedList được biểu diễn như thế nào. Mỗi nút bao gồm:
- Một mục dữ liệu
- Địa chỉ của một nút khác
Chúng tôi bao gồm cả mục dữ liệu và tham chiếu nút tiếp theo trong một cấu trúc như sau:
struct node ( int data; struct node *next; );
Hiểu cấu trúc của một nút danh sách liên kết là chìa khóa để bạn nắm được nó.
Mỗi nút cấu trúc có một mục dữ liệu và một con trỏ đến một nút cấu trúc khác. Hãy để chúng tôi tạo một Danh sách liên kết đơn giản với ba mục để hiểu cách hoạt động của nó.
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data=3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;
Nếu bạn không hiểu bất kỳ dòng nào ở trên, tất cả những gì bạn cần là cập nhật về con trỏ và cấu trúc.
Chỉ trong một vài bước, chúng tôi đã tạo một danh sách liên kết đơn giản với ba nút.
Trình bày danh sách liên kết
Sức mạnh của LinkedList đến từ khả năng phá vỡ chuỗi và tham gia lại nó. Ví dụ: nếu bạn muốn đặt một phần tử 4 giữa 1 và 2, các bước sẽ là:
- Tạo một nút cấu trúc mới và cấp phát bộ nhớ cho nó.
- Thêm giá trị dữ liệu của nó là 4
- Trỏ con trỏ tiếp theo của nó đến nút cấu trúc chứa 2 làm giá trị dữ liệu
- Thay đổi con trỏ tiếp theo của "1" thành nút chúng ta vừa tạo.
Làm điều gì đó tương tự trong một mảng sẽ yêu cầu chuyển vị trí của tất cả các phần tử tiếp theo.
Trong python và Java, danh sách liên kết có thể được triển khai bằng cách sử dụng các lớp như được hiển thị trong mã bên dưới.
Tiện ích danh sách được liên kết
Danh sách là một trong những cấu trúc dữ liệu phổ biến và hiệu quả nhất, được triển khai trong mọi ngôn ngữ lập trình như C, C ++, Python, Java và C #.
Ngoài ra, danh sách được liên kết là một cách tuyệt vời để tìm hiểu cách hoạt động của con trỏ. Bằng cách thực hành cách thao tác với danh sách được liên kết, bạn có thể chuẩn bị cho mình để học các cấu trúc dữ liệu nâng cao hơn như biểu đồ và cây.
Triển khai danh sách được liên kết trong ví dụ Python, Java, C và C ++
Python Java C C + # Linked list implementation in Python class Node: # Creating a node def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None if __name__ == '__main__': linked_list = LinkedList() # Assign item values linked_list.head = Node(1) second = Node(2) third = Node(3) # Connect nodes linked_list.head.next = second second.next = third # Print the linked list item while linked_list.head != None: print(linked_list.head.item, end=" ") linked_list.head = linked_list.head.next
// Linked list implementation in Java class LinkedList ( // Creating a node Node head; static class Node ( int value; Node next; Node(int d) ( value = d; next = null; ) ) public static void main(String() args) ( LinkedList linkedList = new LinkedList(); // Assign value values linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); // Connect nodess linkedList.head.next = second; second.next = third; // printing node-value while (linkedList.head != null) ( System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; ) ) )
// Linked list implementation in C #include #include // Creating a node struct node ( int value; struct node *next; ); // print the linked list value void printLinkedlist(struct node *p) ( while (p != NULL) ( printf("%d ", p->value); p = p->next; ) ) int main() ( // Initialize nodes struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; // Allocate memory one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // printing node-value head = one; printLinkedlist(head); )
// Linked list implementation in C++ #include using namespace std; // Creating a node class Node ( public: int value; Node* next; ); int main() ( Node* head; Node* one = NULL; Node* two = NULL; Node* three = NULL; // allocate 3 nodes in the heap one = new Node(); two = new Node(); three = new Node(); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // print the linked list value head = one; while (head != NULL) ( printf("%d ", head->value); head = head->next; ) )
Độ phức tạp của danh sách được liên kết
Thời gian phức tạp
| Trường hợp xấu nhất | Trường hợp trung bình | |
|---|---|---|
| Tìm kiếm | Trên) | Trên) |
| Chèn | O (1) | O (1) |
| Xóa | O (1) | O (1) |
Độ phức tạp không gian: O (n)
Ứng dụng danh sách được liên kết
- Cấp phát bộ nhớ động
- Được triển khai trong ngăn xếp và hàng đợi
- Trong chức năng hoàn tác của phần mềm
- Bảng băm, đồ thị
Bài đọc được đề xuất
1. Hướng dẫn
- Hoạt động liên kết danh sách (Traverse, Chèn, Xóa)
- Các loại danh sách liên kết
- Java LinkedList
2. Ví dụ
- Nhận phần tử giữa của LinkedList trong một lần lặp lại
- Chuyển đổi LinkedList thành Mảng và ngược lại
- Phát hiện vòng lặp trong LinkedList
