Enkeltforbundet liste i datastrukturer

Hvad er en enkeltstående liste?

Singly Linked List er en lineær og ensrettet datastruktur, hvor data gemmes på noderne, og hver node er forbundet via et link til dens næste node. Hver node indeholder et datafelt og et link til den næste node. Enkeltforbundne lister kan kun krydses i én retning, hvorimod dobbeltforbundne lister kan krydses i begge retninger.

Her er en nodestruktur af en enkeltforbundet liste:

Hvorfor bruge linket liste over array?

Der er flere tilfælde, hvor det er bedre at bruge den linkede liste frem for Array. Her er nogle scenarier:

• Ukendt antal elementer: Når du ikke ved, hvor mange elementer du skal gemme i løbet af programmets køretid, kan du bruge den linkede liste. Hukommelse allokeres dynamisk, når du tilføjer elementer til de sammenkædede lister.
• Tilfældig adgang: I et scenarie, hvor du ikke behøver at bruge tilfældig adgang fra elementerne, kan du bruge den linkede liste.
• Indsættelse i midten: Indsættelse i midten af ​​et array er en kompleks opgave. For du skal skubbe andre elementer til højre. Men en sammenkædet liste giver dig mulighed for at tilføje et element til enhver position, du ønsker.

Operationer af Singly Linked List

Singly Linked List er god til dynamisk allokering af hukommelse. Det giver alle de grundlæggende funktioner for den linkede liste, dvs. indsættelse, sletning, søgning, opdatering, fletning af to linkede lister, krydsning osv.

Her vil vi diskutere følgende betjening af den linkede liste:

• Indføring ved hovedet
• Indføring ved hale
• Indsættelse efter en node
• Indsættelse før en node
• Slet hovedknuden
• Slet haleknuden
• Søg og slet en node
• Gennemgang af den linkede liste

Her er et eksempel på en sammenkædet liste med fire noder.

Indsættelse i spidsen af ​​en enkeltstående liste

Dette er en simpel operation. Generelt er det kendt som at skubbe en enkelt linket liste. Du skal oprette en ny node og placere denne øverst på den sammenkædede liste.

For at udføre denne operation skal vi følge to vigtige betingelser. Det er de

1. Hvis listen er tom, vil den nyoprettede node være hovedknuden, og den næste knude på hovedet vil være ”NULL”.
2. Hvis listen ikke er tom, vil den nye node være hovednoden, og den næste vil pege på den forrige hovedknude.

Her er pseudokoden til at indsætte en node i spidsen af ​​en linket liste:

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

Indsættelse i slutningen af ​​en enkeltstående liste

Indsættelse af en node i slutningen af ​​en sammenkædet liste har nogle ligheder med indsættelse i hovedet. Alt du skal gøre er at gå til endeknuden eller haleknuden. Peg derefter den "næste" knude på slutnoden til den nyoprettede knude. Hvis hovedknuden er nul, vil den nye knude være hovednoden.

Her er trinene:

Trin 1) Kør indtil den "næste" knude på den aktuelle knude bliver nul.

Trin 2) Opret en ny node med den angivne værdi.

Trin 3) Tildel den nye knude som den næste knude på haleknuden.

Pseudokoden til at indsætte en node i halen af ​​en enkelt liste:

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

Indsættelse efter en node i en enkeltforbundet liste

Indsættelse efter en node har to dele: Søg efter noden og vedhæft efter den søgte node. Vi er nødt til at krydse alle knudepunkter. For hver node skal vi matche med søgeelementet. Hvis der er et match, tilføjer vi den nye node efter den søgte node.

Her er trinene:

Trin 1) Gå gennem den næste knude, indtil værdien af ​​den aktuelle knude er lig med søgeelementet.

Trin 2) Ny nodes næste pointer vil være den nuværende nodes næste pointer.

Trin 3) Den nuværende nodes næste node vil være den nye node.

Her er pseudokoden til at indsætte en node efter en node:

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

Indsættelse før en node i en enkeltforbundet liste

Denne funktion minder meget om indsættelsen efter en node. Vi skal oprette en ny node og krydse den linkede liste, indtil den aktuelle node matcher søgenoden. Derefter tilføjer vi den nye node som den forrige node for den nuværende node.

Her er trinene:

Trin 1) Kør indtil den næste nodes værdi er lig med søgeelementet.

Trin 2) Opret en ny node og tildel nodens "næste" med den næste node på den aktuelle node.

Trin 3) Tildel den nye node som den næste node for den aktuelle node.

Her er pseudokoden:

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

Slet hovedet på den enkelt linkede liste

I hver funktion af den lænkede liste er hovedmarkøren angivet som parameter. Du skal slette hovedknudepunktet og gøre det næste knudepunkt i hovedknudepunktet som det nye hoved på den sammenkædede liste. Vi skal også frigøre hukommelsen på den slettede node. Ellers vil hukommelsen blive markeret som optaget, når et andet program forsøger at få adgang til den.

Her er trinene til at slette hovedet på den enkelt-linkede liste:

Trin 1) Tildel den næste knude på hovedknuden som det nye hoved.

Trin 2) Frigør den tildelte hukommelse ved den forrige hovedknude.

Trin 3) Returner den nye hovedknude.

Pseudokoden til sletning af hovedknuden:

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

Slet halen af ​​den enkeltforbundne liste

Sletning af haleknuden er mere bekendt med sletning af hovedknuden. Forskellen er, at vi skal gå til slutningen af ​​den linkede liste og slette den. I den enkeltforbundne liste er noden med den næste node som "NULL" haleknuden.

Her er trinene til at slette haleknuden på den linkede liste:

Trin 1) Kryds før haleknuden. Gem den aktuelle node.

Trin 2) Frigør hukommelsen for den næste node i den aktuelle node.

Trin 3) Indstil den næste node i den aktuelle node som NULL.

Her er pseudokoden til sletning af haleknuden:

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

Søg og slet en node fra en enkelt linket liste

Denne funktion har to opgaver, søg og slet. Vi er nødt til at søge indtil slutningen af ​​de enkeltforbundne lister. Hvis vi finder en lignende node, sletter vi den. Derefter skal vi flette eller sammenkæde venstre og højre noder på den slettede node. Her er trinene til at gøre dette:

Trin 1) Kør indtil slutningen af ​​den sammenkædede liste. Tjek, om den aktuelle node er lig med søgenoden eller ej.

Trin 2) Hvis en node matcher, skal du gemme nodemarkøren til den aktuelle node.

Trin 3) Den "næste" af den forrige knude vil være den næste knude i den aktuelle knude.

Trin 4) Slet og frigør hukommelsen for den aktuelle node.

Pseudo-kode til søgning og sletning af en node fra en enkelt linket liste:

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)

Gennemgå en enkelt linket liste

Enkeltforbundet liste har kun funktionaliteten til at krydse hoved til hale. Der er ingen pointer til den forrige node; det er derfor, vi ikke kan krydse den enkeltstående liste i omvendt rækkefølge. Vi vil krydse hver node og udskrive den aktuelle nodes værdi, indtil vi får null.

Her er trinene:

Trin 1) Gå gennem hver node, indtil vi får null som den næste node.

Trin 2) Udskriv værdien af ​​den aktuelle node.

Pseudo-kode til at krydse en enkelt linket liste:

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

Eksempel på enkeltforbundet liste i 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

Eksempel på enkeltforbundet liste i Python Program

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

Kompleksiteten af ​​enkeltforbundet liste

Der er to slags kompleksitet: tidskompleksitet og rumkompleksitet. Den værste og gennemsnitlige sagstidskompleksitet er den samme for Singly Linked List.

Tidskompleksiteten for den bedste sag:

• Indsættelse i hovedet kan udføres i O(1). Da vi ikke behøver at krydse inde i den linkede liste.
• Søgning og sletning kan udføres i O(1), hvis søgeelementet er til stede i hovedknuden.

Tidskompleksiteten for den gennemsnitlige sag:

• Indsættelse i en sammenkædet liste vil tage O(n), hvis "n" elementer er til stede i den enkeltstående liste.
• Søg og slet kan også tage O(n), da søgeelementet kan være til stede i haleknuden. I så fald bør du gennemgå hele listen.

Rumkompleksiteten af ​​enkeltforbundet liste

Singly Linked List tildeler dynamisk hukommelse. Hvis vi ønsker at gemme n elementer, vil det allokere n hukommelsesenhed. Så rumkompleksiteten er O(n).