รายการที่เชื่อมโยงทวีคูณ: C++, Python (Code ตัวอย่าง)

โครงสร้างข้อมูลแบบ Doubly Linked List คืออะไร?

ในโครงสร้างข้อมูลแบบรายการเชื่อมโยงสองทิศทาง (Doubly Linked List) แต่ละโหนดจะมีลิงก์ไปยังทั้งโหนดก่อนหน้าและโหนดถัดไป แต่ละโหนดประกอบด้วยองค์ประกอบสามส่วน คือ ส่วนหนึ่งเก็บข้อมูล และอีกสองส่วนเป็นตัวชี้ไปยังโหนดถัดไปและโหนดก่อนหน้า ตัวชี้ทั้งสองนี้ช่วยให้เราสามารถเลื่อนไปข้างหน้าหรือข้างหลังจากโหนดใดโหนดหนึ่งได้

นี่คือโครงสร้างพื้นฐานของรายการเชื่อมโยงสองทาง (Doubly Linked List)

โครงสร้างของรายการที่เชื่อมโยงแบบทวีคูณ

โครงสร้างข้อมูลแบบลิสต์เชื่อมโยงทุกโครงสร้างจะมีโหนดหัวและโหนดท้าย โหนดหัวไม่มี... prev โหนด (ตัวชี้ก่อนหน้า) และโหนดท้ายไม่มี ถัดไป ปม

ต่อไปนี้เป็นคำศัพท์สำคัญบางคำสำหรับโครงสร้างข้อมูลแบบ Doubly Linked List:

• ก่อนหน้า: แต่ละโหนดเชื่อมโยงกับโหนดก่อนหน้า มันถูกใช้เป็นตัวชี้หรือลิงค์
• ถัดไป: แต่ละโหนดเชื่อมโยงกับโหนดถัดไป มันถูกใช้เป็นตัวชี้หรือลิงค์
• วันที่: สิ่งนี้ใช้สำหรับจัดเก็บข้อมูลในโหนด ข้อมูลสามารถเก็บสิ่งอื่น ๆ ได้ โครงสร้างข้อมูล ภายในนั้น ตัวอย่างเช่น สามารถจัดเก็บสตริง พจนานุกรม เซต แฮชแมป และโครงสร้างอื่นๆ ไว้ในฟิลด์ข้อมูลได้

นี่คือโครงสร้างพื้นฐานของโหนดเดียวในรายการเชื่อมโยงสองทิศทาง:

โครงสร้างของโหนดในรายการที่เชื่อมโยงแบบทวีคูณ

Operaของรายการเชื่อมโยงแบบทวีคูณ

การดำเนินการของรายการเชื่อมโยงสองทิศทาง ได้แก่ การเพิ่ม การลบ การแทรก และการเอาโหนดออก รวมถึงการท่องไปในรายการจากบนลงล่างหรือจากล่างขึ้นบน

ต่อไปนี้คือรายการของการดำเนินการต่างๆ ที่สามารถนำมาใช้กับโครงสร้างข้อมูลแบบ Doubly Linked List ได้:

• แทรกด้านหน้า
• การแทรกที่ส่วนหางหรือโหนดสุดท้าย
• การแทรกหลังโหนด
• การแทรกก่อนโหนด
• ลบออกจากด้านหน้า
• การลบออกจากส่วนท้าย
• ค้นหาและลบโหนด
• ข้ามหัวจรดท้าย
• เคลื่อนหางไปทางศีรษะ

ต่อไปนี้คือรายละเอียดการใช้งานและรหัสเทียมสำหรับแต่ละการดำเนินการเหล่านี้

การแทรกข้อมูลด้านหน้าของรายการเชื่อมโยงสองทาง

การแทรกไว้ด้านหน้าหมายถึงการสร้างโหนดในรายการเชื่อมโยงและวางไว้ที่จุดเริ่มต้นของรายการ

