Giới thiệu về danh sách được liên kết qua JavaScript - Phần 2: Triển khai

Quay lại Phần 1, ta đã có một cái nhìn tổng quan về danh sách được liên kết là gì và tại sao chúng cần thiết để tạo các cấu trúc dữ liệu nâng cao hơn. Bây giờ ta có thể tìm hiểu cách bắt đầu triển khai danh sách liên kết kép đầy đủ tính năng trong JavaScript.

Các danh sách được liên kết đơn lẻ và triển khai trong các cấu trúc dữ liệu khác thường sẽ chỉ là các version đơn giản hơn của những gì ta sẽ đề cập ở đây, vì vậy điều này sẽ tốt nếu đánh dấu trang làm tài liệu tham khảo chung.

Kết cấu

Giống như bất kỳ lớp nào khác, ta có thể lưu trữ bất cứ thứ gì ta muốn trong mỗi nút, phần quan trọng duy nhất là các con trỏ next và con trỏ prev đó, theo mặc định sẽ là null .

Tương tự như vậy, những thứ duy nhất mà danh sách của ta cần là tail , head và length . Ta cần thao tác thủ công độ dài vì, không giống như mảng, nó sẽ không được tính toán cho ta và cần thiết để tìm kiếm các mục.

class Node {   constructor(val) {     this.val = val;     this.next = null;     this.prev = null;   }; };  class linkedList {   constructor() {     this.head = null;     this.tail = null;     this.length = 0;   }; };

Tạo nên

Bây giờ ta có thể bắt đầu cài đặt tất cả các phương thức bên trong lớp linkedList của ta . Vì ta không có bất kỳ tính năng bình thường nào như push hoặc shift ta sẽ phải tạo các version của riêng mình.

Đầu và đuôi

Hầu hết các hoạt động của ta dựa nhiều hơn vào việc thao tác các con trỏ trong các node xung quanh hơn là vào mục ta muốn thay đổi. Để thêm thứ gì đó không chỉ là đẩy một nút mới vào nơi ta muốn, như với một mảng, mà là thay đổi con trỏ trên các mục trước hoặc sau để trỏ đến mục mới của ta , sau đó tăng độ dài của danh sách theo cách thủ công.

Nếu chưa có gì trong danh sách, ta muốn đặt mục mới làm cả phần đầu và phần đuôi, vì đó là mục duy nhất. Để thêm hoặc xóa khỏi cuối danh sách, ta sẽ lấy phần đầu / đuôi hiện tại mà ta muốn thay thế và đặt con trỏ của nó thành mục mới hoặc null, thay đổi đầu / đuôi của danh sách thành nút mới hoặc null, sau đó tăng chiều dài.

addHead(val) {   let newNode = new Node(val);    if (!this.head) {     this.head = newNode;     this.tail = this.head;   };    this.head.prev = newNode;   newNode.next = this.head;   this.head = newNode;    this.length++;   return this; }  addTail(val) {   let newNode = new Node(val);    if (!this.head) {     this.head = newNode;     this.tail = newNode;   };    this.tail.next = newNode;   newNode.prev = this.tail;   this.tail = newNode;    this.length++;   return this; }  removeHead() {   let removed = this.head;   if (!this.head) return undefined;    this.head = this.head.next;   this.head.prev = null;    this.length--;   return removed; }  removeTail() {   let removed = this.tail;   if (!this.tail) return undefined;    if (this.length === 1) {     this.head = null;     this.tail = null;   };    this.tail = removed.prev;   this.tail.next = null;    this.length--;   return removed; }

Tìm thấy

Vì ta không có index để lấy mục của bạn nên ta sẽ gặp một số vấn đề với việc chèn / xóa vào giữa danh sách, vì vậy ta cần chức năng tiện ích của riêng mình.

Nó rất đơn giản, ta chỉ cần để lưu trữ các mục hiện hành và sử dụng một for hay while vòng lặp để sử dụng con trỏ của ta để cập nhật current cho đến khi ta đang ở mục ta muốn.

Hoạt hình: Tìm kiếm

Graphic / Animation nhờ VisuAlgo.net

Tất nhiên, điều này mang lại cho ta O(n) thời gian tìm kiếm, nhưng vì ta đang sử dụng danh sách được liên kết kép nên ta chỉ có thể bắt đầu từ phần đuôi nếu những gì ta muốn nằm ở giữa danh sách, cho ta O(n / 2) .

find(index) {   let current   if (index < 0 || index >= this.length) return undefined;    if (index <= this.length / 2) {     current = this.head;     for (let i = 0; i < index; i++) current = current.next;   } else {     current = this.tail;     for (let i = this.length; i > index; i--) current = current.prev;   }    return current; }

Chèn và Xóa

Bây giờ ta đã có tiện ích nhỏ của bạn , ta có thể sử dụng nó để tìm mục trong index mà ta muốn, sau đó đặt các con trỏ trên đó và mục trước và sau nó vào nút mới của ta , do đó "ghép" nó vào vị trí.

Hoạt ảnh: chèn

Graphic / Animation nhờ VisuAlgo.net

Nếu index nằm ở phần đầu hoặc phần đuôi, ta có thể sử dụng lại các phương pháp trước đó của bạn .

insert(val, index) {   if (index < 0 || index > this.length) return null;   if (index === this.length) return this.addTail(val);   if (index === 0) return this.addHead(val);    let prev = this.find(index - 1),       newNode = new Node(val),       temp = prev.next;    prev.next = newNode;   newNode.next = temp;   newNode.prev = prev;    this.length++;   return true; }

Xóa rõ ràng chỉ là nghịch đảo của việc chèn và đơn giản hơn một chút. Tìm nút mà ta muốn loại bỏ và đặt các con trỏ trên các node xung quanh với nhau, không để lại gì tham chiếu đến nút đã loại bỏ.

Hoạt ảnh: loại bỏ

Graphic / Animation nhờ VisuAlgo.net

remove(index) {   if (index < 0 || index >= this.length) return null;   if (index === this.length) return this.removeTail();   if (index === 0) return this.removeHead();    let removed = this.find(index);    removed.prev.next = removed.next;   removed.next.prev = removed.prev;    this.length--;   return removed; }

Cập nhật

Cái này đơn giản đến mức gần như không có gì đáng nói, chỉ cần tìm món đồ và đặt lại giá trị của nó.

update(val, index) {   let node = this.find(index);   if (node) node.val = val;   return node; }

Kết luận

Mặc dù điều này có vẻ như rất nhiều công việc, nhưng bạn nên nhớ rằng trong nhiều trường hợp, bạn sẽ không cần tất cả.

Tôi thực sự khuyên bạn nên xem Buckets.js khi bạn không muốn tạo một cái thủ công, mặc dù luôn luôn tốt để hiểu khái niệm này ở mức độ sâu hơn.

Tags:

Các tin liên quan