Triển khai danh sách được liên kết trong JavaScript

Danh sách được liên kết là một cấu trúc dữ liệu rất giống với một mảng, ngoại trừ thực tế là dữ liệu không được lưu trữ trong một vị trí bộ nhớ. Trong JavaScript, mỗi phần tử (nút) của danh sách được liên kết là một đối tượng trỏ đến phần tử (nút) tiếp theo, phần tử này cũng trỏ đến phần tử tiếp theo của danh sách được liên kết, cho đến khi phần tử cuối cùng trỏ đến không (cuối danh sách được liên kết) .

Điểm vào danh sách liên kết được gọi là phần đầu. Đầu là tham chiếu đến nút đầu tiên trong danh sách liên kết. Nút cuối cùng trong danh sách trỏ đến null. Nếu một danh sách trống, phần đầu là một tham chiếu null.

Bằng hình ảnh, danh sách liên kết xem tốt nhất của nó như sau;

Điều này cũng có thể được xem như;

// Skeletal View of a Linked List

const list = {
  head: {
    data: 12,
    next: {
      data: 99,
      next: {
        data: 37,
        next: null
      }
    }
  }
}

//  Joshua Ajagbe

1. Trình phát nhạc — Các bài hát trong trình phát nhạc được liên kết với các bài hát trước đó và tiếp theo. Vì vậy, bạn có thể phát các bài hát từ đầu hoặc cuối danh sách.
2. Trình xem hình ảnh — Các hình ảnh trước đó và tiếp theo được liên kết và có thể được truy cập bằng các nút tiếp theo và trước đó.
3. Trang trước và trang tiếp theo trong trình duyệt web — Chúng tôi có thể truy cập URL trước đó và trang tiếp theo được tìm kiếm trong trình duyệt web bằng cách nhấn các nút quay lại và tiếp theo vì chúng được liên kết dưới dạng danh sách được liên kết.

Có ba loại danh sách liên kết chính, đó là Danh sách liên kết đơn, Danh sách liên kết kép và Danh sách liên kết vòng. Với mục đích của bài học này, chúng ta sẽ triển khai Danh sách liên kết đơn.

Như đã nêu trước đó, một danh sách được liên kết chỉ đơn giản là sự kết hợp của các phần tử (nút) trỏ đến nhau. Đơn vị cơ bản của danh sách liên kết là một nút. Một nút chứa dữ liệu và con trỏ tới nút tiếp theo, được thực hiện như sau;

// A Singly Linked List Node
function SinglyLinkedListNode(data) {
  this.data = data;
  this.next = null; // the pointer to the next node...
}

//  Joshua Ajagbe

function SinglyLinkedList() {
  this.head = null;
  this.size = 0; // this helps keep track of the size of the linked list.
}

SinglyLinkedList.prototype.insert = function (data) {
  // checking if linked list is empty
  if(this.head === null){
    this.head = new SinglyLinkedListNode(data);
  } else {
    let temp = this.head;
    this.head = new SinglyLinkedListNode(data);
    this.head.next = temp;
  }
  this.size++; // updating the linked list size.
}

// Let's add method to check if the linked list is empty here. Bonus 
SinglyLinkedList.prototype.isEmpty = function () {
  return this.size === 0;
}

//  Joshua Ajagbe

Việc loại bỏ một nút khỏi danh sách liên kết được thực hiện bằng cách loại bỏ con trỏ của nó. Điều này có nghĩa là nút trước trỏ đến nút (cần xóa) sẽ được thực hiện để bỏ qua nút (cần xóa), do đó trỏ đến nút tiếp theo.

SinglyLinkedList.prototype.remove = function (data) {
  let currentHead = this.head;
  if(currentHead.data === data) {
    this.head = currentHead.next;
    this.size--;
  } else {
    let prev = currentHead;
    while(currentHead.next) {
      if(currentHead.data === data){
        prev.next = currentHead.next;
        prev = currentHead;
        currentHead = currentHead.next
        this.size--;
        break;
      }
      prev = currentHead;
      currentHead = currentHead.next;
    }
  }
}


//  Joshua Ajagbe

Tôi hy vọng điều này đã giúp bạn hiểu được Danh sách được liên kết và cách triển khai danh sách này.

Trong trường hợp bạn muốn được giải thích thêm, bạn có thể liên hệ với tôi trên LinkedIn:https://www.linkedin.com/in/joshua-ajagbe/hoặc gửi email cho tôi theo địa chỉ [email protected].

Học vui vẻ