ตัวอย่างเช่น มีโหนดที่กำหนดไว้ 15จำเป็นต้องเพิ่มโหนดนี้เป็นโหนดหัว

มีเงื่อนไขสำคัญสองประการที่ต้องปฏิบัติตามขณะดำเนินการนี้:

1. โหนดใหม่จะกลายเป็นโหนดหัวหากรายการเชื่อมโยงสองทิศทางว่างเปล่า
2. หากมีโหนดหัวอยู่แล้ว โหนดหัวเดิมจะถูกแทนที่ด้วยโหนดใหม่

นี่คือรหัสเทียมสำหรับการดำเนินการนี้:

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

การแทรกในโหนดด้านหน้า

การแทรกที่ส่วนท้ายของรายการเชื่อมโยงสองทาง

การแทรกที่ส่วนท้ายหมายถึงการสร้างโหนดในรายการเชื่อมโยงและวางไว้ที่ส่วนท้ายสุด

มีสองวิธีที่ดำเนินการนี้:

• วิธีฮิต: เริ่มสำรวจจากส่วนหัวของรายการเชื่อมโยงสองทิศทางจนกระทั่ง ถัดไป กลายเป็นค่าว่าง จากนั้นเชื่อมโยงโหนดใหม่กับ ถัดไป ตัวชี้
• วิธีฮิต: พิจารณาโหนดสุดท้ายของรายการเชื่อมโยงสองทิศทาง จากนั้น ถัดไป ตัวชี้ของโหนดสุดท้ายจะชี้ไปยังโหนดใหม่ โหนดใหม่นี้จะกลายเป็นโหนดท้าย

นี่คือรหัสเทียมสำหรับการแทรกที่โหนดท้าย:

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

การแทรกที่ส่วนท้ายของรายการที่เชื่อมโยง

การแทรกหลังจากโหนด

พิจารณาโครงสร้างข้อมูลแบบ Doubly Linked List ที่มีอยู่แล้วดังต่อไปนี้:

เป้าหมายคือการแทรกโหนดที่กำหนด ซึ่งจะเชื่อมโยงต่อจากโหนดที่มีค่าดังกล่าว 12.

ขั้นตอน 1) เริ่มจากโหนดแรกจนถึงโหนดสุดท้าย ตรวจสอบว่าโหนดใดมีค่า 12.

ขั้นตอน 2) สร้างโหนดใหม่และกำหนดให้เป็นตัวชี้ถัดไปของโหนด 12ส่วน ถัดไป โหนดของโหนดใหม่จะมีหมายเลข 15

นี่คือรหัสเทียมสำหรับการแทรกโหนดต่อจากโหนดในรายการเชื่อมโยงสองทิศทาง:

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

การแทรกหลังโหนด

การแทรกก่อนโหนด

การดำเนินการนี้คล้ายกับการแทรกหลังจากโหนด โดยจะค้นหาค่าโหนดเฉพาะ จากนั้นสร้างโหนดใหม่และแทรกเข้าไปก่อนโหนดที่ค้นหา

เพื่อแทรกโหนดที่กำหนด 15 ก่อนโหนด 12, ทำตามขั้นตอนเหล่านี้:

ขั้นตอน 1) สำรวจรายการที่เชื่อมโยงจากโหนดหลักไปยังโหนดท้าย

ขั้นตอน 2) ตรวจสอบว่าตัวชี้ถัดไปของโหนดปัจจุบันมีค่าหรือไม่ 12.

ขั้นตอน 3) แทรกโหนดใหม่เข้าไปเป็น ถัดไป โหนดของโหนดปัจจุบัน

นี่คือรหัสเทียมสำหรับการแทรกโหนดก่อนโหนดในรายการเชื่อมโยงสองทิศทาง:

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

การแทรกโหนดก่อนโหนด

ลบส่วนหัวของรายการเชื่อมโยงสองทาง

