🔗 Danh Sách Liên Kết - LinkedList

🎯 Món Ăn Hôm Nay

Trong quán café, ArrayList như một kệ cố định - thêm bớt ở giữa rất khó. LinkedList như chuỗi ghi chú dính nhau - mỗi ghi chú trỏ đến ghi chú tiếp theo, thêm bớt ở đâu cũng dễ dàng! Hôm nay chúng ta học LinkedList - cấu trúc danh sách linh hoạt trong Java!

☕ LinkedList Là Gì?

LinkedList là cấu trúc dữ liệu danh sách liên kết, mỗi phần tử (node) chứa:

• Dữ liệu (data)
• Con trỏ đến phần tử tiếp theo (next)

So sánh với ArrayList:

ArrayList	LinkedList
Mảng động (array-based)	Danh sách liên kết (node-based)
Truy cập nhanh: O(1)	Truy cập chậm: O(n)
Thêm/xóa giữa chậm: O(n)	Thêm/xóa giữa nhanh: O(1)
Tốt cho: Đọc nhiều	Tốt cho: Thêm/xóa nhiều

Tưởng tượng:

• ArrayList: Kệ cố định - tìm ly thứ 5 rất nhanh, nhưng chèn ly vào giữa phải dịch chuyển tất cả
• LinkedList: Chuỗi ghi chú - tìm ghi chú thứ 5 phải đếm từ đầu, nhưng thêm ghi chú mới chỉ cần móc vào

👨‍🍳 Câu Chuyện Trong Quán

Tình huống: Quản lý hàng đợi khách

ArrayList (kệ cố định):

[Anh Minh] [Chị Lan] [Anh Tuấn]
↑
Thêm khách mới ở đầu → Phải dịch chuyển tất cả sang phải!

LinkedList (chuỗi liên kết):

[Anh Minh] → [Chị Lan] → [Anh Tuấn] → null
↑
Thêm khách mới ở đầu → Chỉ cần thay đổi con trỏ!

📝 Công Thức Sử Dụng LinkedList

Ví Dụ 1: Tạo và Thêm Phần Tử

Các cách thêm phần tử:

import java.util.LinkedList;

public class QuanCafe {
    public static void main(String[] args) {
        // 🔗 Tạo LinkedList
        LinkedList<String> danhSachCho = new LinkedList<>();
        
        // Thêm vào cuối
        danhSachCho.add("Anh Minh");
        danhSachCho.add("Chị Lan");
        
        // Thêm vào đầu (nhanh!)
        danhSachCho.addFirst("Anh Tuấn");
        
        // Thêm vào cuối (tương tự add)
        danhSachCho.addLast("Chị Hoa");
        
        // Thêm vào vị trí cụ thể
        danhSachCho.add(2, "Anh Hùng");
        
        // Hiển thị danh sách
        System.out.println("📋 Danh sách chờ:");
        for (int i = 0; i < danhSachCho.size(); i++) {
            System.out.printf("%d. %s%n", i + 1, danhSachCho.get(i));
        }
    }
}

Output:

📋 Danh sách chờ:
1. Anh Tuấn
2. Anh Minh
3. Anh Hùng
4. Chị Lan
5. Chị Hoa

Ví Dụ 2: Xóa Phần Tử

Các cách xóa:

import java.util.LinkedList;

public class QuanCafe {
    public static void main(String[] args) {
        LinkedList<String> danhSachCho = new LinkedList<>();
        danhSachCho.add("Anh Minh");
        danhSachCho.add("Chị Lan");
        danhSachCho.add("Anh Tuấn");
        danhSachCho.add("Chị Hoa");
        
        System.out.println("Ban đầu: " + danhSachCho);
        
        // Xóa phần tử đầu (nhanh!)
        String khachDau = danhSachCho.removeFirst();
        System.out.println("✅ Phục vụ: " + khachDau);
        
        // Xóa phần tử cuối
        String khachCuoi = danhSachCho.removeLast();
        System.out.println("❌ Hủy: " + khachCuoi);
        
        // Xóa theo index
        danhSachCho.remove(0);
        
        // Xóa theo giá trị
        danhSachCho.remove("Anh Tuấn");
        
        System.out.println("Còn lại: " + danhSachCho);
    }
}

