Một danh sách liên kết (Linked list) là một cấu trúc dữ liệu động, bao gồm một tập hợp các phần tử (node) có thể được liên kết với nhau theo một thứ tự nhất định. Mỗi phần tử của danh sách (node) chứa một giá trị dữ liệu và một con trỏ (pointer) trỏ tới phần tử tiếp theo trong danh sách.
Các loại danh sách liên kết chính bao gồm:
Danh sách liên kết đơn (Singly linked list): mỗi node chỉ có một con trỏ trỏ tới phần tử tiếp theo trong danh sách.
Danh sách liên kết đôi (Doubly linked list): mỗi node có hai con trỏ, một con trỏ trỏ tới phần tử tiếp theo và một con trỏ trỏ tới phần tử trước đó trong danh sách.
Danh sách liên kết vòng (Circular linked list): danh sách liên kết trong đó phần tử cuối cùng của danh sách trỏ tới phần tử đầu tiên để tạo thành một vòng.
Danh sách liên kết được sử dụng trong nhiều ứng dụng, bao gồm việc triển khai các danh sách, hàng đợi, ngăn xếp và bộ nhớ động. Tuy nhiên, vì các phần tử trong danh sách không được lưu trữ liên tiếp nhau trong bộ nhớ, việc truy cập ngẫu nhiên đến các phần tử trong danh sách liên kết có thể là không hiệu quả.
Dưới đây là một ví dụ về danh sách liên kết đơn với Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = new_node
def display(self):
current_node = self.head
while current_node is not None:
print(current_node.data, end=' ')
current_node = current_node.next
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.display() # Output: 1 2 3
Trong ví dụ này, chúng ta định nghĩa hai lớp là Node và LinkedList. Lớp Node chứa hai thuộc tính là data và next, thể hiện giá trị của phần tử và con trỏ trỏ tới phần tử tiếp theo trong danh sách. Lớp LinkedList bao gồm các phương thức để thêm một phần tử mới vào danh sách và hiển thị toàn bộ danh sách. Phương thức append tạo một nút mới và chèn nút đó vào cuối danh sách, trong khi phương thức display duyệt qua toàn bộ danh sách và in ra giá trị của mỗi phần tử.
Chúng ta tạo một đối tượng linked_list thuộc lớp LinkedList, sau đó thêm ba phần tử vào danh sách và cuối cùng hiển thị toàn bộ danh sách. Kết quả đầu ra là: 1 2 3.
Dưới đây là một ví dụ về danh sách liên kết đơn trong C++:
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() {
head = nullptr;
}
void add(int data) {
Node* new_node = new Node(data);
if (head == nullptr) {
head = new_node;
} else {
Node* current_node = head;
while (current_node->next != nullptr) {
current_node = current_node->next;
}
current_node->next = new_node;
}
}
void display() {
Node* current_node = head;
while (current_node != nullptr) {
cout << current_node->data << " ";
current_node = current_node->next;
}
}
};
int main() {
LinkedList linked_list;
linked_list.add(1);
linked_list.add(2);
linked_list.add(3);
linked_list.display(); // Output: 1 2 3
return 0;
}
Trong ví dụ này, chúng ta định nghĩa hai lớp là Node và LinkedList. Lớp Node chứa hai thuộc tính là data và next, thể hiện giá trị của phần tử và con trỏ trỏ tới phần tử tiếp theo trong danh sách. Lớp LinkedList bao gồm các phương thức để thêm một phần tử mới vào danh sách và hiển thị toàn bộ danh sách. Phương thức add tạo một nút mới và chèn nút đó vào cuối danh sách, trong khi phương thức display duyệt qua toàn bộ danh sách và in ra giá trị của mỗi phần tử.
Chúng ta tạo một đối tượng linked_list thuộc lớp LinkedList, sau đó thêm ba phần tử vào danh sách và cuối cùng hiển thị toàn bộ danh sách. Kết quả đầu ra là: 1 2 3. Lưu ý rằng trong ví dụ này, chúng ta sử dụng nullptr thay vì NULL để đại diện cho con trỏ null trong C++.