โหนดหัวในรายการเชื่อมโยงสองทิศทางไม่มีโหนดใดอยู่ก่อนหน้า ดังนั้น ถัดไป ตัวชี้จะกลายเป็นโหนดหัวใหม่เมื่อโหนดหัวปัจจุบันถูกลบออก นอกจากนี้ยังจำเป็นต้องปล่อยหน่วยความจำที่โหนดที่ถูกลบใช้ไปอีกด้วย

ต่อไปนี้คือขั้นตอนสำหรับการลบโหนดหัว:

ขั้นตอน 1) กำหนดตัวแปรให้กับโหนดส่วนหัวปัจจุบัน

ขั้นตอน 2) เยี่ยมชม ถัดไป โหนดของโหนดหัวปัจจุบันและสร้าง prev ตัวชี้เป็นค่า NULL ซึ่งจะตัดการเชื่อมต่อโหนดที่สองออกจากโหนดแรก

ขั้นตอน 3) ปล่อยหน่วยความจำที่โหนดหัวก่อนหน้าใช้ไป

นี่คือรหัสเทียมสำหรับการลบส่วนหัวออกจากรายการเชื่อมโยงสองทิศทาง:

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

กำลังลบโหนดส่วนหัว

จำเป็นต้องคืนหน่วยความจำที่จัดสรรไว้หลังจากลบข้อมูลทุกครั้ง มิเช่นนั้น หน่วยความจำสำหรับบล็อกที่ถูกลบจะยังคงถูกใช้งานอยู่ตลอดระยะเวลาการทำงานของโปรแกรม และแอปพลิเคชันอื่นจะไม่สามารถใช้ส่วนของหน่วยความจำนั้นได้

ลบส่วนท้ายของรายการเชื่อมโยงสองทาง

การดำเนินการนี้คล้ายกับการลบส่วนหัว แต่แทนที่จะลบส่วนหัว จะลบส่วนหางแทน ในการระบุว่าโหนดใดเป็นส่วนหาง ให้ตรวจสอบว่าตัวชี้ถัดไปเป็นค่าว่างหรือไม่ หลังจากลบส่วนหางแล้ว จะต้องปล่อยหน่วยความจำส่วนที่เหลือ

การผ่าตัดนี้เรียกอีกอย่างว่า การลบจากด้านหลัง.

นี่คือขั้นตอนในการทำเช่นนี้:

ขั้นตอน 1) วนลูปไปจนถึงโหนดสุดท้ายของรายการเชื่อมโยงสองทิศทาง (Doubly Linked List)

ขั้นตอน 2) กำหนดตัวแปรหรือตัวชี้ให้กับโหนดส่วนท้าย

ขั้นตอน 3) ตั้ง ถัดไป ชี้ไปยังค่า NULL และปลดปล่อยหน่วยความจำของโหนดท้าย

นี่คือรหัสเทียมสำหรับการลบโหนดท้าย:

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

ค้นหาและลบโหนดจากรายการเชื่อมโยงสองทาง

การดำเนินการนี้จะค้นหาค่าโหนดที่ระบุและลบโหนดนั้น การค้นหาแบบเชิงเส้นเป็นสิ่งจำเป็นเนื่องจากรายการเชื่อมโยงเป็นโครงสร้างข้อมูลเชิงเส้น หลังจากลบแล้ว จะต้องคืนหน่วยความจำ

ต่อไปนี้คือขั้นตอนการค้นหาและลบโหนดในรายการเชื่อมโยงสองทิศทาง:

ขั้นตอน 1) วนลูปผ่านรายการเชื่อมโยงจากส่วนหัวจนกว่าค่าของโหนดจะเท่ากับคำค้นหา

ขั้นตอน 2) กำหนดค่าให้กับตัวแปร ลบโหนด ไปยังโหนดที่ตรงกัน

ขั้นตอน 3) เชื่อมโยงโหนดก่อนหน้าของ ลบโหนด ไปยังโหนดถัดไป และตั้งค่าโหนดถัดไป prev ตัวชี้ไปยังโหนดก่อนหน้า

