Danh sách liên kết đôi: C++, Python (Code Ví dụ)

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

Trong danh sách liên kết đôi, mỗi nút đều có liên kết đến cả nút trước và nút sau. Mỗi nút bao gồm ba phần tử: một phần tử chứa dữ liệu, và hai phần tử còn lại là con trỏ đến nút trước và nút sau. Hai con trỏ này giúp di chuyển tiến hoặc lùi từ một nút cụ thể.

Đây là cấu trúc cơ bản của danh sách liên kết đôi.

Cấu trúc của danh sách liên kết đôi

Mỗi danh sách liên kết đều có một nút đầu và một nút cuối. Nút đầu không có trước (con trỏ trước đó) nút, và nút đuôi không có tiếp theo nút.

Dưới đây là một số thuật ngữ quan trọng đối với danh sách liên kết đôi:

• Prev: Mỗi nút được liên kết với nút trước đó của nó. Nó được sử dụng như một con trỏ hoặc liên kết.
• Tiếp theo: Mỗi nút được liên kết với nút tiếp theo của nó. Nó được sử dụng như một con trỏ hoặc liên kết.
• ngày: Điều này được sử dụng để lưu trữ dữ liệu trong một nút. Dữ liệu có thể chứa các thông tin khác. Cấu trúc dữ liệu Bên trong đó. Ví dụ, chuỗi ký tự, từ điển, tập hợp, bảng băm và các cấu trúc khác có thể được lưu trữ trong trường dữ liệu.

Đây là cấu trúc cơ bản của một nút đơn trong danh sách liên kết đôi:

Cấu trúc của một nút trong Danh sách liên kết đôi

Operacác chức năng của danh sách liên kết đôi

Các thao tác trên danh sách liên kết đôi bao gồm thêm, xóa, chèn và loại bỏ các phần tử, cũng như duyệt danh sách từ trên xuống dưới hoặc từ dưới lên trên.

Dưới đây là danh sách các thao tác có thể thực hiện trên danh sách liên kết đôi:

• Chèn ở phía trước
• Chèn vào phần đuôi hoặc nút cuối cùng
• Chèn sau một nút
• Chèn trước một nút
• Xóa từ phía trước
• Xóa từ đuôi
• Tìm kiếm và xóa một nút
• Đi ngang từ đầu đến đuôi
• Xoay đuôi tới đầu

Phần hướng dẫn triển khai và mã giả cho mỗi thao tác này được trình bày bên dưới.

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

Chèn vào đầu danh sách có nghĩa là tạo một nút trong danh sách liên kết và đặt nó ở đầu danh sách.

Ví dụ, có một nút nhất định. 15Cần thêm nó làm nút đầu.

Có hai điều kiện quan trọng cần tuân thủ khi thực hiện thao tác này:

1. Nếu danh sách liên kết đôi rỗng, nút mới sẽ trở thành nút đầu.
2. Nếu đã có một nút đầu (head node), nút đầu cũ sẽ được thay thế bằng nút đầu mới.

Đây là đoạn mã giả cho thao tác này:

function insertAtFront(ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = newNode
  newNode.next = ListHead
  newNode.prev = NULL
  return ListHead

Chèn vào nút phía trước

Chèn phần tử vào cuối danh sách liên kết đôi

Chèn vào cuối nghĩa là tạo một nút trong danh sách liên kết và đặt nó ở cuối danh sách.

Có hai phương pháp thực hiện thao tác này:

• Phương pháp 1: Bắt đầu duyệt từ đầu danh sách liên kết đôi cho đến khi tiếp theo trở thành null. Sau đó liên kết nút mới với tiếp theo con trỏ.
• Phương pháp 2: Lấy nút cuối cùng của danh sách liên kết đôi. Sau đó, tiếp theo Con trỏ của nút cuối cùng trỏ đến nút mới. Nút mới trở thành nút cuối cùng.

Đây là đoạn mã giả để chèn vào nút cuối:

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Chèn vào cuối danh sách liên kết

Chèn sau một nút

Hãy xem xét một danh sách liên kết đôi hiện có như sau:

Mục tiêu là chèn một nút nhất định sẽ được liên kết sau nút có giá trị đã cho. 12.

Bước 1) Duyệt từ nút đầu đến nút cuối. Kiểm tra xem nút nào có giá trị. 12.

Bước 2) Tạo một nút mới và gán nó làm con trỏ tiếp theo của nút. 12. Các tiếp theo Số nút của nút mới sẽ là 15.