Output:

Ban đầu: [Anh Minh, Chị Lan, Anh Tuấn, Chị Hoa]
✅ Phục vụ: Anh Minh
❌ Hủy: Chị Hoa
Còn lại: []

Ví Dụ 3: Truy Cập Phần Tử

Đọc dữ liệu:

import java.util.LinkedList;

public class QuanCafe {
    public static void main(String[] args) {
        LinkedList<String> menu = new LinkedList<>();
        menu.add("Espresso");
        menu.add("Latte");
        menu.add("Cappuccino");
        menu.add("Mocha");
        
        // Lấy phần tử đầu (không xóa)
        String dauTien = menu.getFirst();
        System.out.println("☕ Món đầu tiên: " + dauTien);
        
        // Lấy phần tử cuối
        String cuoiCung = menu.getLast();
        System.out.println("☕ Món cuối cùng: " + cuoiCung);
        
        // Lấy theo index (chậm hơn ArrayList!)
        String monThu2 = menu.get(1);
        System.out.println("☕ Món thứ 2: " + monThu2);
        
        // Kiểm tra tồn tại
        if (menu.contains("Latte")) {
            System.out.println("✅ Có Latte trong menu");
        }
        
        // Kích thước
        System.out.println("Tổng món: " + menu.size());
    }
}

Output:

☕ Món đầu tiên: Espresso
☕ Món cuối cùng: Mocha
☕ Món thứ 2: Latte
✅ Có Latte trong menu
Tổng món: 4

Ví Dụ 4: LinkedList Như Queue (Hàng Đợi)

Sử dụng như hàng đợi FIFO:

import java.util.LinkedList;

public class QuanCafe {
    public static void main(String[] args) {
        // 🚶 Hàng đợi khách
        LinkedList<String> hangDoi = new LinkedList<>();
        
        // Khách đến (thêm vào cuối)
        hangDoi.offer("Anh Minh");
        hangDoi.offer("Chị Lan");
        hangDoi.offer("Anh Tuấn");
        
        System.out.println("📋 Hàng đợi: " + hangDoi);
        
        // Phục vụ khách (lấy từ đầu)
        while (!hangDoi.isEmpty()) {
            String khach = hangDoi.poll();  // Lấy và xóa
            System.out.println("☕ Đang phục vụ: " + khach);
            System.out.println("   Còn lại: " + hangDoi.size() + " khách");
        }
        
        System.out.println("✅ Đã phục vụ xong!");
    }
}

Output:

📋 Hàng đợi: [Anh Minh, Chị Lan, Anh Tuấn]
☕ Đang phục vụ: Anh Minh
   Còn lại: 2 khách
☕ Đang phục vụ: Chị Lan
   Còn lại: 1 khách
☕ Đang phục vụ: Anh Tuấn
   Còn lại: 0 khách
✅ Đã phục vụ xong!

Ví Dụ 5: LinkedList Như Stack (Ngăn Xếp)

Sử dụng như ngăn xếp LIFO:

import java.util.LinkedList;

public class QuanCafe {
    public static void main(String[] args) {
        // 📚 Ngăn xếp ly
        LinkedList<String> nganXep = new LinkedList<>();
        
        // Xếp ly (thêm vào đầu)
        nganXep.push("Ly Latte");
        nganXep.push("Ly Cappuccino");
        nganXep.push("Ly Mocha");
        
        System.out.println("📚 Ngăn xếp: " + nganXep);
        
        // Lấy ly (lấy từ đầu - LIFO)
        while (!nganXep.isEmpty()) {
            String ly = nganXep.pop();  // Lấy và xóa
            System.out.println("☕ Lấy: " + ly);
        }
        
        System.out.println("✅ Hết ly!");
    }
}

Output:

📚 Ngăn xếp: [Ly Mocha, Ly Cappuccino, Ly Latte]
☕ Lấy: Ly Mocha
☕ Lấy: Ly Cappuccino
☕ Lấy: Ly Latte
✅ Hết ly!

Ví Dụ 6: Duyệt LinkedList

Các cách duyệt:

import java.util.LinkedList;
import java.util.Iterator;

