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

รายการเชื่อมโยงเดี่ยวคืออะไร?

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

นี่คือโครงสร้างโหนดของรายการเชื่อมโยงเดี่ยว:

เหตุใดจึงใช้รายการที่เชื่อมโยงมากกว่าอาร์เรย์

มีหลายกรณีที่ควรใช้รายการที่เชื่อมโยงมากกว่า แถว- ต่อไปนี้เป็นบางสถานการณ์:

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

Operaของรายการลิงค์เดี่ยว

Singly Linked List เหมาะกับการจัดสรรหน่วยความจำแบบไดนามิก โดยรองรับการทำงานพื้นฐานทั้งหมดของ Linked List เช่น การแทรก การลบ การค้นหา การอัพเดต การรวม Linked List สองรายการ การย้ายตำแหน่ง ฯลฯ

ที่นี่เราจะหารือเกี่ยวกับการดำเนินการของรายการที่เชื่อมโยงต่อไปนี้:

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

นี่คือตัวอย่างของรายการเชื่อมโยงที่มีสี่โหนด

การแทรกที่ส่วนหัวของ Singly Linked List

เป็นการดำเนินการแบบง่ายๆ โดยทั่วไปเรียกว่าการผลักรายการลิงก์เดี่ยว คุณต้องสร้างโหนดใหม่และวางไว้ที่ส่วนหัวของรายการลิงก์

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

1. หากรายการว่างเปล่า โหนดที่สร้างขึ้นใหม่จะเป็นโหนดหลัก และโหนดถัดไปของส่วนหัวจะเป็น ”NULL”
2. หากรายการไม่ว่างเปล่า โหนดใหม่จะเป็นโหนดหลัก และโหนดถัดไปจะชี้ไปยังโหนดหลักก่อนหน้า

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

function insertAtHead( head, value ):
	newNode = Node(value)
	if head is NULL:
		head = newNode
		return head
	else: 
		newNode.next = head
		return newNode

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

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

ต่อไปนี้เป็นขั้นตอน:

ขั้นตอน 1) เคลื่อนที่จนกระทั่งโหนด "ถัดไป" ของโหนดปัจจุบันกลายเป็นโมฆะ

ขั้นตอน 2) สร้างโหนดใหม่ด้วยค่าที่ระบุ

ขั้นตอน 3) กำหนดโหนดใหม่เป็นโหนดถัดไปของโหนดส่วนท้าย

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

function insertAtEnd( head, value ):
	newNode = Node(value)
	if head is NULL:
		head = newNode
		return head
	while head.next is not NULL:
		then head = head.next
	head.next = newNode
	newNode.next = NULL

การแทรกหลังโหนดในรายการที่เชื่อมโยงแบบเดี่ยว

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

ต่อไปนี้เป็นขั้นตอน:

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

ขั้นตอน 2) ตัวชี้ถัดไปของโหนดใหม่จะเป็นตัวชี้ถัดไปของโหนดปัจจุบัน

ขั้นตอน 3) โหนดถัดไปของโหนดปัจจุบันจะเป็นโหนดใหม่

นี่คือรหัสหลอกสำหรับการแทรกโหนดหลังโหนด:

function insertAfter( head, value, searchItem ):
	newNode = Node(value)
	while head.value equals searchItem:
		then head = head.next
	newNode.next = head.next.next
	head.next = newNode

การแทรกก่อนโหนดในรายการที่เชื่อมโยงเดี่ยว

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

ต่อไปนี้เป็นขั้นตอน:

ขั้นตอน 1) เคลื่อนที่จนกว่าค่าของโหนดถัดไปจะเท่ากับรายการค้นหา

ขั้นตอน 2) สร้างโหนดใหม่และกำหนด "ถัดไป" ของโหนดโดยให้โหนดถัดจากโหนดถัดไปของโหนดปัจจุบัน

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

นี่คือรหัสเทียม:

function insertBefore( head, value, searchItem ):
	newNode = Node(value)
	while head.next.value equals searchItem:
		then head = head.next
	newNode.next = head.next.next
	head.next = newNode

ลบส่วนหัวของรายการที่ลิงก์เดี่ยวๆ

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

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

ขั้นตอน 1) กำหนดโหนดถัดไปของโหนดหลักเป็นส่วนหัวใหม่

ขั้นตอน 2) ปลดปล่อยหน่วยความจำที่จัดสรรโดยโหนดหลักก่อนหน้า

ขั้นตอน 3) คืนโหนดส่วนหัวใหม่

รหัสหลอกสำหรับการลบโหนดหลัก:

function deleteHead( head ):
	temp = head
	head = head.next
	free( temp )
	return head

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

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

ต่อไปนี้เป็นขั้นตอนในการลบโหนดท้ายของรายการที่เชื่อมโยง:

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

ขั้นตอน 2) เพิ่มหน่วยความจำของโหนดถัดไปของโหนดปัจจุบัน

ขั้นตอน 3) ตั้งค่าโหนดถัดไปของโหนดปัจจุบันเป็น NULL

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

function deleteTail( head ):
	while head.next.next is not NULL:
		head = head.next
	free( head.next )
	head.next = NULL

ค้นหาและลบโหนดออกจากรายการลิงก์เดี่ยว

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

ขั้นตอน 1) ข้ามไปจนสุดรายการลิงก์ ตรวจสอบว่าโหนดปัจจุบันเท่ากับโหนดการค้นหาหรือไม่

ขั้นตอน 2) หากโหนดใดตรงกัน ให้จัดเก็บตัวชี้โหนดไปยังโหนดปัจจุบัน

ขั้นตอน 3) “ถัดไป” ของโหนดก่อนหน้าจะเป็นโหนดถัดไปของโหนดปัจจุบัน

ขั้นตอน 4) ลบและเพิ่มหน่วยความจำของโหนดปัจจุบัน

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

function searchAndDelete( head, searchItem ):
	while head.next.next is not NULL  and head.next.value is not equals searchItem :
		head = head.next
	head.next = head.next.next
	delete(head.next)

สำรวจรายการที่เชื่อมโยงเพียงรายการเดียว

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

ต่อไปนี้เป็นขั้นตอน:

ขั้นตอน 1) สำรวจแต่ละโหนดจนกว่าเราจะได้ค่าว่างเป็นโหนดถัดไป

ขั้นตอน 2) พิมพ์ค่าของโหนดปัจจุบัน

รหัสหลอกสำหรับการสำรวจรายการที่เชื่อมโยงโดยลำพัง:

function traverse( head ):
		while head.next is not NULL:
			print the value of the head
			head = head.next

ตัวอย่างรายการลิงค์เดี่ยวใน C++