Đây là đoạn mã giả để chèn một nút sau một nút khác trong danh sách liên kết đôi:

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Chèn sau một nút

Chèn trước một nút

Thao tác này tương tự như việc chèn sau một nút. Một giá trị nút cụ thể được tìm kiếm, sau đó một nút mới được tạo và chèn vào trước nút được tìm kiếm.

Để chèn một nút nhất định 15 trước nút 12, hãy làm theo các bước sau:

Bước 1) Duyệt danh sách liên kết từ nút đầu đến nút đuôi.

Bước 2) Kiểm tra xem con trỏ next của nút hiện tại có giá trị hay không. 12.

Bước 3) Chèn nút mới vào dưới dạng tiếp theo nút của nút hiện tại.

Đây là đoạn mã giả để chèn một nút trước một nút khác trong danh sách liên kết đôi:

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.next.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Chèn một nút trước một nút

Xóa phần tử đầu của danh sách liên kết đôi

Nút đầu tiên trong danh sách liên kết đôi không có nút nào đứng trước nó. Vì vậy, tiếp theo Con trỏ trở thành nút đầu mới khi nút đầu hiện tại bị xóa. Việc giải phóng bộ nhớ do nút bị xóa chiếm dụng cũng là điều cần thiết.

Dưới đây là các bước để xóa nút đầu:

Bước 1) Gán một biến cho nút đầu hiện tại.

Bước 2) Truy cập vào tiếp theo nút của nút đầu hiện tại và tạo ra trước Con trỏ NULL. Thao tác này ngắt kết nối nút thứ hai khỏi nút thứ nhất.

Bước 3) Giải phóng bộ nhớ do nút đầu tiên chiếm dụng.

Đây là đoạn mã giả để xóa phần tử đầu tiên khỏi danh sách liên kết đôi:

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead

Xóa nút đầu

Việc giải phóng bộ nhớ đã cấp phát sau khi xóa là bắt buộc. Nếu không, bộ nhớ dành cho khối bị xóa sẽ vẫn bị chiếm dụng trong suốt thời gian chạy của chương trình, và không ứng dụng nào khác có thể sử dụng phân đoạn bộ nhớ đó.

Xóa phần đuôi của danh sách liên kết đôi

Thao tác này tương tự như việc xóa đầu nút. Thay vì xóa đầu nút, phần đuôi nút sẽ bị xóa. Để xác định một nút là đuôi nút, hãy kiểm tra xem con trỏ next có phải là null hay không. Sau khi xóa đuôi nút, vùng nhớ phải được giải phóng.

Thao tác này còn được gọi là xóa từ phía sau.

Dưới đây là các bước để thực hiện việc này:

Bước 1) Duyệt đến nút cuối cùng của danh sách liên kết đôi.

Bước 2) Gán một biến hoặc con trỏ tới nút đuôi.

Bước 3) Đặt tiếp theo Trỏ con trỏ về NULL và giải phóng bộ nhớ của nút cuối.

Đây là đoạn mã giả để xóa nút cuối cùng:

function deleteTail(ListHead):
  head = ListHead
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  Tail = ListHead
  ListHead.prev.next = NULL
  free memory(Tail)
  return head

Tìm kiếm và xóa một nút khỏi danh sách liên kết đôi.

Thao tác này tìm kiếm một giá trị nút cụ thể và xóa nút đó. Cần phải thực hiện tìm kiếm tuyến tính vì danh sách liên kết là một cấu trúc dữ liệu tuyến tính. Sau khi xóa, bộ nhớ phải được giải phóng.

Dưới đây là các bước tìm kiếm và xóa một nút trong danh sách liên kết đôi:

Bước 1) Duyệt qua danh sách liên kết từ đầu đến cuối cho đến khi giá trị của nút bằng với mục cần tìm.

Bước 2) Gán một biến xóa nút đến nút phù hợp.

Bước 3) Liên kết nút trước đó của xóa nút đến nút tiếp theo và thiết lập nút tiếp theo. trước Con trỏ trỏ đến nút trước đó.

Bước 4) Giải phóng ký ức của xóa nút.

Đây là đoạn mã giả để tìm kiếm và xóa một nút khỏi danh sách liên kết:

function searchAndDelete(ListHead, searchItem):
  head = ListHead
  while head.value not equals searchItem:
    head = head.next
  deleteNode = head
  head.prev.next = head.next
  if head.next is not NULL:
    head.next.prev = head.prev
  free memory(deleteNode)
  return ListHead

Thao tác tìm kiếm và xóa