public class QuanCafe {
    public static void main(String[] args) {
        LinkedList<String> menu = new LinkedList<>();
        menu.add("Espresso - 45,000");
        menu.add("Latte - 50,000");
        menu.add("Cappuccino - 55,000");
        
        System.out.println("📋 MENU");
        System.out.println("========");
        
        // Cách 1: for-each (khuyên dùng)
        for (String mon : menu) {
            System.out.println("☕ " + mon);
        }
        
        System.out.println();
        
        // Cách 2: Iterator
        Iterator<String> it = menu.iterator();
        while (it.hasNext()) {
            String mon = it.next();
            System.out.println("☕ " + mon);
        }
        
        System.out.println();
        
        // Cách 3: for cổ điển (chậm!)
        for (int i = 0; i < menu.size(); i++) {
            System.out.println("☕ " + menu.get(i));
        }
    }
}

Output:

📋 MENU
========
☕ Espresso - 45,000
☕ Latte - 50,000
☕ Cappuccino - 55,000

☕ Espresso - 45,000
☕ Latte - 50,000
☕ Cappuccino - 55,000

☕ Espresso - 45,000
☕ Latte - 50,000
☕ Cappuccino - 55,000

🔥 Thực Hành Trong Quán

Bài Tập 1: Quản Lý Hàng Đợi

Viết chương trình quản lý hàng đợi khách với thao tác thêm/xóa.

import java.util.LinkedList;

LinkedList<String> hangDoi = new LinkedList<>();

// Khách đến
hangDoi.offer("Anh Minh");
hangDoi.offer("Chị Lan");
System.out.println("Hàng đợi: " + hangDoi);

// Phục vụ khách đầu tiên
String phucVu = hangDoi.poll();
System.out.println("✅ Phục vụ: " + phucVu);
System.out.println("Còn lại: " + hangDoi);

// Thêm khách ưu tiên vào đầu
hangDoi.offerFirst("VIP - Anh Tuấn");
System.out.println("Hàng đợi mới: " + hangDoi);

Bài Tập 2: Lịch Sử Đơn Hàng (Stack)

Tạo lịch sử đơn hàng với khả năng undo.

import java.util.LinkedList;

LinkedList<String> lichSu = new LinkedList<>();

// Thêm đơn hàng
lichSu.push("Đơn #1: 2 Latte");
lichSu.push("Đơn #2: 1 Mocha");
lichSu.push("Đơn #3: 3 Cappuccino");

System.out.println("Lịch sử: " + lichSu);

// Undo đơn cuối
String undo = lichSu.pop();
System.out.println("❌ Hủy: " + undo);
System.out.println("Còn lại: " + lichSu);

// Xem đơn cuối mà không xóa
String peek = lichSu.peek();
System.out.println("👀 Đơn cuối: " + peek);

Bài Tập 3: Danh Sách Ưu Tiên

Quản lý danh sách với khách VIP luôn ở đầu.

import java.util.LinkedList;

public static void themKhach(LinkedList<String> ds, String ten, boolean isVIP) {
    if (isVIP) {
        ds.addFirst("⭐ VIP - " + ten);
    } else {
        ds.addLast(ten);
    }
}

LinkedList<String> danhSach = new LinkedList<>();

themKhach(danhSach, "Anh Minh", false);
themKhach(danhSach, "Chị Lan", true);
themKhach(danhSach, "Anh Tuấn", false);

System.out.println("Danh sách: " + danhSach);
// Output: [⭐ VIP - Chị Lan, Anh Minh, Anh Tuấn]

⚠️ Những Lỗi Đầu Bếp Thường Gặp

Lỗi 1: Dùng get() Trong Vòng Lặp

❌ SAI:

LinkedList<String> list = new LinkedList<>();
// ... thêm 1000 phần tử

// ❌ Rất chậm - O(n²)
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));  // Mỗi get() là O(n)!
}

✅ ĐÚNG:

// ✅ Nhanh - O(n)
for (String item : list) {
    System.out.println(item);
}

Lỗi 2: Dùng LinkedList Khi Cần Truy Cập Ngẫu Nhiên

❌ SAI:

// Cần truy cập nhiều lần theo index
LinkedList<Integer> gia = new LinkedList<>();
// ...
int g1 = gia.get(5);   // Chậm!
int g2 = gia.get(10);  // Chậm!

