Danh sách liên kết đôi: Cấu trúc và Cài đặt Chi tiết

Trong thế giới khoa học máy tính và lập trình, cấu trúc dữ liệu đóng vai trò nền tảng, quyết định hiệu quả của việc lưu trữ và truy xuất thông tin. Sau khi tìm hiểu về Danh sách liên kết đơn (Singly Linked List), chúng ta sẽ cùng khám phá một biến thể mạnh mẽ và linh hoạt hơn: Danh Sách Liên Kết đôi (Doubly Linked List). Cấu trúc này khắc phục một số hạn chế của danh sách liên kết đơn, cho phép duyệt dữ liệu theo cả hai chiều và thực hiện một số thao tác xóa hiệu quả hơn. Mặc dù yêu cầu thêm một chút bộ nhớ cho con trỏ ngược, sự linh hoạt mà danh sách liên kết đôi mang lại khiến nó trở thành lựa chọn tối ưu trong nhiều ứng dụng thực tế, từ việc quản lý lịch sử duyệt web đến các chức năng hoàn tác (undo/redo) trong phần mềm. Bài viết này sẽ đi sâu vào khái niệm, ưu nhược điểm và hướng dẫn chi tiết cách cài đặt các thao tác cơ bản trên danh sách liên kết đôi, giúp bạn nắm vững và ứng dụng cấu trúc dữ liệu quan trọng này.

Danh sách liên kết đôi là gì?

Nội dung

1 Danh sách liên kết đôi là gì?
2 Ưu điểm và Nhược điểm của Danh sách liên kết đôi
3 Cài đặt Danh sách liên kết đôi
4 Ứng dụng của Danh sách liên kết đôi
5 Kết luận
- 5.1 Chia sẻ:

Danh sách liên kết đôi (Doubly Linked List) là một cấu trúc dữ liệu tuyến tính, tương tự như danh sách liên kết đơn, nhưng với một điểm khác biệt quan trọng: mỗi nút (node) trong danh sách không chỉ chứa dữ liệu và một con trỏ (next) đến nút kế tiếp, mà còn chứa thêm một con trỏ (prev – previous) trỏ đến nút đứng trước nó.

Cụ thể, mỗi nút trong danh sách liên kết đôi bao gồm ba thành phần:

Data (Dữ liệu): Lưu trữ thông tin của nút.
Next Pointer (Con trỏ tới): Trỏ đến địa chỉ bộ nhớ của nút tiếp theo trong danh sách. Nếu nút là nút cuối cùng (tail), con trỏ next sẽ trỏ tới NULL.
Previous Pointer (Con trỏ lui): Trỏ đến địa chỉ bộ nhớ của nút đứng trước nó trong danh sách. Nếu nút là nút đầu tiên (head), con trỏ prev sẽ trỏ tới NULL.

Mô tả cấu trúc node và liên kết trong danh sách liên kết đôi

Sự tồn tại của con trỏ prev mang lại khả năng duyệt danh sách theo cả hai chiều: từ đầu đến cuối (forward traversal) và từ cuối về đầu (backward traversal). Điều này tạo ra sự khác biệt lớn so với danh sách liên kết đơn, vốn chỉ cho phép duyệt theo một chiều.

Ưu điểm và Nhược điểm của Danh sách liên kết đôi

So với danh sách liên kết đơn và mảng (Array), danh sách liên kết đôi có những ưu và nhược điểm riêng:

Ưu điểm:

Duyệt hai chiều: Có thể duyệt danh sách từ đầu đến cuối và ngược lại một cách dễ dàng nhờ con trỏ prev và next.
Xóa nút hiệu quả hơn: Việc xóa một nút trở nên đơn giản hơn vì có thể dễ dàng truy cập nút đứng trước (prev) và nút đứng sau (next) của nút cần xóa để cập nhật lại các liên kết. Trong danh sách liên kết đơn, để xóa một nút, bạn thường cần tham chiếu đến nút đứng trước nó, việc này đôi khi phức tạp hơn. Với danh sách liên kết đôi, bạn có thể xóa một nút chỉ cần biết chính nút đó (hoặc nút sau nó).
Chèn linh hoạt: Việc chèn một nút vào trước hoặc sau một nút đã biết cũng thuận tiện hơn.

Nhược điểm:

