02. Linked Lists (Danh sách liên kết)
🎯 Mục tiêu học tập
- Hiểu khái niệm Node và cách liên kết
- Phân biệt các loại Linked List
- Cài đặt các thao tác cơ bản
- So sánh với Array về performance và memory
📚 Lý thuyết
Linked List là gì?
Định nghĩa: Cấu trúc dữ liệu tuyến tính với các phần tử (nodes) được liên kết thông qua con trỏ/reference.
Cấu trúc Node:
class Node {
int data; // Dữ liệu
Node next; // Con trỏ tới node tiếp theo
}
Đặc điểm chính:
- Kích thước động (thêm/xóa linh hoạt)
- Bộ nhớ không liên tiếp
- Không truy cập ngẫu nhiên (phải duyệt từ đầu)
- Memory overhead cho con trỏ
🔍 Các loại Linked List
1. Singly Linked List (Danh sách liên kết đơn)
[Data|Next] -> [Data|Next] -> [Data|Next] -> null
- Mỗi node chỉ có 1 con trỏ next
- Chỉ duyệt được một chiều (từ head → tail)
2. Doubly Linked List (Danh sách liên kết đôi)
null <- [Prev|Data|Next] <-> [Prev|Data|Next] <-> [Prev|Data|Next] -> null
- Mỗi node có 2 con trỏ: prev và next
- Duyệt được cả hai chiều
- Tốn nhiều memory hơn
3. Circular Linked List (Danh sách liên kết vòng)
[Data|Next] -> [Data|Next] -> [Data|Next] ⤴
↑ |
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
- Node cuối trỏ về node đầu
- Không có null ở cuối
⚡ Độ phức tạp thời gian
| Thao tác | Array | Linked List |
|---|---|---|
| Truy cập (index) | O(1) | O(n) |
| Tìm kiếm | O(n) | O(n) |
| Chèn đầu | O(n) | O(1) |
| Chèn cuối | O(1) | O(n) hoặc O(1)* |
| Chèn giữa | O(n) | O(n) |
| Xóa đầu | O(n) | O(1) |
| Xóa cuối | O(1) | O(n) hoặc O(1)* |
| Xóa giữa | O(n) | O(n) |
*O(1) nếu có con trỏ tail
💡 Ưu nhược điểm
Ưu điểm:
- Kích thước động
- Chèn/xóa ở đầu rất nhanh O(1)
- Không cần khai báo kích thước trước
- Memory được cấp phát khi cần
Nhược điểm:
- Không truy cập ngẫu nhiên
- Memory overhead cho con trỏ
- Cache performance kém (bộ nhớ rải rác)
- Dễ tạo memory leak nếu không quản lý tốt
🔧 Thao tác cơ bản cần implement
Singly Linked List:
- insertFirst(data): Thêm node vào đầu
- insertLast(data): Thêm node vào cuối
- insertAt(index, data): Thêm node vào vị trí chỉ định
- deleteFirst(): Xóa node đầu
- deleteLast(): Xóa node cuối
- deleteAt(index): Xóa node tại vị trí chỉ định
- search(data): Tìm kiếm node chứa dữ liệu
- get(index): Lấy dữ liệu tại vị trí index
- size(): Đếm số node
- display(): In toàn bộ danh sách
- reverse(): Đảo ngược danh sách
- isEmpty(): Kiểm tra danh sách rỗng
Doubly Linked List (thêm):
- insertBefore(node, data): Thêm trước node chỉ định
- insertAfter(node, data): Thêm sau node chỉ định
- displayReverse(): In ngược từ cuối
🎨 Kỹ thuật quan trọng
1. Two Pointers (Con trỏ đôi)
// Tìm middle node
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow sẽ ở giữa
2. Dummy Node
// Tạo node giả để đơn giản hóa code
Node dummy = new Node(0);
dummy.next = head;
// Làm việc với dummy.next thay vì head
3. Recursive Operations
// Reverse recursively
public Node reverse(Node node) {
if (node == null || node.next == null) return node;
Node reversed = reverse(node.next);
node.next.next = node;
node.next = null;
return reversed;
}
📋 Bài tập thực hành
Cơ bản:
- Cài đặt Singly Linked List với tất cả operations
- Tìm middle node của linked list
- Detect cycle trong linked list
- Merge hai sorted linked lists
Nâng cao:
- Reverse linked list (iterative & recursive)
- Remove duplicates from sorted list
- Add two numbers represented as linked lists
- Clone linked list with random pointers
- LRU Cache implementation
🚀 Use cases thực tế
Khi nào dùng Linked List:
- Undo operations (text editor)
- Music playlist (previous/next)
- Browser history (back/forward)
- Memory allocation
- Adjacency list in graphs
Khi nào KHÔNG dùng:
- Cần truy cập ngẫu nhiên thường xuyên
- Bộ nhớ hạn chế
- Cần cache performance cao
- Làm việc với big data
🚀 Chuẩn bị code
mkdir 02-linked-lists
cd 02-linked-lists
# Files sẽ được tạo:
# - SinglyLinkedList.java (Basic implementation)
# - DoublyLinkedList.java (Doubly implementation)
# - LinkedListProblems.java (Practice problems)
# - Node.java (Node classes)