Giới thiệu
Danh sách liên kết là một cấu trúc dữ liệu cơ bản mà mọi lập trình viên nên thành thạo. Khác với mảng, danh sách liên kết không yêu cầu phân bổ bộ nhớ liên tiếp, điều này giúp chúng trở nên hiệu quả hơn cho các thao tác chèn và xóa.
Trong bài viết này, chúng ta sẽ khám phá hai loại danh sách liên kết quan trọng:
- Danh Sách Liên Kết Đôi (DLL)
- Danh Sách Liên Kết Vòng (CLL)
Chúng ta sẽ thực hiện cả hai loại danh sách trong Java, từng bước một.
🔹 Danh Sách Liên Kết Đôi (DLL) trong Java
Danh Sách Liên Kết Đôi có các nút chứa:
- Dữ liệu
- Một con trỏ đến nút trước đó
- Một con trỏ đến nút tiếp theo
Điều này cho phép duyệt qua cả hai hướng: tiến và lùi.
Cài đặt
java
// Lớp Node cho Danh Sách Liên Kết Đôi
class Node {
int data;
Node prev, next;
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
// Lớp Danh Sách Liên Kết Đôi
class DoublyLinkedList {
private Node head;
// Thêm vào đầu
public void insertFront(int data) {
Node newNode = new Node(data);
if (head != null) {
newNode.next = head;
head.prev = newNode;
}
head = newNode;
}
// Thêm vào cuối
public void insertEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
newNode.prev = temp;
}
// Xóa nút theo giá trị
public void delete(int key) {
Node temp = head;
while (temp != null) {
if (temp.data == key) {
if (temp.prev != null) {
temp.prev.next = temp.next;
} else {
head = temp.next; // xóa đầu
}
if (temp.next != null) {
temp.next.prev = temp.prev;
}
return;
}
temp = temp.next;
}
System.out.println("Giá trị " + key + " không tìm thấy!");
}
// Hiển thị tiến
public void displayForward() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " <-> ");
temp = temp.next;
}
System.out.println("null");
}
// Hiển thị lùi
public void displayBackward() {
Node temp = head;
if (temp == null) return;
// Đi đến nút cuối
while (temp.next != null) {
temp = temp.next;
}
// In ngược lại
while (temp != null) {
System.out.print(temp.data + " <-> ");
temp = temp.prev;
}
System.out.println("null");
}
}
// Ví dụ
public class Main {
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
dll.insertEnd(10);
dll.insertEnd(20);
dll.insertFront(5);
dll.insertEnd(30);
System.out.println("Duyệt Tiến:");
dll.displayForward();
System.out.println("Duyệt Lùi:");
dll.displayBackward();
dll.delete(20);
System.out.println("Sau khi xóa 20:");
dll.displayForward();
}
}🔹 Danh Sách Liên Kết Vòng (CLL) trong Java
Danh Sách Liên Kết Vòng là một biến thể trong đó nút cuối cùng trỏ lại đầu danh sách. Điều này tạo thành một vòng tròn và cho phép duyệt liên tục.
Chúng ta sẽ thực hiện một Danh Sách Liên Kết Vòng Đơn ở đây.
Cài đặt
java
// Lớp Node cho Danh Sách Liên Kết Vòng
class CNode {
int data;
CNode next;
public CNode(int data) {
this.data = data;
this.next = null;
}
}
// Lớp Danh Sách Liên Kết Vòng
class CircularLinkedList {
private CNode head = null;
private CNode tail = null;
// Thêm vào cuối
public void insert(int data) {
CNode newNode = new CNode(data);
if (head == null) {
head = newNode;
tail = newNode;
newNode.next = head; // trỏ đến chính nó
} else {
tail.next = newNode;
tail = newNode;
tail.next = head; // nút cuối trỏ lại đầu
}
}
// Xóa một nút
public void delete(int key) {
if (head == null) return;
CNode current = head, prev = null;
// Trường hợp: xóa đầu
if (head.data == key) {
if (head == tail) {
head = tail = null;
return;
}
head = head.next;
tail.next = head;
return;
}
// Tìm kiếm giá trị
do {
prev = current;
current = current.next;
if (current.data == key) {
prev.next = current.next;
if (current == tail) {
tail = prev;
}
return;
}
} while (current != head);
System.out.println("Giá trị " + key + " không tìm thấy!");
}
// Hiển thị các nút
public void display() {
if (head == null) {
System.out.println("Danh sách rỗng!");
return;
}
CNode temp = head;
do {
System.out.print(temp.data + " -> ");
temp = temp.next;
} while (temp != head);
System.out.println("(quay lại đầu)");
}
}
// Ví dụ
public class CircularMain {
public static void main(String[] args) {
CircularLinkedList cll = new CircularLinkedList();
cll.insert(10);
cll.insert(20);
cll.insert(30);
cll.insert(40);
System.out.println("Danh Sách Liên Kết Vòng:");
cll.display();
cll.delete(20);
System.out.println("Sau khi xóa 20:");
cll.display();
}
}🔹 Những Điểm Khác Nhau Chính
| Đặc điểm | Danh Sách Liên Kết Đôi (DLL) | Danh Sách Liên Kết Vòng (CLL) |
|---|---|---|
| Duyệt | Tiến & Lùi | Tiến (vòng liên tục) |
| Nút Cuối Trỏ Đến | null |
Nút đầu |
| Sử Dụng Bộ Nhớ | Nhiều hơn (liên kết prev thêm) |
Ít hơn (một liên kết) |
| Trường Hợp Sử Dụng | Deques, Điều hướng | Tác vụ vòng tròn, Bộ đệm |
🔹 Thực Hành Tốt Nhất
- Sử dụng danh sách liên kết đôi khi bạn cần duyệt hai chiều.
- Sử dụng danh sách liên kết vòng cho các ứng dụng như lập lịch vòng tròn và cấu trúc lặp liên tục.
🔹 Những Cạm Bẫy Thường Gặp
- Quên cập nhật các liên kết trong danh sách khi xóa nút.
- Duyệt qua danh sách liên kết vòng mà không có điều kiện dừng sẽ dẫn đến vòng lặp vô hạn.
🔹 Mẹo Tối Ưu Hiệu Suất
- Cố gắng tối ưu các thao tác chèn và xóa bằng cách duy trì các con trỏ đến nút đầu và nút cuối.
- Sử dụng danh sách liên kết đôi cho các tác vụ cần truy cập nhanh.
🔹 Kết Luận
Danh Sách Liên Kết Đôi rất hữu ích khi bạn cần duyệt hai chiều. Danh Sách Liên Kết Vòng là lựa chọn tốt nhất cho các ứng dụng như lập lịch vòng tròn, cấu trúc lặp liên tục và bộ đệm. Cả hai đều là các cấu trúc dữ liệu mạnh mẽ và được sử dụng rộng rãi trong các kịch bản thực tế như hệ điều hành, trình duyệt (điều hướng lùi/tiến) và quản lý bộ nhớ.
🔹 Câu Hỏi Thường Gặp
1. Danh sách liên kết có ưu điểm gì so với mảng?
- Danh sách liên kết cho phép chèn và xóa nhanh hơn mà không cần di chuyển các phần tử khác.
2. Làm thế nào để chọn giữa danh sách liên kết đôi và danh sách liên kết vòng?
- Chọn danh sách liên kết đôi khi bạn cần truy cập cả hai hướng, còn danh sách liên kết vòng tốt cho các thuật toán cần lặp liên tục.
