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

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

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

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

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

เหตุใดจึงควรใช้โครงสร้างข้อมูลแบบ Linked List แทน Array?

มีหลายสถานการณ์ที่การใช้ Linked List เหมาะสมกว่าการใช้ Intégrédient แถว:

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

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

โครงสร้างข้อมูลแบบรายการเชื่อมโยงเดี่ยว (Singly 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

การใส่ที่ศีรษะ

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

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

ขั้นตอน 1) เดินทางไปจนถึง ถัดไป ตัวชี้ของโหนดปัจจุบันจะกลายเป็น NULL

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

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

รหัสเทียมสำหรับการแทรกข้อมูลที่ส่วนท้ายของลิสต์ที่มีสมาชิกเพียงตัวเดียว:

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

การสอดเข้าที่ส่วนหาง

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

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

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

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

ขั้นตอน 3) ชี้ไปยังโหนดปัจจุบัน ถัดไป ตัวชี้ไปยังโหนดใหม่

รหัสเทียม:

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

การแทรกโหนดหลังโหนดใน Singly Linked List

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

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

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

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

ขั้นตอน 3) ชี้ไปยังโหนดปัจจุบัน ถัดไป ไปยังโหนดใหม่

function insertBefore(head, value, searchItem):
  newNode = Node(value)
  while head.next.value != searchItem:
    head = head.next
  newNode.next = head.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

การลบส่วนท้ายของ Singly Linked List

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

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

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

ขั้นตอน 2) หากพบการจับคู่ ให้บันทึกตัวชี้ไปยังโหนดปัจจุบัน

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

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

function searchAndDelete(head, searchItem):
  while head.next.next is not NULL and head.next.value != searchItem:
    head = head.next
  temp = head.next
  head.next = head.next.next
  free(temp)

ค้นหาและลบโหนดออกจาก Singly Linked List

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

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

ขั้นตอน 1) วนลูปผ่านแต่ละโหนดจนกว่าจะพบค่า NULL

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

function traverse(head):
  while head is not NULL:
    print head.value
    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);
    return;
  }
  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 = NULL;
  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);
        break;
      } else {
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
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 = 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);
}

เอาท์พุต

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.')
  def insertAtEnd(self, value):
    if self.head is None:
      self.insertAtHead(value)
      return
    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):
    if self.head is None:
      return
    if self.head.data == searchItem:
      self.head = self.head.next
      print(f'Deleted node\t{searchItem}')
      return
    currentNode = self.head
    while currentNode.next is not None:
      if currentNode.next.data == searchItem:
        currentNode.next = currentNode.next.next
        print(f'Deleted node\t{searchItem}')
        return
      currentNode = currentNode.next
  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
    print(f'Inserted {value} after node\t{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
    print(f'Inserted {value} before node\t{searchItem}')
  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()

เอาท์พุต

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

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

ความซับซ้อนมีสองประเภท ได้แก่ ความซับซ้อนเชิงเวลาและความซับซ้อนเชิงพื้นที่ สำหรับโครงสร้างข้อมูลแบบรายการเชื่อมโยงเดี่ยว (Singly Linked List) ความซับซ้อนเชิงเวลาในกรณีที่เลวร้ายที่สุดและกรณีเฉลี่ยจะเท่ากัน

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

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

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

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

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

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

การประยุกต์ใช้รายการเชื่อมโยงเดี่ยว

โครงสร้างข้อมูลแบบลิสต์เดี่ยว (Singly Linked Lists) ปรากฏในหลายๆ ที่ซึ่งการท่องไปในทิศทางเดียวเท่านั้นและหน่วยความจำแบบไดนามิกมีประโยชน์:

• สแต็กและคิว: ระบบจัดเก็บข้อมูลพื้นฐานสำหรับสแต็ก LIFO และคิว FIFO ที่สร้างขึ้นจากโหนด
• การเชื่อมโยงตารางแฮช: การชนกันของข้อมูลจะได้รับการแก้ไขโดยการเชื่อมโยงรายการต่างๆ เข้ากับรายการเชื่อมโยงแบบเดี่ยว (Singly Linked List) ในแต่ละบัคเก็ต
• รายการที่อยู่ติดกัน: กราฟแบบเบาบางใช้รายการเชื่อมโยงแบบเดี่ยว (Singly Linked List) ของเพื่อนบ้านสำหรับแต่ละจุดยอด
• ตารางสัญลักษณ์: คอมไพเลอร์และอินเตอร์พรีเตอร์จะเชื่อมโยงตัวระบุต่างๆ เข้าด้วยกันเป็นรายการเชื่อมโยงเดี่ยว (Singly Linked List) ต่อขอบเขตหนึ่งๆ
• ตัวจัดสรรหน่วยความจำ: ผู้จัดสรรรายการอิสระ tracมีบล็อกว่าง k บล็อกในรูปแบบรายการเชื่อมโยงเดี่ยว (Singly Linked List)

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