Tốn bộ nhớ hơn: Mỗi nút cần thêm không gian để lưu trữ con trỏ prev, làm tăng tổng dung lượng bộ nhớ yêu cầu so với danh sách liên kết đơn.
Thao tác phức tạp hơn: Các thao tác chèn và xóa đòi hỏi phải cập nhật nhiều con trỏ hơn (cả next và prev), làm cho việc triển khai mã nguồn phức tạp hơn một chút và có thể tốn thêm một chút thời gian xử lý so với danh sách liên kết đơn.

Cài đặt Danh sách liên kết đôi

Chúng ta sẽ tiến hành cài đặt danh sách liên kết đôi bằng cách định nghĩa lớp Node và lớp DoublyLinkedList.

Thiết lập ban đầu

Lớp Node: Đại diện cho một phần tử trong danh sách. Mỗi node chứa giá trị (value), con trỏ tới nút phía trước (prev), và con trỏ tới nút phía sau (next).

class Node {
  constructor(value, prev = null, next = null) { // Thêm giá trị mặc định là null
    this.value = value;
    this.prev = prev;
    this.next = next;
  }
}

Lớp DoublyLinkedList: Quản lý toàn bộ danh sách. Nó chứa con trỏ đến nút đầu tiên (head), con trỏ đến nút cuối cùng (tail – để tối ưu hóa thao tác cuối danh sách), và độ dài (length) của danh sách.

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null; // Thêm con trỏ tail
    this.length = 0;
  }
}

Phương thức phụ trợ getNodeAtIndex: Lấy nút ở một vị trí (index) cụ thể. Phương thức này hữu ích cho các thao tác chèn/xóa tại vị trí bất kỳ.

  // Thêm phương thức này vào trong class DoublyLinkedList
  getNodeAtIndex(index) {
    // Kiểm tra chỉ số không hợp lệ
    if (index < 0 || index >= this.length) {
      return null; // Hoặc ném lỗi tùy theo thiết kế
    }
    // Tối ưu: Duyệt từ đầu nếu index gần đầu, duyệt từ cuối nếu index gần cuối
    let currentNode;
    if (index < this.length / 2) {
        currentNode = this.head;
        for (let i = 0; i < index; i++) {
             currentNode = currentNode.next;
        }
    } else {
        currentNode = this.tail;
        for (let i = this.length - 1; i > index; i--) {
            currentNode = currentNode.prev;
        }
    }
    return currentNode;
  }

Các thao tác chèn (Insertion Operations)

Giống như danh sách liên kết đơn, chúng ta có ba trường hợp chèn chính:

1. Chèn vào đầu danh sách (insertAtHead)

Ý tưởng: Tạo nút mới. prev của nút mới là null. next của nút mới trỏ tới head cũ. prev của head cũ (nếu có) trỏ tới nút mới. Cập nhật head thành nút mới. Nếu danh sách rỗng, cập nhật cả tail.
Các bước:
1. Tạo một Node mới với value được cung cấp, prev là null, và next trỏ tới this.head hiện tại.
2. Nếu danh sách không rỗng (this.head tồn tại), cập nhật con trỏ prev của head cũ để trỏ tới nút mới.
3. Cập nhật this.head để trỏ tới nút mới.
4. Nếu danh sách ban đầu rỗng (this.length === 0), cập nhật this.tail cũng trỏ tới nút mới.
5. Tăng this.length.
Mã nguồn:

  // Thêm phương thức này vào trong class DoublyLinkedList
  insertAtHead(data) {
    const newNode = new Node(data, null, this.head);
    if (this.head) {
      // Nếu danh sách không rỗng, cập nhật prev của head cũ
      this.head.prev = newNode;
    } else {
      // Nếu danh sách rỗng, tail cũng là node mới
      this.tail = newNode;
    }
    this.head = newNode; // Cập nhật head
    this.length++;
    // return this; // Có thể trả về danh sách để chaining
  }

2. Chèn vào cuối danh sách (insertAtTail)