✅ ĐÚNG:

// Dùng ArrayList cho truy cập ngẫu nhiên
ArrayList<Integer> gia = new ArrayList<>();
// ...
int g1 = gia.get(5);   // Nhanh!
int g2 = gia.get(10);  // Nhanh!

Lỗi 3: Không Kiểm Tra isEmpty()

❌ SAI:

LinkedList<String> hangDoi = new LinkedList<>();
String khach = hangDoi.poll();  // ❌ Trả về null nếu rỗng!
System.out.println(khach.toUpperCase());  // NullPointerException!

✅ ĐÚNG:

if (!hangDoi.isEmpty()) {
    String khach = hangDoi.poll();
    System.out.println(khach.toUpperCase());
} else {
    System.out.println("⚠️ Hàng đợi rỗng!");
}

Lỗi 4: Xóa Sai Trong Vòng Lặp

❌ SAI:

// ❌ ConcurrentModificationException!
for (String item : list) {
    if (item.equals("Xóa")) {
        list.remove(item);  // ❌ Lỗi!
    }
}

✅ ĐÚNG:

// ✅ Dùng Iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("Xóa")) {
        it.remove();  // ✅ OK
    }
}

💡 Bí Quyết Của Barista

1. Khi Nào Dùng LinkedList?

• Thêm/xóa nhiều ở đầu/cuối: addFirst(), removeFirst()
• Hàng đợi (Queue): FIFO - First In First Out
• Ngăn xếp (Stack): LIFO - Last In First Out
• Ít truy cập ngẫu nhiên: Không dùng get(index) nhiều

2. Khi Nào Dùng ArrayList?

• Truy cập ngẫu nhiên nhiều: get(index) thường xuyên
• Đọc nhiều hơn ghi
• Thêm/xóa chủ yếu ở cuối

3. Methods Quan Trọng

Thêm:

add(item)           // Thêm cuối
addFirst(item)      // Thêm đầu
addLast(item)       // Thêm cuối
offer(item)         // Queue - thêm cuối
offerFirst(item)    // Thêm đầu
offerLast(item)     // Thêm cuối
push(item)          // Stack - thêm đầu

Xóa:

remove(item)        // Xóa phần tử
removeFirst()       // Xóa đầu
removeLast()        // Xóa cuối
poll()              // Queue - lấy và xóa đầu
pop()               // Stack - lấy và xóa đầu

Đọc:

get(index)          // Lấy theo index (chậm!)
getFirst()          // Lấy đầu
getLast()           // Lấy cuối
peek()              // Xem đầu (không xóa)
peekFirst()         // Xem đầu
peekLast()          // Xem cuối

4. Performance Cheat Sheet

// LinkedList
addFirst/Last:    O(1)  ⚡ Nhanh
removeFirst/Last: O(1)  ⚡ Nhanh
get(index):       O(n)  🐌 Chậm
add(index):       O(n)  🐌 Chậm

// ArrayList
add:              O(1)  ⚡ Nhanh (amortized)
get(index):       O(1)  ⚡ Nhanh
add(0):           O(n)  🐌 Chậm (dịch chuyển)
remove(0):        O(n)  🐌 Chậm (dịch chuyển)

🎓 Bạn Đã Học Được

• ✅ LinkedList: Danh sách liên kết với node
• ✅ Thêm/xóa đầu/cuối: Rất nhanh O(1)
• ✅ Truy cập index: Chậm O(n)
• ✅ Queue: offer(), poll(), peek()
• ✅ Stack: push(), pop(), peek()
• ✅ Duyệt: for-each hoặc Iterator (KHÔNG dùng get())
• ✅ So với ArrayList: Chọn đúng cho use case

☕ Món Tiếp Theo

Bài tiếp theo: 🗺️ Bảng Băm - HashMap

Học cách lưu menu với cặp key-value (tên món - giá)!

---

💡 Lời Khuyên Cuối: LinkedList rất mạnh cho queue và stack, nhưng đừng lạm dụng! Nếu bạn thấy mình dùng get(index) nhiều, hãy chuyển sang ArrayList. Chọn đúng cấu trúc dữ liệu = code nhanh gấp 100 lần! 🔗☕