Duyệt qua danh sách liên kết đôi từ phía trước

Việc duyệt từ nút đầu tiên sẽ lặp qua nút tiếp theo cho đến khi tìm thấy giá trị NULL. Trong khi duyệt qua từng nút, giá trị có thể được in ra. Dưới đây là các bước để duyệt theo chiều thuận:

Bước 1) Gán một con trỏ hoặc biến cho nút đầu hiện tại.

Bước 2) Lặp lại cho đến nút tiếp theo của phần đầu cho đến khi nhận được giá trị NULL.

Bước 3) In ra dữ liệu của nút trong mỗi lần lặp.

Bước 4) Trả về nút đầu.

Đây là đoạn mã giả để duyệt qua một danh sách liên kết đôi từ đầu:

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals NULL:
    print head.data
    head = head.next
  return ListHead

Việc trả về không bắt buộc. Tuy nhiên, việc trả về nút đầu sau khi thực hiện các thao tác là một thực hành tốt.

Duyệt qua danh sách liên kết đôi từ phía sau.

Thao tác này là thao tác ngược lại của việc duyệt từ phía trước. Cách tiếp cận tương tự với một điểm khác biệt nhỏ: trước tiên hãy đến nút cuối, sau đó đi ngược trở lại nút đầu bằng cách sử dụng... trước con trỏ.

Dưới đây là các bước để duyệt qua một danh sách liên kết đôi từ phía sau:

Bước 1) Di chuyển tiếp cho đến khi đến nút cuối cùng.

Bước 2) Từ nút đuôi, duyệt theo hướng bằng cách sử dụng trước cho đến khi nút trước đó là NULL. trước Con trỏ có giá trị null đối với nút đầu.

Bước 3) Tại mỗi lần lặp, hãy in dữ liệu của nút.

Đây là đoạn mã giả để duyệt từ phía sau:

function traverseFromBack(ListHead):
  head = ListHead
  while head.next is not NULL:
    head = head.next
  tail = head
  while tail is not NULL:
    print tail.value
    tail = tail.prev
  return ListHead

Sự khác biệt giữa danh sách liên kết đơn và danh sách liên kết đôi

Sự khác biệt chính giữa danh sách liên kết đơn và danh sách liên kết đôi nằm ở số lượng liên kết mà mỗi nút nắm giữ.

Dưới đây là sự khác biệt giữa các nút của danh sách liên kết đơn và danh sách liên kết đôi:

Danh sách liên kết đôi trong C++

Dưới đây là bản đầy đủ. C++ Triển khai một danh sách liên kết đôi với các thao tác chèn, xóa, tìm kiếm và duyệt.

#include<iostream>
using namespace std;
struct node{
  int data;
  struct node *next;
  struct node *prev;
};
void insertFront(node* &listHead, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  if(listHead != NULL){
    listHead->prev = newNode;
    newNode->next = listHead;
  }
  listHead = newNode;
  cout<<"Added "<<value<<" at the front"<<endl;
}
void insertEnd(node* &listHead, int value){
  if(listHead == NULL){
    insertFront(listHead, value);
    return;
  }
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL){
    head = head->next;
  }
  head->next = newNode;
  newNode->prev = head;
  cout<<"Added "<<value<<" at the end"<<endl;
}
void insertAfter(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
}
void insertBefore(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->next->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;
}
void traverseFromFront(node *listHead){
  node* head = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\t";
  while(head->next != NULL){
    head = head->next;
  }
  node *tail = head;
  while(tail != NULL){
    cout<<tail->data<<"\t";
    tail = tail->prev;
  }
  cout<<endl;
}
void searchAndDelete(node **listHead, int searchItem){
  node* head = (*listHead);
  while(head != NULL && head->data != searchItem){
    head = head->next;
  }
  if(*listHead == NULL || head == NULL) return;
  if((*listHead)->data == head->data){
    *listHead = head->next;
  }
  if(head->next != NULL){
    head->next->prev = head->prev;
  }
  if(head->prev != NULL){
    head->prev->next = head->next;
  }
  free(head);
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
int main(){
  node *head = NULL;
  insertFront(head, 5);
  insertFront(head, 6);
  insertFront(head, 7);
  insertEnd(head, 9);
  insertEnd(head, 10);
  insertAfter(head, 5, 11);
  insertBefore(head, 5, 20);
  traverseFromFront(head);
  traverseFromEnd(head);
  searchAndDelete(&head, 7);
  traverseFromFront(head);
  traverseFromEnd(head);
}

Đầu ra

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversal from head:    7  6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6  7
Deleted Node    7
Traversal from head:    6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6

Danh sách liên kết đôi trong Python

Dưới đây là bản đầy đủ. Python Triển khai danh sách liên kết đôi bằng cách sử dụng các lớp cho các nút và chính danh sách đó.

class Node:
  def __init__(self, data=None, prev=None, next=None):
    self.data = data
    self.next = next
    self.prev = prev
class DoublyLinkedList:
  def __init__(self):
    self.head = None
  def insertFront(self, val):
    newNode = Node(data=val)
    newNode.next = self.head
    if self.head is not None:
      self.head.prev = newNode
    self.head = newNode
    print("Added {} at the front".format(val))
  def insertEnd(self, val):
    newNode = Node(data=val)
    if self.head is None:
      self.head = newNode
      print("Added {} at the end".format(val))
      return
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    newNode.prev = temp
    print("Added {} at the end".format(val))
  def traverseFromFront(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp is not None:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
  def traverseFromEnd(self):
    temp = self.head
    print("Traversing from tail:\t", end="")
    while temp.next is not None:
      temp = temp.next
    tail = temp
    while tail is not None:
      print("{}\t".format(tail.data), end="")
      tail = tail.prev
    print()
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} after node {}".format(value, searchItem))
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} before node {}".format(value, searchItem))
  def searchAndDelete(self, searchItem):
    temp = self.head
    while temp is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == temp.data:
      self.head = temp.next
    if temp.next is not None:
      temp.next.prev = temp.prev
    if temp.prev is not None:
      temp.prev.next = temp.next
    print("Deleted Node\t{}".format(searchItem))
doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()

Đầu ra

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversing from head:   7  6  20  5  11  9  10
Traversing from tail:   10  9  11  5  20  6  7
Deleted Node    7
Traversing from head:   6  20  5  11  9  10
Traversing from tail:   10  9  11  5  20  6

Độ phức tạp của danh sách liên kết kép

Độ phức tạp về thời gian thường được chia thành ba loại: trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất.

Độ phức tạp thời gian trong trường hợp tốt nhất cho Danh sách liên kết kép:

1. Chèn vào đầu hoặc cuối tốn O(1) vì không cần duyệt bên trong danh sách liên kết. Con trỏ đầu và cuối cho phép truy cập trực tiếp vào các nút đầu và cuối.
2. Việc xóa ở đầu hoặc cuối tốn chi phí O(1).
3. Việc tìm kiếm một nút có chi phí O(1) khi nút mục tiêu là nút đầu.

Độ phức tạp thời gian trong trường hợp trung bình của Danh sách liên kết kép:

1. Chèn vào đầu hoặc cuối tốn chi phí O(1).
2. Việc xóa ở đầu hoặc cuối tốn chi phí O(1).
3. Việc tìm kiếm một nút có chi phí O(n), vì mục tiêu có thể nằm ở bất kỳ đâu trong danh sách. Ở đây, n là tổng số nút.

Độ phức tạp thời gian trong trường hợp xấu nhất của danh sách liên kết đôi cũng giống như trường hợp trung bình.

Độ phức tạp của bộ nhớ danh sách liên kết đôi

Độ phức tạp bộ nhớ là O(n), trong đó n là tổng số nút. Khi triển khai danh sách liên kết, bộ nhớ phải được giải phóng. Nếu không, danh sách liên kết càng lớn sẽ gây ra rò rỉ bộ nhớ.

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

Danh sách liên kết đôi là nền tảng của nhiều cấu trúc dữ liệu thực tế vì khả năng duyệt hai chiều giúp đơn giản hóa nhiều thao tác thông thường.

• Bộ nhớ đệm LRU: Bộ nhớ đệm Least-Recently-Used sử dụng Danh sách liên kết đôi với bản đồ băm cho việc di chuyển lên đầu và loại bỏ O(1).
• Lịch sử trình duyệt: Chức năng điều hướng tiến và lùi cho phép duyệt danh sách liên kết theo cả hai hướng.
• Các ngăn xếp hoàn tác và làm lại: Trình soạn thảo và IDE track phiên bản tài liệu với con trỏ trước và sau.
• Deque: Double-các hàng đợi có đầu cuối đẩy và lấy dữ liệu từ cả hai đầu trong thời gian O(1).
• Danh sách phát nhạc: Trước và sau tracCác nút k dựa vào con trỏ tiến và lùi.

Câu Hỏi Thường Gặp