Ý tưởng: Tạo nút mới. next của nút mới là null. prev của nút mới trỏ tới tail cũ. next của tail cũ (nếu có) trỏ tới nút mới. Cập nhật tail thành nút mới. Nếu danh sách rỗng, gọi insertAtHead.
Các bước:
1. Nếu danh sách rỗng (!this.head), gọi insertAtHead(data) và kết thúc.
2. Tạo một Node mới với value được cung cấp, prev trỏ tới this.tail hiện tại, và next là null.
3. Cập nhật con trỏ next của tail cũ (this.tail) để trỏ tới nút mới.
4. Cập nhật this.tail để trỏ tới nút mới.
5. Tăng this.length.
Mã nguồn:

  // Thêm phương thức này vào trong class DoublyLinkedList
  insertAtTail(data) {
    if (!this.head) {
      return this.insertAtHead(data); // Xử lý trường hợp danh sách rỗng
    }
    const newNode = new Node(data, this.tail, null);
    this.tail.next = newNode; // Cập nhật next của tail cũ
    this.tail = newNode; // Cập nhật tail
    this.length++;
    // return this;
  }

3. Chèn vào vị trí bất kỳ (insertAtIndex)

Chèn node vào vị trí bất kỳ trong danh sách liên kết đôi

Ý tưởng: Tìm nút đứng trước (prevNode) và nút đứng sau (nextNode) vị trí cần chèn. Tạo nút mới. Cập nhật các con trỏ next và prev của prevNode, nextNode, và nút mới để liên kết chúng lại với nhau. Xử lý các trường hợp đặc biệt (chèn vào đầu, cuối, hoặc chỉ số không hợp lệ).
Các bước:
1. Kiểm tra chỉ số index:
  - Nếu index < 0 hoặc index > this.length: Không hợp lệ (có thể ném lỗi hoặc không làm gì).
  - Nếu index === 0: Gọi insertAtHead(data).
  - Nếu index === this.length: Gọi insertAtTail(data).
2. Lấy nút tại vị trí index - 1 (gọi là prevNode) bằng getNodeAtIndex(index - 1).
3. Lấy nút tại vị trí index (gọi là nextNode, đây là nút prevNode.next).
4. Tạo một Node mới (newNode) với value là data, prev trỏ tới prevNode, next trỏ tới nextNode.
5. Cập nhật prevNode.next để trỏ tới newNode.
6. Cập nhật nextNode.prev để trỏ tới newNode.
7. Tăng this.length.
Mã nguồn:

  // Thêm phương thức này vào trong class DoublyLinkedList
  insertAtIndex(data, index) {
    if (index < 0 || index > this.length) {
      // Xử lý chỉ số không hợp lệ (ví dụ: return null hoặc throw Error)
      console.error("Index out of bounds");
      return false; // Hoặc return null
    }
    if (index === 0) {
      return this.insertAtHead(data);
    }
    if (index === this.length) {
      return this.insertAtTail(data);
    }

    // Tìm nút đứng trước vị trí chèn (index - 1)
    const prevNode = this.getNodeAtIndex(index - 1);
    if (!prevNode) return false; // Không tìm thấy node trước đó (lỗi logic nếu index hợp lệ)

    const nextNode = prevNode.next; // Nút sẽ đứng sau nút mới
    const newNode = new Node(data, prevNode, nextNode);

    prevNode.next = newNode; // Cập nhật next của node trước
    if (nextNode) { // Cần kiểm tra vì nextNode có thể là null nếu đang chèn cuối (đã xử lý ở trên)
        nextNode.prev = newNode; // Cập nhật prev của node sau
    }

    this.length++;
    return true; // Chèn thành công
  }

Các thao tác xóa (Deletion Operations)

Tương tự như chèn, việc xóa cũng có ba trường hợp chính:

1. Xóa ở vị trí đầu danh sách (deleteAtHead)

Ý tưởng: Cập nhật head thành nút thứ hai. prev của head mới (nếu có) thành null. Xử lý trường hợp danh sách rỗng hoặc chỉ có một phần tử.
Các bước:
1. Kiểm tra danh sách rỗng (!this.head), nếu rỗng thì không làm gì.
2. Lưu lại head cũ để có thể trả về (tùy chọn).
3. Nếu danh sách chỉ có một phần tử (this.length === 1), đặt this.head và this.tail thành null.
4. Nếu có nhiều hơn một phần tử:
  - Cập nhật this.head thành this.head.next (nút thứ hai).
  - Đặt this.head.prev thành null.
