Giới thiệu

Chào các bạn 👋! Hôm nay chúng ta sẽ khám phá một khái niệm quan trọng trong cấu trúc dữ liệu - Danh sách liên kết (Linked List) trong JavaScript. Đây là một phần không thể thiếu trong hành trình học tập về cấu trúc dữ liệu và thuật toán của chúng ta.

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

Danh sách liên kết là một chuỗi các phần tử được kết nối với nhau theo một thứ tự nhất định. Hãy tưởng tượng bạn đang tham gia một cuộc săn kho báu, nơi mỗi manh mối nằm trên một mảnh giấy riêng biệt. Manh mối đầu tiên rất dễ tìm, nhưng các manh mối tiếp theo được giấu ở các vị trí khác nhau và chỉ ra manh mối tiếp theo. Danh sách liên kết hoạt động giống như vậy:

• Mỗi Node là một mảnh giấy. Nó chứa một dữ liệu (vị trí của kho báu) và một con trỏ đến manh mối tiếp theo.
• Head là manh mối đầu tiên, điểm khởi đầu của cuộc săn.
• Tail là một ghi chú đặc biệt bạn giữ trong túi, luôn cho bạn biết vị trí của manh mối cuối cùng.

Cấu trúc này cho phép chúng ta thêm hoặc xóa các phần tử một cách rất hiệu quả, như chúng ta sẽ thấy ở phần dưới.

Triển khai Danh Sách Liên Kết

Mã cho danh sách liên kết được chia thành hai phần: Lớp Node và Lớp LinkedList.

i. Lớp Node

Đây là bản thiết kế cho mỗi phần tử trong danh sách. Nó rất đơn giản.

class Node {
  constructor(value) {
    this.value = value; // Dữ liệu cho node này
    this.next = null;   // Con trỏ đến node tiếp theo trong danh sách
  }
}

ii. Lớp LinkedList

Lớp này quản lý toàn bộ danh sách. Nó theo dõi head (node đầu tiên) và tail (node cuối cùng). Tail là chìa khóa để thực hiện các thao tác nhanh.

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null; // Thêm con trỏ tail ở đây
  }

Phương thức append: Phép màu của O(1)

Phương thức append thêm một node mới vào cuối danh sách của chúng ta. Đây là nơi con trỏ tail tỏa sáng, làm cho quá trình này trở nên cực kỳ nhanh chóng.

• Không có con trỏ tail: Để thêm một manh mối mới, bạn sẽ phải theo dõi từng manh mối từ đầu đến cuối để tìm ra manh mối cuối cùng. Nếu cuộc săn của bạn có 100 manh mối, bạn sẽ phải thực hiện 100 bước. Đây là quá trình chậm và chúng ta gọi là O(n).

• Có con trỏ tail: Bạn chỉ cần nhìn vào ghi chú "manh mối cuối" (this.tail), liên kết manh mối mới với nó, và sau đó cập nhật ghi chú của bạn để chỉ đến manh mối mới. Đây luôn là một quá trình nhanh chóng, chỉ với hai bước, bất kể danh sách dài bao nhiêu. Chúng ta gọi điều này là O(1).

  // Thêm node vào cuối trong thời gian O(1)
  append(value) {
    const newNode = new Node(value);

    // Nếu danh sách rỗng, node mới là cả đầu và cuối
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }

    // Ngược lại, liên kết tail hiện tại với node mới
    this.tail.next = newNode;
    // Sau đó, làm cho node mới trở thành tail mới
    this.tail = newNode;
  }

Phương thức print

Phương thức này cho phép chúng ta xem tất cả các node trong danh sách bằng cách duyệt từ head.

  // In tất cả các node 
  print() {
    const values = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    return values.join(" -> ");
  }
}

Ví dụ Sử Dụng
Đây là cách chúng ta sẽ sử dụng danh sách liên kết hiệu quả mới của mình.

const list = new LinkedList();
list.append("Manh mối đầu tiên");
list.append("Manh mối thứ hai");
list.append("Manh mối thứ ba");
console.log(list.print()); // Manh mối đầu tiên -> Manh mối thứ hai -> Manh mối thứ ba

🎮 Thử Nghiệm Ngay

Dưới đây là một trang chơi trực tiếp nơi bạn có thể:

• Thêm các node
• Xem danh sách liên kết một cách trực quan dưới dạng chuỗi các hộp
• Thấy mỗi node liên kết với node tiếp theo, tất cả từ một điểm khởi đầu duy nhất.

👉 Demo Danh Sách Liên Kết Trực Quan trên CodePen

🙋🏽‍♀️ Đến lượt bạn!

• Thử chèn một node tại một vị trí cụ thể
• Thử xóa một node
• Thực nghiệm với định dạng trực quan để làm cho các mũi tên trở nên động hơn

Hãy cho tôi biết nếu bạn thực hiện thử thách! Tôi muốn xem sản phẩm của bạn! Kết nối với tôi trên GitHub.

Bạn thấy hướng dẫn này có hữu ích không? Có câu hỏi nào không? Hoặc có bất kỳ góc nhìn nào giúp tôi viết hướng dẫn tốt hơn không? Hãy cho tôi biết trong phần bình luận 💬!

Đến đây là hết bài hướng dẫn mini giữa tuần hôm nay!

Tôi sẽ giữ cho mọi thứ nhẹ nhàng, vui vẻ và hữu ích; từng dự án nhỏ một.

Nếu bạn thích bài viết này, hãy để lại một 💬 hoặc 🧡 để cho tôi biết nhé.

Và nếu bạn có một ý tưởng cho điều gì đó bạn muốn tôi thử vào thứ Tư tới, hãy để lại trong phần bình luận. 👇

Theo dõi tôi để xem nhiều hướng dẫn ngắn gọn và dễ hiểu như thế này :)

Nếu bạn muốn biết tôi đang làm gì, hãy xem Portfolio của tôi.

:-)

Theo dõi tôi trên LinkedIn
hoặc trên X (Twitter)

✍🏾 Tôi đang ghi lại quá trình học tập của mình mỗi thứ Tư. Hãy theo dõi nếu bạn cũng đang học JavaScript!
Hãy cùng nhau học hỏi nhé!

Hẹn gặp lại vào thứ Tư tới, hy vọng không phải thứ Sáu😑 🚀