#include<iostream>
using namespace std;
struct Node{
  int data;
  struct Node *next;
};
void insertAtHead(Node* &head, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  if(head!=NULL){
    newNode->next = head;
  }
  head = newNode;
  cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
  if(head==NULL){
    insertAtHead(head,value);
  }
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *temp = head;
  while(temp->next!=NULL){
    temp = temp->next;
  }
  temp->next = newNode;
  cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
  Node *temp = new Node();
  if( (*headPtr)->data == searchItem ){
    temp = *headPtr;
    *headPtr = (*headPtr)->next;
    free(temp);
  }else{
    Node *currentNode = *headPtr;
    while(currentNode->next != NULL){
      if(currentNode->next->data == searchItem){
        temp = currentNode->next;
        currentNode->next = currentNode->next->next;
        free(temp);
      }else{
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
}
void insertAfter(Node * &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next!=NULL &&  head->data!=searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node * &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next!=NULL &&  head->next->data!=searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){  
  Node* tempNode = new Node();
  tempNode = headPointer;
  cout<<"Traversal from head:\t";
  while(tempNode !=NULL){
    cout<<tempNode->data;
    if(tempNode->next)
      cout<<" --> ";
    tempNode = tempNode ->next;
  }
  cout<<endl;
}
int main(){
  Node *head = NULL;
  insertAtHead(head,5);
  insertAtHead(head,6);
  insertAtHead(head,7);
  insertEnd(head,9);
  traverse(head);
  searchAndDelete(&head,6);
  traverse(head);
  insertAfter(head,7,10);
  insertBefore(head,9,11);
  traverse(head);
}

Output:

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

ตัวอย่างรายการลิงค์เดี่ยวใน Python โครงการ

class Node:
  def __init__(self,data = None, next = None):
    self.data = data
    self.next = next
class SinglyLinkedList:
  def __init__(self):
    self.head = None 
  def insertAtHead(self, value):
    newNode = Node(data=value)    
    if self.head is not None:
      newNode.next = self.head
    self.head = newNode
    print(f'Added {newNode.data} at the front.')
    return  
  def insertAtEnd(self,value):
    if self.head is None:
      self.insertAtHead(value)
    newNode = Node(value)
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    print(f'Added {newNode.data} at the end.')  
  def searchAndDelete(self,searchItem):
    temp = Node()
    if self.head is searchItem:
      temp = self.head
      self.head = self.head.next
    else:
      currentNode = self.head
      while currentNode.next is not None:
        if currentNode.next.data is searchItem:
          temp = currentNode.next
          currentNode.next = currentNode.next.next
        else:
          currentNode = currentNode.next
    print(f'Deleted node\t{searchItem}')
    return
  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
    print(f'Inserted {value} after node\t{searchItem}')
    return 
  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
    print(f'Inserted {value} before node\t{searchItem}')
    return
  def traverse(self):
    temp = self.head
    print("Traversing from head:\t",end="")
    while temp:
      print("{}\t".format(temp.data),end="")
      temp = temp.next
    print()
SinglyLinkedList = SinglyLinkedList()
SinglyLinkedList.insertAtHead(5)
SinglyLinkedList.insertAtHead(6)
SinglyLinkedList.insertAtHead(7)
SinglyLinkedList.insertAtEnd(9)
SinglyLinkedList.traverse()
SinglyLinkedList.searchAndDelete(6)
SinglyLinkedList.traverse()
SinglyLinkedList.insertAfter(7,10)
SinglyLinkedList.insertbefore(9, 11)
SinglyLinkedList.traverse()

Output:

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

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

ความซับซ้อนมีอยู่ 2 ประเภท ได้แก่ ความซับซ้อนของเวลาและความซับซ้อนของพื้นที่ ความซับซ้อนของเวลาที่แย่ที่สุดและโดยเฉลี่ยจะเหมือนกันสำหรับรายการลิงก์เดี่ยว

ความซับซ้อนของเวลาสำหรับกรณีที่ดีที่สุด:

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

ความซับซ้อนของเวลาสำหรับกรณีเฉลี่ย:

• การแทรกภายในรายการเชื่อมโยงจะใช้ O(n) หากมีองค์ประกอบ “n” อยู่ในรายการเชื่อมโยงเดี่ยว
• การค้นหาและการลบอาจใช้ O(n) เช่นกัน เนื่องจากองค์ประกอบการค้นหาสามารถแสดงอยู่ในโหนดส่วนท้ายได้ ในกรณีนั้น คุณควรสำรวจรายการทั้งหมด

ความซับซ้อนของพื้นที่ของรายการลิงก์เดี่ยว

Singly Linked List จะจัดสรรหน่วยความจำแบบไดนามิก หากเราต้องการจัดเก็บ n องค์ประกอบ ระบบจะจัดสรรหน่วยความจำ n หน่วย ดังนั้นความซับซ้อนของพื้นที่คือ O(n)