5. Giảm this.length.
6. Trả về giá trị của nút đã xóa (tùy chọn).
Mã nguồn:

  // Thêm phương thức này vào trong class DoublyLinkedList
  deleteAtHead() {
    if (!this.head) {
      return null; // Danh sách rỗng
    }
    const deletedNode = this.head; // Lưu lại node bị xóa
    if (this.length === 1) {
      // Trường hợp chỉ có 1 node
      this.head = null;
      this.tail = null;
    } else {
      // Trường hợp có nhiều node
      this.head = this.head.next; // head mới là node thứ 2
      this.head.prev = null; // prev của head mới là null
      deletedNode.next = null; // Ngắt kết nối của node bị xóa (quan trọng)
    }
    this.length--;
    return deletedNode.value; // Trả về giá trị của node đã xóa
  }

2. Xóa ở vị trí cuối danh sách (deleteAtTail)

Xóa node cuối cùng trong danh sách liên kết đôi

Ý tưởng: Cập nhật tail thành nút kế cuối (tail.prev). next của tail mới thành null. Xử lý trường hợp danh sách rỗng hoặc chỉ có một phần tử.
Các bước:
1. Kiểm tra danh sách rỗng (!this.tail hoặc !this.head).
2. Nếu danh sách chỉ có một phần tử (this.length === 1), gọi deleteAtHead() và kết thúc.
3. Lưu lại tail cũ (deletedNode).
4. Cập nhật this.tail thành this.tail.prev (nút kế cuối).
5. Đặt this.tail.next thành null.
6. Ngắt kết nối prev của nút đã xóa (deletedNode.prev = null).
7. Giảm this.length.
8. Trả về giá trị của nút đã xóa (tùy chọn).
Mã nguồn:

  // Thêm phương thức này vào trong class DoublyLinkedList
  deleteAtTail() {
    if (!this.tail) { // Hoặc !this.head
      return null; // Danh sách rỗng
    }
    if (this.length === 1) {
      // Nếu chỉ có 1 node, xử lý như xóa head
      return this.deleteAtHead();
    }
    const deletedNode = this.tail; // Lưu lại tail cũ
    this.tail = this.tail.prev; // Tail mới là node kế cuối
    this.tail.next = null; // Next của tail mới là null
    deletedNode.prev = null; // Ngắt kết nối prev của node bị xóa

    this.length--;
    return deletedNode.value; // Trả về giá trị
  }

3. Xóa ở vị trí bất kỳ (deleteAtIndex)

Ý tưởng: Tìm nút cần xóa (nodeToBeDeleted). Lấy nút đứng trước (prevNode) và nút đứng sau (nextNode). Cập nhật prevNode.next trỏ tới nextNode. Cập nhật nextNode.prev trỏ tới prevNode. Xử lý các trường hợp đặc biệt (xóa đầu, cuối, chỉ số không hợp lệ).
Các bước:
1. Kiểm tra chỉ số index:
  - Nếu index < 0 hoặc index >= this.length: Không hợp lệ.
  - Nếu index === 0: Gọi deleteAtHead().
  - Nếu index === this.length - 1: Gọi deleteAtTail().
2. Lấy nút tại vị trí index cần xóa (nodeToBeDeleted) bằng getNodeAtIndex(index).
3. Lấy nút đứng trước nó: prevNode = nodeToBeDeleted.prev.
4. Lấy nút đứng sau nó: nextNode = nodeToBeDeleted.next.
5. Cập nhật con trỏ next của prevNode để trỏ tới nextNode.
6. Cập nhật con trỏ prev của nextNode để trỏ tới prevNode.
7. Ngắt kết nối của nodeToBeDeleted (nodeToBeDeleted.prev = null; nodeToBeDeleted.next = null;).
8. Giảm this.length.
9. Trả về giá trị của nút đã xóa (tùy chọn).
Mã nguồn:

  // Thêm phương thức này vào trong class DoublyLinkedList
  deleteAtIndex(index) {
    if (index < 0 || index >= this.length) {
      // Chỉ số không hợp lệ
      return null;
    }
    if (index === 0) {
      return this.deleteAtHead();
    }
    if (index === this.length - 1) {
      return this.deleteAtTail();
    }

    // Tìm node cần xóa
    const nodeToBeDeleted = this.getNodeAtIndex(index);
    if (!nodeToBeDeleted) return null; // Không tìm thấy node (không nên xảy ra nếu index hợp lệ)

    const prevNode = nodeToBeDeleted.prev;
    const nextNode = nodeToBeDeleted.next;

    // Bỏ qua nodeToBeDeleted bằng cách nối prevNode và nextNode
    if (prevNode) { // Kiểm tra phòng trường hợp lỗi logic
        prevNode.next = nextNode;
    }
     if (nextNode) { // Kiểm tra phòng trường hợp lỗi logic
        nextNode.prev = prevNode;
    }

    // Ngắt kết nối hoàn toàn node bị xóa (tùy chọn nhưng tốt cho garbage collection)
    nodeToBeDeleted.prev = null;
    nodeToBeDeleted.next = null;

    this.length--;
    return nodeToBeDeleted.value; // Trả về giá trị
  }