ขั้นตอน 4) ปลดปล่อยความทรงจำของ ลบโหนด.

ต่อไปนี้คือรหัสเทียมสำหรับการค้นหาและลบโหนดออกจากรายการเชื่อมโยง:

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

การค้นหาและการลบการดำเนินการ

ท่องไปในรายการเชื่อมโยงสองทางจากด้านหน้า

การวนลูปจากโหนดหัวจะวนซ้ำไปยังโหนดถัดไปจนกว่าจะพบค่า NULL ในระหว่างการวนลูปแต่ละโหนด สามารถพิมพ์ค่าออกมาได้ ต่อไปนี้คือขั้นตอนการวนลูปในทิศทางไปข้างหน้า:

ขั้นตอน 1) กำหนดตัวชี้หรือตัวแปรให้กับโหนดส่วนหัวปัจจุบัน

ขั้นตอน 2) วนซ้ำไปยังโหนดถัดไปของส่วนหัวจนกว่าจะได้ค่า NULL

ขั้นตอน 3) พิมพ์ข้อมูลโหนดในแต่ละรอบการทำงาน

ขั้นตอน 4) กลับโหนดหัว

นี่คือรหัสเทียมสำหรับการวนลูปผ่านรายการเชื่อมโยงสองทิศทางจากด้านหน้า:

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

การส่งคืนค่าไม่ใช่ข้อบังคับ อย่างไรก็ตาม การส่งคืนโหนดหัวหลังจากดำเนินการเสร็จสิ้นถือเป็นแนวปฏิบัติที่ดี

ท่องโครงสร้างข้อมูลแบบ Doubly Linked List จากด้านหลัง

การดำเนินการนี้เป็นการดำเนินการย้อนกลับของการเดินจากด้านหน้า วิธีการเหมือนกันแต่มีข้อแตกต่างเล็กน้อยคือ ไปถึงโหนดสุดท้ายก่อน จากนั้นเดินย้อนกลับไปยังโหนดเริ่มต้นโดยใช้ prev ตัวชี้

ต่อไปนี้คือขั้นตอนในการท่องไปในโครงสร้างข้อมูลแบบ Doubly Linked List จากด้านหลัง:

ขั้นตอน 1) เดินทางต่อไปจนกว่าจะถึงโหนดสุดท้าย

ขั้นตอน 2) จากโหนดท้าย ให้เดินทางต่อไปโดยใช้ prev จนกว่าโหนดก่อนหน้าจะเป็นค่าว่าง (NULL) prev ตัวชี้สำหรับโหนดหัวเป็นค่าว่าง

ขั้นตอน 3) ในแต่ละรอบการทำงาน ให้พิมพ์ข้อมูลของโหนดออกมา

นี่คือรหัสเทียมสำหรับการท่องกลับไปกลับมา:

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

ความแตกต่างระหว่างรายการเชื่อมโยงเดี่ยวและรายการเชื่อมโยงคู่

ความแตกต่างหลักระหว่างรายการเชื่อมโยงแบบเดี่ยว (Singly Linked List) และรายการเชื่อมโยงแบบคู่ (Doubly Linked List) คือจำนวนลิงก์ที่แต่ละโหนดมี

นี่คือความแตกต่างระหว่างโหนดของรายการเชื่อมโยงเดี่ยวและรายการเชื่อมโยงคู่:

รายการที่เชื่อมโยงทวีคูณใน C++

ด้านล่างนี้คือข้อมูลทั้งหมด C++ การใช้งานโครงสร้างข้อมูลแบบ Doubly Linked List ที่มีฟังก์ชันการแทรก การลบ การค้นหา และการวนดูข้อมูล

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

เอาท์พุต

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

รายการที่เชื่อมโยงทวีคูณใน Python

