Cấu trúc dữ liệu và giải thuật: Danh sách liên kết đôi (Doubly Linked List)

Trong bài viết này, chúng ta sẽ tìm hiểu về cấu trúc dữ liệu danh sách liên kết đôi và cách cài đặt thuật toán cho nó.

Giới thiệu về danh sách liên kết đôi

Danh sách liên kết đôi (Doubly Linked List) là một cấu trúc dữ liệu mà mỗi node trong danh sách chứa thông tin về dữ liệu, con trỏ trỏ tới node trước đó và con trỏ trỏ tới node sau đó. Nếu con trỏ trỏ tới NULL, tức là node đó là node đầu tiên trong danh sách, và nếu con trỏ trỏ tới NULL thì node đó là node cuối cùng trong danh sách.

Khác với danh sách liên kết đơn, trong danh sách liên kết đôi, ta có thể xóa một node trong danh sách 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ó. Điều này giúp cho việc xóa node trong danh sách liên kết đôi trở nên dễ dàng hơn.

Cài đặt thuật toán danh sách liên kết đôi

Chuẩn bị

Trước khi bắt đầu, chúng ta cần chuẩn bị một số phần tử cơ bản để cài đặt thuật toán danh sách liên kết đôi.

Đầu tiên, ta sẽ tạo một class Node để đại diện cho một node trong danh sách liên kết đôi:

class Node {   constructor(value, prev, next) {     this.value = value;     this.prev = prev;     this.next = next;   } }

Tiếp theo, ta khởi tạo một class DoublyLinkedList để thao tác với danh sách liên kết đôi:

class DoublyLinkedList {   constructor() {     this.head = null;     this.length = 0;   } }

Lấy node ở vị trí bất kỳ trong danh sách

Ta có thể lấy một node ở vị trí bất kỳ trong danh sách bằng cách sử dụng method getNodeAtIndex(index):

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 <= index; i++) {     if (currentNode) {       currentNode = currentNode.next;     }   }    return currentNode; }

Chèn node vào danh sách liên kết đôi

Để chèn một node vào danh sách liên kết đôi, ta có 3 trường hợp sau:

1. Chèn vào vị trí đầu của danh sách.
2. Chèn vào vị trí cuối của danh sách.
3. Chèn vào vị trí bất kỳ trong danh sách.

Chèn vào vị trí đầu

Để chèn một node vào vị trí đầu của danh sách, ta thực hiện các bước sau:

1. Tạo một node mới, với con trỏ prev trỏ tới NULL và con trỏ next trỏ tới head node hiện tại.
2. Cập nhật con trỏ prev của head node hiện tại để trỏ tới node mới và cập nhật head node thành node mới.

insertAtHead(data) {   const node = new Node(data, null, this.head);    if (this.head) {     this.head.prev = node;   }    this.head = node;   this.length++; }

Chèn vào vị trí cuối

Để chèn một node vào vị trí cuối của danh sách, ta thực hiện các bước sau:

1. Lấy node cuối cùng của danh sách.
2. Tạo một node mới, với con trỏ prev trỏ tới node cuối cùng, con trỏ next trỏ tới NULL.
3. Cập nhật con trỏ next của node cuối cùng hiện tại để trỏ tới node mới và cập nhật node cuối cùng thành node mới.

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++; }

Chèn vào vị trí bất kỳ

Để chèn một node vào vị trí bất kỳ trong danh sách, ta thực hiện các bước sau:

1. Lấy node ở vị trí trước vị trí cần chèn, gọi là prevNode, và node sau vị trí cần chèn, gọi là nextNode.
2. Tạo một node mới, với con trỏ prev trỏ tới prevNode, con trỏ next trỏ tới nextNode.
3. Cập nhật con trỏ next của prevNode và con trỏ prev của nextNode để trỏ tới node mới.

insertAtIndex(data, index) {   if (index < 0 || index >= this.length) {     return null;   }    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++; }

Xóa node trong danh sách liên kết đôi

Để xóa một node trong danh sách liên kết đôi, ta cũng có 3 trường hợp tương tự như chèn:

1. Xóa ở vị trí đầu của danh sách.
2. Xóa ở vị trí cuối của danh sách.
3. Xóa ở vị trí bất kỳ trong danh sách.

Xóa ở vị trí đầu

Để xóa head node, ta thực hiện các bước sau:

1. Lấy nextNode của head node.
2. Cập nhật con trỏ prev của nextNode để trỏ tới NULL và cập nhật head node thành nextNode.

deleteAtHead() {   if (this.length === 1) {     this.head = null;     this.length = 0;     return;   }    const nextNode = this.head.next;   nextNode.prev = null;   this.head = nextNode;   this.length--; }

Xóa ở vị trí cuối

Để xóa tail node, ta thực hiện các bước sau:

1. Lấy node ở vị trí kế cuối, gọi là prevNode.
2. Cập nhật con trỏ next của prevNode thành NULL.

deleteAtTail() {   if (this.length === 1) {     return this.deleteAtHead();   }    const prevNode = this.getNodeAtIndex(this.length - 2);   prevNode.next = null;   this.length--; }

Xóa ở vị trí bất kỳ

Để xóa một node ở vị trí bất kỳ trong danh sách, ta thực hiện các bước sau:

1. Lấy node ở vị trí cần xóa, node đứng trước gọi là prevNode, node đứng sau gọi là nextNode.
2. Cập nhật con trỏ next của prevNode để trỏ tới nextNode và cập nhật con trỏ prev của nextNode để trỏ tới prevNode.

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--; }

Kết luận

Với bài viết này, chúng ta đã có cái nhìn tổng quan về danh sách liên kết đôi và cách cài đặt thuật toán cho nó. Hy vọng bài viết sẽ giúp bạn hiểu rõ hơn về cấu trúc dữ liệu này và áp dụng vào việc lập trình. Happy Coding!