Khám phá Danh sách liên kết: Cấu trúc dữ liệu tuyến tính linh hoạt

Chào mừng bạn đến với bài viết thứ tư trong series về cấu trúc dữ liệu và giải thuật. Hôm nay, chúng ta sẽ khám phá một cấu trúc dữ liệu tuyến tính rất quan trọng: Danh sách liên kết (Linked List). Danh sách liên kết cung cấp một cách linh hoạt để lưu trữ và quản lý dữ liệu. Chúng là một lựa chọn thay thế tuyệt vời cho mảng trong nhiều tình huống.

Danh sách liên kết là gì?

Danh sách liên kết là một tập hợp các phần tử dữ liệu, được gọi là các nút (node). Mỗi nút chứa hai thành phần chính: dữ liệu và một con trỏ (pointer). Con trỏ này trỏ đến nút tiếp theo trong danh sách. Điều này tạo ra một chuỗi các nút liên kết với nhau. Nút cuối cùng trong danh sách có con trỏ trỏ đến null, đánh dấu sự kết thúc của danh sách.

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

Có ba loại danh sách liên kết chính:

• Danh sách liên kết đơn (Singly Linked List): Mỗi nút chỉ có một con trỏ, trỏ đến nút tiếp theo.
• Danh sách liên kết đôi (Doubly Linked List): Mỗi nút có hai con trỏ, một trỏ đến nút tiếp theo và một trỏ đến nút trước đó.
• Danh sách liên kết vòng (Circular Linked List): Nút cuối cùng trỏ đến nút đầu tiên, tạo thành một vòng tròn.

Danh sách liên kết đơn (Singly Linked List)

Đây là loại danh sách liên kết đơn giản nhất. Mỗi nút chứa dữ liệu và một con trỏ đến nút tiếp theo. Việc duyệt danh sách chỉ có thể thực hiện theo một hướng, từ đầu đến cuối.

Ví dụ minh họa bằng Java:

class Node {
 int data;
 Node next;

 Node(int data) {
 this.data = data;
 this.next = null;
 }
}

class SinglyLinkedList {
 Node head;

 // Thêm một nút vào cuối danh sách
 public void append(int data) {
 Node newNode = new Node(data);
 if (head == null) {
 head = newNode;
 return;
 }
 Node current = head;
 while (current.next != null) {
 current = current.next;
 }
 current.next = newNode;
 }

 // In danh sách
 public void printList() {
 Node current = head;
 while (current != null) {
 System.out.print(current.data + " ");
 current = current.next;
 }
 System.out.println();
 }

 public static void main(String[] args) {
 SinglyLinkedList list = new SinglyLinkedList();
 list.append(1);
 list.append(2);
 list.append(3);
 list.printList(); // Output: 1 2 3
 }
}

Danh sách liên kết đôi (Doubly Linked List)

Danh sách liên kết đôi cho phép duyệt theo cả hai hướng. Mỗi nút có hai con trỏ: 'next' trỏ đến nút tiếp theo và 'prev' trỏ đến nút trước đó.

Ví dụ minh họa bằng Java:

class Node {
 int data;
 Node next;
 Node prev;

 Node(int data) {
 this.data = data;
 this.next = null;
 this.prev = null;
 }
}

class DoublyLinkedList {
 Node head;
 Node tail;

 // Thêm một nút vào cuối danh sách
 public void append(int data) {
 Node newNode = new Node(data);
 if (head == null) {
 head = newNode;
 tail = newNode;
 return;
 }
 tail.next = newNode;
 newNode.prev = tail;
 tail = newNode;
 }

 // In danh sách từ đầu đến cuối
 public void printList() {
 Node current = head;
 while (current != null) {
 System.out.print(current.data + " ");
 current = current.next;
 }
 System.out.println();
 }

 public static void main(String[] args) {
 DoublyLinkedList list = new DoublyLinkedList();
 list.append(1);
 list.append(2);
 list.append(3);
 list.printList(); // Output: 1 2 3
 }
}

Danh sách liên kết vòng (Circular Linked List)

Trong danh sách liên kết vòng, nút cuối cùng trỏ đến nút đầu tiên, tạo thành một vòng tròn. Điều này có nghĩa là không có nút nào có con trỏ trỏ đến null.

Ví dụ minh họa bằng Java:

class Node {
 int data;
 Node next;

 Node(int data) {
 this.data = data;
 this.next = null;
 }
}

class CircularLinkedList {
 Node head;

 // Thêm một nút vào cuối danh sách
 public void append(int data) {
 Node newNode = new Node(data);
 if (head == null) {
 head = newNode;
 newNode.next = head; // Nút mới trỏ đến chính nó
 return;
 }
 Node current = head;
 while (current.next != head) { // Đi cho đến khi nút tiếp theo là head
 current = current.next;
 }
 current.next = newNode;
 newNode.next = head; // Nút mới trỏ đến head
 }

 // In danh sách
 public void printList() {
 if (head == null) {
 return;
 }
 Node current = head;
 do {
 System.out.print(current.data + " ");
 current = current.next;
 } while (current != head);
 System.out.println();
 }

 public static void main(String[] args) {
 CircularLinkedList list = new CircularLinkedList();
 list.append(1);
 list.append(2);
 list.append(3);
 list.printList(); // Output: 1 2 3
 }
}

Thêm, xóa và tìm kiếm một nút

Các thao tác cơ bản trên danh sách liên kết bao gồm thêm một nút, xóa một nút và tìm kiếm một nút.

• Thêm một nút: Có thể thêm một nút vào đầu, cuối hoặc giữa danh sách.
• Xóa một nút: Có thể xóa một nút dựa trên vị trí hoặc giá trị của nó.
• Tìm kiếm một nút: Duyệt qua danh sách để tìm một nút có giá trị cụ thể.

So sánh với Mảng

Danh sách liên kết và mảng là hai cấu trúc dữ liệu tuyến tính khác nhau. Dưới đây là một số so sánh:

• Kích thước: Mảng có kích thước cố định, trong khi danh sách liên kết có thể thay đổi kích thước động.
• Bộ nhớ: Mảng yêu cầu bộ nhớ liền kề, trong khi danh sách liên kết có thể lưu trữ các nút ở các vị trí bộ nhớ khác nhau.
• Chèn/Xóa: Chèn hoặc xóa một phần tử ở giữa mảng có thể tốn kém, trong khi nó hiệu quả hơn trong danh sách liên kết.
• Truy cập: Truy cập một phần tử trong mảng rất nhanh (O(1)), trong khi cần duyệt qua danh sách liên kết (O(n)).

Kết luận

Danh sách liên kết là một cấu trúc dữ liệu mạnh mẽ và linh hoạt. Chúng cung cấp nhiều ưu điểm so với mảng trong một số tình huống nhất định. Hiểu rõ về danh sách liên kết và các biến thể của nó là rất quan trọng đối với bất kỳ lập trình viên nào. Hãy tiếp tục khám phá và thực hành để làm chủ cấu trúc dữ liệu này!