Cấu Trúc Dữ Liệu JavaScript: Danh Sách Liên Kết

Khi nghĩ đến việc lưu trữ dữ liệu trong JavaScript, mảng thường là lựa chọn đầu tiên. Tuy nhiên, mảng không phải lúc nào cũng hiệu quả cho các thao tác như chèn hoặc xóa ở giữa.
👉 Đó là lúc Danh Sách Liên Kết phát huy tác dụng.

🔗 Danh Sách Liên Kết là gì?

Danh Sách Liên Kết là một cấu trúc dữ liệu tuyến tính, trong đó mỗi phần tử (gọi là nút) chỉ đến phần tử tiếp theo. Không giống như mảng, danh sách liên kết không lưu trữ các phần tử trong bộ nhớ liên tiếp.

• Mỗi nút chứa:
  • Giá trị (dữ liệu)
  • Một tham chiếu (con trỏ) đến nút tiếp theo

Ví dụ cấu trúc:

[đầu] → [nút1] → [nút2] → [nút3] → null

🛠 Triển Khai Danh Sách Liên Kết trong JavaScript

Lớp Node

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

Lớp LinkedList

class LinkedList {
  constructor() {
    this.head = null;
  }

  // Chèn vào cuối
  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }

  // Chèn vào đầu
  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
  }

  // Tìm một nút
  find(value) {
    let current = this.head;
    while (current) {
      if (current.value === value) return current;
      current = current.next;
    }
    return null;
  }

  // Xóa một nút
  delete(value) {
    if (!this.head) return;

    if (this.head.value === value) {
      this.head = this.head.next;
      return;
    }

    let current = this.head;
    while (current.next && current.next.value !== value) {
      current = current.next;
    }

    if (current.next) {
      current.next = current.next.next;
    }
  }

  // In tất cả giá trị
  print() {
    let values = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join(" → "));
  }
}

✅ Ví dụ Thực Tế

const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.prepend(5);

list.print(); // 5 → 10 → 20 → 30

console.log(list.find(20)); // Node { value: 20, next: Node { value: 30, ... } }

list.delete(10);
list.print(); // 5 → 20 → 30

🚀 Khi Nào Nên Sử Dụng Danh Sách Liên Kết

• Khi cần chèn/xóa thường xuyên
• Khi cần quản lý bộ nhớ một cách động
• Khi việc thay đổi kích thước mảng quá tốn kém

⚖️ Ưu Nhược Điểm

✅ Ưu điểm:

• Chèn/xóa hiệu quả
• Kích thước động

❌ Nhược điểm:

• Truy cập chậm hơn (không có truy cập chỉ số trực tiếp như mảng)
• Tốn nhiều bộ nhớ (lưu trữ con trỏ thêm)

🎯 Kết Luận

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 hiểu. Mặc dù mảng phổ biến hơn trong JavaScript, việc biết đến danh sách liên kết giúp bạn hiểu sâu hơn về bộ nhớ, hiệu suất và thuật toán.

Lần tới khi bạn cần chèn hoặc xóa linh hoạt, hãy nghĩ đến những thứ vượt xa mảng — và thử dùng Danh Sách Liên Kết!

🔍 Câu Hỏi Thường Gặp (FAQ)

1. Danh sách liên kết có thể được sử dụng ở đâu?
Danh sách liên kết thường được sử dụng trong các ứng dụng yêu cầu chèn và xóa liên tục, chẳng hạn như trong quản lý danh sách người dùng hoặc các ứng dụng trò chơi.

2. Danh sách liên kết có nhanh hơn mảng không?
Danh sách liên kết nhanh hơn mảng trong việc chèn và xóa, nhưng chậm hơn trong việc truy cập ngẫu nhiên.

📚 Tài Nguyên Tham Khảo

• JavaScript Data Structures
• Algorithms and Data Structures

Hy vọng bài viết này đã giúp bạn hiểu rõ hơn về danh sách liên kết trong JavaScript!