Code danh sách liên kết đôi

Ở 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:

• Danh sách liên kết đôi [Doubly Linked List]: Mỗi node trong danh sách liên kết đôi gồm có previous pointer, data và next pointer, previous pointer trỏ tới phần tử đứng trước, next pointer trỏ tới phần tử phía sau. Nếu previous pointer trỏ tới NULL thì có nghĩa node đó là node đứng đầu tiên trong danh sách liên kết đơn. Và tương tự với danh sách liên kết, next pointer trỏ tới NULL thì đó là node cuối trong danh sách liên kết đơn.

• Không giống như danh sách liên kết đơn, xóa 1 node trong list cần biết node đứng trước nó. Thì trong danh sách liên kết đôi, có thể xóa 1 node trong list mà không cần dựa vào node đứng trước nó mà chỉ cần dựa vào node đứng sau nó.
• Với mỗi node, có thêm một con trỏ previous pointer dẫn tới sẽ cần thêm bộ nhớ.
• Thêm hoặc xóa 1 node trong danh sách liên kết đôi, sẽ lâu hơn 1 chút so với danh sách liên kết đơn.

1. Setup

• Các bạn có thể clone source code thuật toán tại đây: //github.com/DucLS/Data-structure-algorithm/tree/main/linked-list

• Vẫn như thường lệ, mình sẽ khởi tạo với một class Node như sau:

class Node { constructor[value, prev, next] { this.value = value; this.prev = prev; this.next = next; } }

• Và khởi tạo thêm một class DoublyLinkedList:

class DoublyLinkedList { constructor[] { this.head = null; this.length = 0; } }

• Khởi tạo một method, có tác dụng lấy node ở vị trí bất kỳ trong danh sách:

getNodeAtIndex[index] { if [index < 0 || index >= this.length] { return null; } if [index == 0] { return this.head; } let currentNode = this.head; for [let i = 1; i = 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!!!