รายการที่เชื่อมโยงทวีคูณ: C++, Python (ตัวอย่างโค้ด)
ซาราห์ เฉิน
รายการที่เชื่อมโยงแบบทวีคูณคืออะไร?
ในรายการที่มีการเชื่อมโยงแบบทวีคูณ แต่ละโหนดจะมีลิงก์ไปยังโหนดก่อนหน้าและโหนดถัดไป แต่ละโหนดประกอบด้วยสามองค์ประกอบ: หนึ่งโหนดเก็บข้อมูล และอีกสององค์ประกอบคือตัวชี้ของโหนดถัดไปและก่อนหน้า พอยน์เตอร์ทั้งสองนี้ช่วยให้เราไปข้างหน้าหรือข้างหลังจากโหนดใดโหนดหนึ่ง
ต่อไปนี้เป็นโครงสร้างพื้นฐานของรายการที่เชื่อมโยงแบบทวีคูณ
ทุกรายการที่เชื่อมโยงมีโหนดหัวและส่วนท้าย โหนด Head ไม่มีโหนด "ก่อนหน้า" (ตัวชี้ก่อนหน้า) และโหนดส่วนท้ายไม่มีโหนด "ถัดไป"
ต่อไปนี้เป็นคำศัพท์ที่สำคัญสำหรับรายการที่เชื่อมโยงแบบทวีคูณ:
- ก่อนหน้า: แต่ละโหนดเชื่อมโยงกับโหนดก่อนหน้า มันถูกใช้เป็นตัวชี้หรือลิงค์
- ถัดไป: แต่ละโหนดเชื่อมโยงกับโหนดถัดไป มันถูกใช้เป็นตัวชี้หรือลิงค์
- วันที่: ใช้เพื่อเก็บข้อมูลในโหนด “ข้อมูล” สามารถเก็บข้อมูลอื่นๆ โครงสร้างข้อมูล ข้างในนั้น ตัวอย่างเช่น สตริง พจนานุกรม เซต แฮชแมป ฯลฯ สามารถจัดเก็บไว้ใน “ข้อมูล” ได้
นี่คือโครงสร้างพื้นฐานของโหนดเดียวในรายการที่เชื่อมโยงแบบทวีคูณ:
Operaของรายการเชื่อมโยงแบบทวีคูณ
การดำเนินการของรายการที่เชื่อมโยงคู่ได้แก่ การเพิ่มและการลบโหนด การแทรกและการลบโหนด และการเคลื่อนผ่านรายการที่เชื่อมโยงจากบนลงล่าง
นี่คือรายการการดำเนินการที่เราสามารถดำเนินการได้โดยใช้รายการเชื่อมโยงคู่:
- แทรกด้านหน้า
- การแทรกที่ส่วนท้ายหรือโหนดสุดท้าย
- การแทรกหลังโหนด
- การแทรกก่อนโหนด
- ลบออกจากด้านหน้า
- การลบออกจากส่วนท้าย
- ค้นหาและลบโหนด
- ข้ามหัวจรดท้าย
- เคลื่อนหางไปทางศีรษะ
เราจะเห็นการใช้งานและรหัสเทียมสำหรับการดำเนินการทั้งหมดข้างต้น
การแทรกที่ด้านหน้าของรายการที่เชื่อมโยงแบบทวีคูณ
การแทรกไว้ข้างหน้าหมายความว่าเราจำเป็นต้องสร้างโหนดในรายการที่เชื่อมโยงและวางไว้ที่จุดเริ่มต้นของรายการที่เชื่อมโยง
ตัวอย่างเช่น มีโหนดที่กำหนดเป็น “15” เราจำเป็นต้องเพิ่มสิ่งนี้ลงในโหนดหลัก
นี่คือเงื่อนไขสำคัญสองประการขณะทำการดำเนินการนี้:
- โหนดใหม่จะเป็นโหนดหลักหากไม่มีโหนดในรายการที่เชื่อมโยงแบบทวีคูณ
- หากมีโหนดหลักอยู่แล้ว โหนดก่อนหน้าจะถูกแทนที่ด้วยโหนดใหม่
นี่คือรหัสเทียมสำหรับการดำเนินการนี้:
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: then ListHead = ListHead.next newNode.prev = ListHead ListHead.next = newNode return ListHead
การแทรกหลังโหนด
สมมติว่าเรามีรายการที่เชื่อมโยงคู่กันดังต่อไปนี้:
เราต้องการแทรกโหนดที่กำหนดซึ่งจะเชื่อมโยงหลังโหนดซึ่งมีค่าเป็น "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 then List = ListHead.next 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 then List = ListHead.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
ลบส่วนหัวของรายการที่เชื่อมโยงแบบทวีคูณ
โหนดหลักในรายการที่เชื่อมโยงแบบทวีคูณที่ไม่มีโหนดก่อนหน้า ดังนั้นตัวชี้ถัดไปจะเป็นโหนดหลักใหม่หากเราต้องการลบโหนดหลัก นอกจากนี้เรายังต้องเพิ่มหน่วยความจำที่โหนดครอบครองขณะลบโหนด
ต่อไปนี้เป็นขั้นตอนในการลบโหนดหลัก:
ขั้นตอน 1) กำหนดตัวแปรให้กับโหนดส่วนหัวปัจจุบัน
ขั้นตอน 2) เยี่ยมชมโหนด "ถัดไป" ของโหนดหลักปัจจุบันและสร้างโหนด "ก่อนหน้า" (ตัวชี้ก่อนหน้า) เป็น ''NULL" ซึ่งหมายความว่าเรากำลังตัดการเชื่อมต่อโหนดที่สองจากโหนดแรก
ขั้นตอน 3) ปลดปล่อยหน่วยความจำที่ถูกครอบครองโดยโหนดหลักก่อนหน้า
นี่คือรหัสหลอกสำหรับการลบส่วนหัวออกจากรายการที่เชื่อมโยงแบบทวีคูณ:
function deleteHead(ListHead): PrevHead = ListHead ListHead = ListHead.next ListHead.prev = NULL PrevHead.next = NULL free memory(PrevHead) return ListHead
จำเป็นต้องลบหน่วยความจำที่จัดสรรไว้หลังจากดำเนินการลบใดๆ มิฉะนั้น หน่วยความจำสำหรับบล็อกที่ถูกลบจะยังคงถูกใช้ไปตลอดระยะเวลาที่โปรแกรมทำงาน แอปพลิเคชันอื่นไม่สามารถใช้เซกเมนต์หน่วยความจำนั้นได้
ลบส่วนท้ายของรายการที่เชื่อมโยงแบบทวีคูณ
การดำเนินการนี้คล้ายกับการลบส่วนหัว ในกรณีนี้ แทนที่จะลบส่วนหัว เราต้องลบส่วนท้าย เมื่อต้องการระบุโหนดเป็นโหนดส่วนท้าย เราควรตรวจสอบว่าตัวชี้ถัดไปหรือโหนดถัดไปเป็นค่าว่างหรือไม่ หลังจากลบส่วนท้ายแล้ว เราต้องปลดปล่อยหน่วยความจำ
การดำเนินการนี้เรียกอีกอย่างว่าการ “ลบจากด้านหลัง”
ต่อไปนี้เป็นขั้นตอนในการดำเนินการนี้:
ขั้นตอน 1) เคลื่อนที่ไปจนถึงโหนดท้ายของรายการที่เชื่อมโยงแบบทวีคูณ
ขั้นตอน 2) กำหนดตัวแปรหรือตัวชี้ให้กับโหนดส่วนท้าย
ขั้นตอน 3) ทำให้โหนด "ถัดไป" เป็น NULL และเพิ่มหน่วยความจำของโหนดส่วนท้าย
นี่คือรหัสหลอกสำหรับการลบโหนดท้าย:
function DeleteTail( ListHead ): head = ListHead while ListHead.next is not NULL: ListHead = ListHead.next Tail = ListHead.next ListHead.next = NULL free memory( Tail ) return head
ค้นหาและลบโหนดออกจากรายการเชื่อมโยงแบบทวีคูณ
การดำเนินการนี้ช่วยให้เราค้นหาข้อมูลโหนดเฉพาะและลบโหนดนั้นได้ เราจำเป็นต้องดำเนินการค้นหาเชิงเส้นเนื่องจากรายการลิงก์เป็นโครงสร้างข้อมูลเชิงเส้น หลังจากลบแล้ว เรายังต้องล้างหน่วยความจำด้วย
ต่อไปนี้เป็นขั้นตอนในการค้นหาและลบโหนดในรายการลิงก์คู่:
ขั้นตอน 1) สำรวจรายการที่เชื่อมโยงจากส่วนหัวจนกว่าค่าของโหนดจะเท่ากับรายการค้นหา
ขั้นตอน 2) กำหนดตัวแปร “deleteNode” ให้กับโหนดที่ตรงกัน
ขั้นตอน 3) กำหนดโหนดก่อนหน้าของ "deleteNode" ให้กับโหนดถัดไป
ขั้นตอน 4) ปลดปล่อยหน่วยความจำของ "deleteNode"
นี่คือซูโดโค้ดสำหรับการค้นหาและลบโหนดจากรายการที่ลิงก์:
function SearchAndDelete(ListHead, searchItem): head = ListHead while ListHead.next.value not equals searchItem: head = head.next deleteNode = head.next head.next = head.next.next head.next.prev = head deleteNode.next, deleteNode.next = NULL free memory(deleteNode) return ListHead
สำรวจรายการที่เชื่อมโยงแบบทวีคูณจากไปข้างหน้า
เพื่อสำรวจจากโหนดหลักและวนซ้ำโหนดถัดไปจนกว่าเราจะพบ "NULL" ในขณะที่สำรวจแต่ละโหนด เราสามารถพิมพ์ค่าของโหนดได้ ต่อไปนี้เป็นขั้นตอนในการเคลื่อนที่จากด้านหน้า (ทิศทางไปข้างหน้า):
ขั้นตอน 1) กำหนดตัวชี้หรือตัวแปรให้กับโหนดส่วนหัวปัจจุบัน
ขั้นตอน 2) วนซ้ำไปยังโหนดถัดไปของส่วนหัวจนกระทั่งได้รับ "NULL"
ขั้นตอน 3) พิมพ์ข้อมูลของโหนดในการวนซ้ำแต่ละครั้ง
ขั้นตอน 4) กลับโหนดหัว
นี่คือรหัสหลอกสำหรับการสำรวจรายการที่มีการเชื่อมโยงแบบทวีคูณจากด้านหน้า:
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
ที่นี่ การส่งคืนไม่ใช่ข้อบังคับ แต่การส่งคืนโหนดหลักหลังการดำเนินการถือเป็นแนวทางปฏิบัติที่ดี
สำรวจรายการที่เชื่อมโยงแบบทวีคูณจากด้านหลัง
การดำเนินการนี้เป็นแบบย้อนกลับของการเคลื่อนที่จากด้านหน้า วิธีการนี้เหมือนกัน แต่มีความแตกต่างเล็กน้อย เราต้องเคลื่อนที่ไปยังโหนดสุดท้าย จากนั้นจึงเคลื่อนที่จากโหนดสุดท้ายไปยังโหนดด้านหน้า
ต่อไปนี้เป็นขั้นตอนในการสำรวจรายการที่เชื่อมโยงแบบทวีคูณจากด้านหลัง:
ขั้นตอน 1) เคลื่อนตัวไปเรื่อย ๆ จนกระทั่งถึงส่วนท้าย
ขั้นตอน 2) จากโหนดส่วนท้าย เราจะเคลื่อนที่ไปจนกว่าเราจะได้โหนดก่อนหน้าเป็น "NULL" “ก่อนหน้า” (ตัวชี้ก่อนหน้า) จะเป็นโมฆะสำหรับโหนดหลัก
ขั้นตอน 3) ในการวนซ้ำแต่ละครั้ง เราจะพิมพ์ข้อมูลโหนด
นี่คือรหัสหลอกสำหรับการสำรวจจากด้านหลัง:
function traverseFromBack(ListHead): head = ListHead while head not equals NULL: head = head.next tail = head while tail not equal to NULL: print tail.value tail = tail.prev return ListHead
ความแตกต่างระหว่างรายการเชื่อมโยงแบบเดี่ยวและแบบทวีคูณ
ข้อแตกต่างที่สำคัญระหว่างรายการ Singly และ Doublely Linked คือจำนวนลิงก์
ต่อไปนี้เป็นข้อแตกต่างระหว่างโหนดของรายการที่เชื่อมโยงแบบเดี่ยวและโครงสร้างโหนดของรายการที่เชื่อมโยงแบบทวีคูณ:
| สนาม | รายการที่เชื่อมโยงเพียงรายการเดียว | รายการที่เชื่อมโยงเป็นสองเท่า |
|---|---|---|
| โครงสร้าง | รายการที่เชื่อมโยงเพียงรายการเดียว มีหนึ่งช่องข้อมูลและหนึ่งลิงค์ไปยังโหนดถัดไป | รายการที่เชื่อมโยงแบบทวีคูณมีช่องข้อมูลหนึ่งช่องและลิงก์สองรายการ หนึ่งอันสำหรับโหนดก่อนหน้าและอีกอันสำหรับโหนดถัดไป |
| การข้ามผ่าน | มันสามารถเคลื่อนที่ได้ตั้งแต่หัวจรดท้ายเท่านั้น | สามารถเคลื่อนที่ได้ทั้งเดินหน้าและถอยหลัง |
| หน่วยความจำ | ใช้หน่วยความจำน้อยลง | ใช้หน่วยความจำมากกว่ารายการที่เชื่อมโยงเพียงรายการเดียว |
| การเข้าถึง | รายการที่เชื่อมโยงแบบเดี่ยวมีประสิทธิภาพน้อยกว่าเนื่องจากใช้ลิงก์เดียวไปยังโหนดถัดไป ไม่มีลิงก์สำหรับโหนดก่อนหน้า | รายการที่เชื่อมโยงแบบทวีคูณมีประสิทธิภาพมากกว่ารายการที่เชื่อมโยงแบบเดี่ยว |
รายการที่เชื่อมโยงทวีคูณใน C++
#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);
}
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 = new 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 = new node();
head = listHead;
cout<<"Traversal from head:\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 = new node();
head = (*listHead);
while(head->next!=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;
return;
}
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 Aded 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 head: 10 9 11 5 20 6 7 Deleted Node 7 Traversal from head: 6 20 5 11 9 10 Traversal from head: 10 9 11 5 20 6
รายการที่เชื่อมโยงทวีคูณใน Python
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.insertFront(val)
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:
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 is not 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 is not 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.next is not None and temp.data is not searchItem:
temp = temp.next
if self.head is None or temp is None:
return
if self.head.data is 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))
return
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
ความซับซ้อนของรายการที่เชื่อมโยงแบบคู่
โดยทั่วไปความซับซ้อนของเวลาจะแบ่งออกเป็น 3 ประเภท
พวกเขาจะ:
- เคสที่ดีที่สุด
- กรณีเฉลี่ย
- กรณีที่เลวร้ายที่สุด
ความซับซ้อนของเวลาในกรณีที่ดีที่สุดสำหรับรายการเชื่อมโยงแบบคู่:
- การแทรกในส่วนหัวหรือส่วนท้ายจะมีค่าใช้จ่าย O(1) เนื่องจากเราไม่จำเป็นต้องเข้าไปภายในรายการที่เชื่อมโยง ตัวชี้ส่วนหัวและส่วนท้ายสามารถให้เราเข้าถึงโหนดส่วนหัวและส่วนท้ายด้วยความซับซ้อนของเวลา O(1)
- การลบที่หัวหรือส่วนท้ายจะมีค่าใช้จ่าย O(1)
- การค้นหาโหนดจะมีความซับซ้อนของเวลาเท่ากับ O(1) เนื่องจากโหนดเป้าหมายสามารถเป็นโหนดหัวได้
ความซับซ้อนของเวลาในกรณีเฉลี่ยของรายการเชื่อมโยงแบบคู่:
- การแทรกที่หัวหรือหางจะมีความซับซ้อนของเวลาเท่ากับต้นทุน O(1)
- การลบที่หัวหรือหางจะมีความซับซ้อนของเวลาและมีต้นทุน O(1)
- การค้นหาโหนดจะมีความซับซ้อนของเวลาเท่ากับ O(n) เนื่องจากรายการค้นหาสามารถอยู่ที่ใดก็ได้ระหว่างรายการที่เชื่อมโยง ในที่นี้ "n" คือโหนดทั้งหมดที่มีอยู่ในรายการที่เชื่อมโยง
ความซับซ้อนของเวลาในกรณีเลวร้ายที่สุดของรายการที่เชื่อมโยงแบบคู่จะเหมือนกับกรณีโดยเฉลี่ย
ความซับซ้อนของหน่วยความจำของรายการเชื่อมโยงแบบคู่
ความซับซ้อนของหน่วยความจำคือ O(n) โดยที่ "n" คือจำนวนโหนดทั้งหมด ขณะใช้งานรายการลิงก์ เราต้องปลดปล่อยหน่วยความจำที่ใช้ มิฉะนั้น หากรายการลิงก์มีขนาดใหญ่ขึ้น หน่วยความจำอาจรั่วไหลได้
สรุป
- รายการที่เชื่อมโยงคือโครงสร้างข้อมูลเชิงเส้นประเภทหนึ่ง ซึ่งเป็นการรวบรวมข้อมูลที่แสดงในลักษณะเส้นตรง
- รายการที่เชื่อมโยงแบบทวีคูณคือประเภทของรายการที่เชื่อมโยงโดยที่โหนดมีการเชื่อมโยงกับทั้งโหนดก่อนหน้าและถัดไป
- รายการที่เชื่อมโยงแบบคู่จะมีการดำเนินการทั้งหมด เช่น การเพิ่มโหนด การลบโหนด การแทรกโหนดหลังหรือก่อนโหนดอื่น และการเคลื่อนผ่านรายการที่เชื่อมโยงจากหัวถึงหาง
- รายการที่เชื่อมโยงแบบทวีคูณมีช่องข้อมูลหนึ่งช่องและลิงก์สองรายการ หนึ่งอันสำหรับโหนดก่อนหน้าและอีกอันสำหรับโหนดถัดไป
- ความซับซ้อนของรายการเชื่อมโยงคู่ กรณีที่ดีที่สุด กรณีเฉลี่ย
- และกรณีที่เลวร้ายที่สุด
