Duyệt qua danh sách liên kết trong JavaScript

Trong các cuộc phỏng vấn, nhà tuyển dụng họ thường hỏi những câu mà bạn cảm thấy nó phức tạp, nhưng thực chất vô cùng đơn giản. Với nhà tuyển dụng X tại công ty ABC đã đưa ra câu hỏi Làm thế nào để duyệt qua cấu trúc dữ liệu của danh sách liên kết?.

Cấu trúc dữ liệu danh sách liên kết

Ta có một danh sách liên kết sau:


5 -> 3 -> 10

Trong JavaScript, danh sách liên kết ở dạng đối tượng (object) có giá trị (value) và chúng tham chiếu tới hàng kế tiếp trong danh sách. Với danh sách liên kết 5 -> 3 -> 10:


const linkedList = {
  val: 5,
  next: {
    val: 3,
    next: {
      val: 10,
      next: null,
    },
  },
};

Làm sao để Traverse?

Trước hết để làm điều đó, bạn cần phải duyệt qua danh sách này và đặt các giá trị của chúng vào trong một mảng


[5, 3, 10]

Từ cấu trúc dữ liệu, bạn có thể thấy rằng, nếu next có một giá trị thì có nhiều phần tử hơn để đi qua. Nếu next thì nó sẽ trả về null. Khi đó chương trình sẽ kết thúc.

Tạo một mảng rỗng và sử dụng vòng lặp while để theo dõi cấu trúc


const arr = [];
let head = linkedList;

while (head !== null) {
  arr.push(head.val);
  head = head.next;
}

console.log(arr);
// [5, 3, 10]

Cách thức hoạt động

Ở đây, mỗi lần lặp của vòng lặp while, biến head sẽ trỏ đến một đối tượng trong danh sách liên kết.


const linkedList = {
  // head @ Lặp 1
  val: 5,
  next: {
    // head @ Lặp 2
    val: 3,
    next: {
      // head @ Lặp 3
      val: 10,
      next: null,
    },
  },
};

Ở đây, mỗi vòng lặp chúng ta đẩy val đến arr và tiếp tục. Nếu tiếp đến vòng lặp là null, khi đó chương trình sẽ kết thúc.

Tác giả: Jos Hoàng Tiên