Code danh sách liên kết đôi
Cấu trúc dữ liệu và giải thuật: Danh sách liên kết đôi (Doubly Linked List)
Ở bài viết trước, Cấu trúc dữ liệu và giải thuật: Danh sách liên kết đơn (Singly Linked List). Mình đã giới thiệu về danh sách liên kết, và 'biến thể' của cấu trúc dữ liệu này. Trong bài viết này, mình sẽ hướng dẫn cách cài đặt thuật toán cho danh sách liên kết đôi (Doubly Linked List). Mình sẽ giới thiệu lại một chút danh sách liên kết đôi:
1. Setup
2. Doubly Linked List Insertion Cũng giống như danh sách sách liên kết đơn, đối với danh sách liên kết đôi, chèn 1 node vào trong list, cũng có 3 loại:
Chèn vào vị trí đầu của danh sách Để chèn 1 node vào vị trí đầu của danh sách, cần làm 2 bước sau:
Cụ thể, thuật toán sẽ như sau: insertAtHead(data) { const node = new Node(data, null, this.head); if (this.head) { this.head.prev = node; } this.head = node; this.length ++; return; }Chèn vào vị trí cuối của danh sách Để chèn 1 node vào vị trí cuối của danh sách, cần làm 3 bước sau:
Cụ thể, thuật toán như sau: insertAtTail(data) { if (!this.head) { return this.insertAtHead(data); } const prevNode = this.getNodeAtIndex(this.length - 1); const node = new Node(data, prevNode, null); prevNode.next = node; this.length ++; return; }Chèn vào vị trí bất kỳ trong danh sách Để chèn 1 node vào vị trí bất kỳ trong danh sách, cần làm 3 bước sau:
Cụ thể, thuật toán sẽ như sau: insertAtIndex(data, index) { if (index === 0) { return this.insertAtHead(data); } if (index === this.length) { return this.insertAtTail(data); } const prevNode = this.getNodeAtIndex(index - 1); const node = new Node(data, prevNode, prevNode.next); prevNode.next.prev = node; prevNode.next = node; this.length ++; return; }3. Doubly Linked List Deletion Cũng tương tự như chèn, thì xóa 1 node trong list cũng có 3 loại:
Xóa ở vị trí đầu của danh sách Để xóa head node, mình làm 2 bước sau:
Cụ thể, thuật toán sẽ như sau: Xóa ở vị trí cuối của danh sách Để xóa tail node, mình làm 2 bước sau:
Thuật toán sẽ như sau: deleteAtTail() { if (this.length === 1) { return this.deleteAtHead(); } const prevNode = this.getNodeAtIndex(this.length - 2); prevNode.next = null; this.length --; return; }Xóa ở vị trí bất kỳ trong danh sách Để xóa 1 node, ở vị trí bất kỳ. Mình làm như sau:
Thuât toán như sau: deleteAtIndex(index) { if (index < 0 || index >= this.length) { return null; } if (index === 0) { return this.deleteAtHead(); } if (index === this.length - 1) { return this.deleteAtTail(); } const nodeToBeDeleted = this.getNodeAtIndex(index); nodeToBeDeleted.prev.next = nodeToBeDeleted.next; nodeToBeDeleted.next.prev = nodeToBeDeleted.prev; this.length --; return; }4. Lời kết Hy vọng với bài viết này, sẽ giúp các bạn có cái nhìn tổng quan về danh sach liên kết đơn, và các thuật toán xung quanh. Happy Coding!!! |