Ứng dụng của Danh sách liên kết đôi

Danh sách liên kết đôi được sử dụng trong nhiều tình huống thực tế nhờ khả năng duyệt hai chiều và thao tác hiệu quả:

Lịch sử trình duyệt: Các nút “Back” và “Forward” trong trình duyệt web có thể được triển khai bằng danh sách liên kết đôi, cho phép di chuyển tới lui giữa các trang đã xem.
Chức năng Undo/Redo: Trong các trình soạn thảo văn bản hoặc phần mềm đồ họa, danh sách liên kết đôi lưu trữ các trạng thái hoặc hành động, cho phép người dùng hoàn tác hoặc làm lại các thao tác.
Quản lý Tác vụ (Task Management): Trong một số hệ điều hành, danh sách các tiến trình đang chạy có thể được quản lý bằng danh sách liên kết đôi để dễ dàng thêm, xóa và duyệt qua các tiến trình.
Bộ đệm (Cache): Các thuật toán cache như LRU (Least Recently Used) thường sử dụng danh sách liên kết đôi kết hợp với hash map để quản lý các mục trong bộ đệm, cho phép truy cập nhanh và loại bỏ mục ít sử dụng nhất một cách hiệu quả.
Danh sách phát nhạc/video: Cho phép người dùng chuyển tới bài hát/video trước đó hoặc tiếp theo một cách dễ dàng.

Kết luận

Danh sách liên kết đôi là một cấu trúc dữ liệu mạnh mẽ, cung cấp sự linh hoạt trong việc duyệt và thao tác dữ liệu theo cả hai chiều. Mặc dù tốn thêm bộ nhớ cho con trỏ prev và các thao tác có phần phức tạp hơn so với danh sách liên kết đơn, những ưu điểm về khả năng duyệt hai chiều và xóa nút hiệu quả làm cho nó trở thành công cụ hữu ích trong nhiều bài toán lập trình và ứng dụng thực tế.

Việc hiểu rõ cách thức hoạt động và cài đặt các thao tác cơ bản như chèn (đầu, cuối, vị trí bất kỳ) và xóa (đầu, cuối, vị trí bất kỳ) trên danh sách liên kết đôi là nền tảng quan trọng cho bất kỳ lập trình viên nào muốn làm chủ các cấu trúc dữ liệu và giải thuật. Hy vọng bài viết này đã cung cấp cái nhìn tổng quan và chi tiết, giúp bạn tự tin hơn khi làm việc với danh sách liên kết đôi.

Sign up for Newsletter

Danh sách liên kết đôi là gì?

Ưu điểm và Nhược điểm của Danh sách liên kết đôi

Cài đặt Danh sách liên kết đôi

Thiết lập ban đầu

Các thao tác chèn (Insertion Operations)

Các thao tác xóa (Deletion Operations)

Ứng dụng của Danh sách liên kết đôi

Kết luận

Gửi phản hồiHủy

Sign up for Newsletter

Văn phòng & Sách

Danh sách liên kết đôi: Cấu trúc và Cài đặt Chi tiết

Danh sách liên kết đôi là gì?

Ưu điểm và Nhược điểm của Danh sách liên kết đôi

Cài đặt Danh sách liên kết đôi

Thiết lập ban đầu

Các thao tác chèn (Insertion Operations)

Các thao tác xóa (Deletion Operations)

Ứng dụng của Danh sách liên kết đôi

Kết luận

Chia sẻ:

Gửi phản hồiHủy