ด้านล่างนี้คือข้อมูลทั้งหมด Python การนำโครงสร้างข้อมูลแบบ Doubly Linked List มาใช้ โดยใช้คลาสสำหรับโหนดและตัวลิสต์เอง

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()

เอาท์พุต

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

ความซับซ้อนของรายการที่เชื่อมโยงแบบคู่

โดยทั่วไปแล้ว ความซับซ้อนของเวลาจะแบ่งออกเป็นสามประเภท ได้แก่ กรณีที่ดีที่สุด กรณีเฉลี่ย และกรณีที่แย่ที่สุด

ความซับซ้อนของเวลาในกรณีที่ดีที่สุดสำหรับรายการเชื่อมโยงแบบคู่:

1. การแทรกที่หัวหรือท้ายมีค่าใช้จ่าย O(1) เนื่องจากไม่จำเป็นต้องมีการวนซ้ำภายในรายการเชื่อมโยง ตัวชี้หัวและท้ายช่วยให้เข้าถึงโหนดหัวและท้ายได้โดยตรง
2. การลบที่หัวหรือท้ายมีค่าใช้จ่าย O(1)
3. การค้นหาโหนดมีค่าใช้จ่าย O(1) เมื่อโหนดเป้าหมายเป็นโหนดหัว

ความซับซ้อนของเวลาในกรณีเฉลี่ยของรายการเชื่อมโยงแบบคู่:

1. การแทรกที่หัวหรือหางมีค่าใช้จ่าย O(1)
2. การลบที่หัวหรือท้ายมีค่าใช้จ่าย O(1)
3. การค้นหาโหนดมีค่าใช้จ่าย O(n) เนื่องจากเป้าหมายสามารถอยู่ที่ใดก็ได้ในรายการ ในที่นี้ n คือจำนวนโหนดทั้งหมด

ความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดของรายการเชื่อมโยงสองทางนั้นเท่ากับกรณีเฉลี่ย

ความซับซ้อนของหน่วยความจำของรายการเชื่อมโยงแบบคู่

ความซับซ้อนของหน่วยความจำคือ O(n) โดยที่ n คือจำนวนโหนดทั้งหมด ในระหว่างการสร้างโครงสร้างข้อมูลแบบลิสต์เชื่อมโยง จะต้องมีการคืนหน่วยความจำ มิฉะนั้น ลิสต์เชื่อมโยงที่มีขนาดใหญ่เกินไปจะทำให้เกิดการรั่วไหลของหน่วยความจำ

การประยุกต์ใช้โครงสร้างข้อมูลแบบรายการเชื่อมโยงสองทาง

โครงสร้างข้อมูลแบบลิสต์เชื่อมโยงสองทิศทาง (Doubly Linked Lists) เป็นหัวใจสำคัญของโครงสร้างข้อมูลในโลกแห่งความเป็นจริงหลายอย่าง เนื่องจากความสามารถในการเข้าถึงข้อมูลแบบสองทิศทางช่วยลดความซับซ้อนของการดำเนินการทั่วไปหลายอย่าง

• แคช LRU: แคชแบบ Least-Recently-Used ใช้ Doubly Linked List ร่วมกับ hash map สำหรับการย้ายไปด้านหน้าและการลบออกด้วย O(1)
• ประวัติเบราว์เซอร์: การนำทางไปข้างหน้าและย้อนกลับจะเลื่อนดูรายการที่เชื่อมโยงไปในทิศทางใดก็ได้
• ลำดับการยกเลิกและการทำซ้ำ: โปรแกรมแก้ไขข้อความและ IDE track เวอร์ชันของเอกสารพร้อมตัวชี้ก่อนหน้าและถัดไป
• เดค: Double-คิวแบบ end จะทำการ push และ pop จากทั้งสองด้านในเวลา O(1)
• เพลย์ลิสต์เพลง: ก่อนหน้าและถัดไป tracปุ่ม k อาศัยตัวชี้ไปข้างหน้าและข้างหลัง

คำถามที่พบบ่อย