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

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

Singly Linked List is a linear and unidirectional data structure where data is saved on the nodes, and each node is connected via a link to its next node. Each node contains a data field and a link to the next node. Singly Linked Lists can be traversed in only one direction, whereas a รายการที่เชื่อมโยงเป็นสองเท่า can be traversed in both directions.

Here is the node structure of a Singly Linked List:

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

Why Use a Linked List Over an Array?

Several scenarios favor a Linked List over an แถว:

• ไม่ทราบจำนวนองค์ประกอบ: When the required element count is not known at compile time, a Linked List allocates memory dynamically as elements get added.
• การเข้าถึงแบบสุ่ม: When random indexed access is not needed, a Linked List is a suitable choice.
• การแทรกตรงกลาง: Inserting in the middle of an array requires shifting elements. A Linked List allows insertion at any position by rewriting only a few pointers.

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

A Singly Linked List is good for dynamically allocating memory. It supports the standard operations of the linked list, i.e., insertion, deletion, searching, updating, merging two lists, and traversing.

The following operations are discussed in this article:

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

Here is an example of a linked list with four nodes.

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

Insertion at the Head of a Singly Linked List

This is a simple operation. It is generally known as pushing onto a Singly Linked List. A new node is created and placed at the head of the list.

To perform this operation, follow two important conditions:

1. If the list is empty, the newly created node becomes the head node, and its ถัดไป pointer is NULL.
2. If the list is not empty, the new node becomes the head node, and its ถัดไป pointer points to the previous head node.

Here is the pseudo-code for inserting a node at the head of a linked list:

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

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

Insertion at the End of a Singly Linked List

Inserting a node at the end of a linked list is similar to inserting at the head. Traverse to the tail node, then point its ถัดไป pointer to the new node. If the head is NULL, the new node becomes the head.

ขั้นตอน 1) Traverse until the ถัดไป pointer of the current node becomes NULL.

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

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

The pseudo-code for inserting at the tail of a singly list:

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

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

Insertion After a Node in a Singly Linked List

Inserting after a node has two parts: search for the target node and attach a new node after it. Traverse the list until a match is found, then splice the new node in.

ขั้นตอน 1) Traverse until the value of the current node equals the search item.

ขั้นตอน 2) Set the new node’s ถัดไป pointer to the current node’s ถัดไป ตัวชี้

ขั้นตอน 3) Point the current node’s ถัดไป pointer to the new node.

รหัสเทียม:

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

Insertion Before a Node in a Singly Linked List

This is similar to insertion after a node. Traverse until the next node matches the search value, then insert the new node before it.

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

ขั้นตอน 2) Create a new node and set its ถัดไป pointer to the current node’s ถัดไป.

ขั้นตอน 3) Point the current node’s ถัดไป to the new node.

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

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

Delete the Head of the Singly Linked List

The head pointer is provided as the parameter. The head node is removed, and the next node becomes the new head. The memory of the deleted node must be freed to avoid memory leaks.

ขั้นตอน 1) Assign the next node of the head as the new head.

ขั้นตอน 2) Free the allocated memory of the previous head node.

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

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

การลบส่วนหัวของลิงค์ลิสต์

Delete the Tail of the Singly Linked List

Deleting the tail node is similar to deleting the head node. The difference is that traversal to the end of the list is required. In a Singly Linked List, the node whose ถัดไป pointer is NULL is the tail node.

ขั้นตอน 1) Traverse until just before the tail node. Save the current node.

ขั้นตอน 2) Free the memory of the next node (the tail).

ขั้นตอน 3) Set the next node of the current node to NULL.

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

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

Search and Delete a Node from a Singly Linked List

This function performs two tasks: search and delete. Traverse until the end of the list. If a matching node is found, remove it and relink the previous node’s ถัดไป ตัวชี้

ขั้นตอน 1) Traverse until the end of the list. Check whether the current node equals the search node.

ขั้นตอน 2) If a match is found, store a pointer to the current node.

ขั้นตอน 3) การขอ ถัดไป of the previous node becomes the next node of the current node.

ขั้นตอน 4) Delete the current node and free its memory.

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

Traverse a Singly Linked List

A Singly Linked List only supports traversal from head to tail. There is no pointer to the previous node, so reverse traversal is not possible. Each node is visited in turn, printing its value until NULL is reached.

ขั้นตอน 1) Traverse each node until NULL is reached.

ขั้นตอน 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

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

There are two kinds of complexity: time complexity and space complexity. The worst and average case time complexity are the same for a Singly Linked List.

Best-case time complexity:

• Insertion at the head can be done in O(1). No traversal inside the list is required.
• Search and delete can be done in O(1) if the target element is at the head node.

Average-case time complexity:

• Insertion inside a linked list takes O(n), where n is the total number of elements.
• Search and delete can take O(n) too, because the target element can reside anywhere up to the tail node.

Space complexity of Singly Linked List

A Singly Linked List dynamically allocates memory. To store n elements, it allocates n memory units. So the space complexity is O(n).

Applications of Singly Linked List

Singly Linked Lists appear in many places where forward-only traversal and dynamic memory are useful:

• Stacks and queues: Underlying storage for LIFO stacks and FIFO queues built from nodes.
• Hash table chaining: Collisions are resolved by chaining entries into a Singly Linked List per bucket.
• Adjacency lists: Sparse graphs use a Singly Linked List of neighbors for each vertex.
• ตารางสัญลักษณ์: Compilers and interpreters chain identifiers into a Singly Linked List per scope.
• Memory allocators: Free-list allocators track free blocks as a Singly Linked List.

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