Enkelvoudig gekoppelde lijst in datastructuren

Wat is een enkelvoudig gekoppelde lijst?

Singly Linked List is een lineaire en unidirectionele datastructuur, waarbij gegevens op de knooppunten worden opgeslagen en elk knooppunt via een link met het volgende knooppunt is verbonden. Elk knooppunt bevat een gegevensveld en een link naar het volgende knooppunt. Enkelvoudig gekoppelde lijsten kunnen in slechts één richting worden doorlopen, terwijl dubbel gekoppelde lijsten in beide richtingen kunnen worden doorlopen.

Hier is een knooppuntstructuur van een enkelvoudig gekoppelde lijst:

Waarom een ​​gekoppelde lijst gebruiken in plaats van een array?

Er zijn verschillende gevallen waarin het beter is om de gekoppelde lijst te gebruiken in plaats van de reeks. Hier zijn enkele scenario's:

• Onbekend aantal elementen: Als u niet weet hoeveel elementen u tijdens de programmalooptijd moet opslaan, kunt u de gekoppelde lijst gebruiken. Geheugen wordt dynamisch toegewezen terwijl u elementen aan de gekoppelde lijsten toevoegt.
• Willekeurige toegang: In een scenario waarin u de willekeurige toegang van de elementen niet hoeft te gebruiken, kunt u de gekoppelde lijst gebruiken.
• Inbrengen in het midden: Invoegen in het midden van een array is een complexe taak. Omdat u andere elementen naar rechts moet duwen. Een gekoppelde lijst stelt u echter in staat om een ​​element toe te voegen aan elke gewenste positie.

Operavan Singly Linked List

Singly Linked List is goed voor het dynamisch toewijzen van geheugen. Het biedt alle basisbewerkingen van de gekoppelde lijst, d.w.z. invoegen, verwijderen, zoeken, bijwerken, twee gekoppelde lijsten samenvoegen, doorkruisen, etc.

Hier bespreken we de volgende werking van de gekoppelde lijst:

• Inbrengen bij het hoofd
• Inbrengen bij de staart
• Invoegen na een knooppunt
• Invoegen vóór een knooppunt
• Verwijder het hoofdknooppunt
• Verwijder het staartknooppunt
• Zoek en verwijder een knooppunt
• De gekoppelde lijst doorlopen

Hier is een voorbeeld van een gekoppelde lijst met vier knooppunten.

Invoeging aan het hoofd van een enkelvoudig gekoppelde lijst

Dit is een eenvoudige handeling. Over het algemeen staat het bekend als het pushen van een enkelvoudig gekoppelde lijst. U moet een nieuw knooppunt maken en dit bovenaan de gekoppelde lijst plaatsen.

Om deze bewerking uit te voeren, moeten we aan twee belangrijke voorwaarden voldoen. Ze zijn

1. Als de lijst leeg is, zal het nieuw aangemaakte knooppunt het hoofdknooppunt zijn, en het volgende knooppunt van het hoofd zal "NULL" zijn.
2. Als de lijst niet leeg is, is het nieuwe knooppunt het hoofdknooppunt en verwijst het volgende naar het vorige hoofdknooppunt.

Hier is de pseudocode voor het invoegen van een knooppunt aan het hoofd van een gekoppelde lijst:

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

Invoeging aan het einde van een enkelvoudig gekoppelde lijst

Het invoegen van een knooppunt aan het einde van een gekoppelde lijst heeft enkele overeenkomsten met het invoegen in de kop. Het enige wat u hoeft te doen is naar het eindknooppunt of het staartknooppunt te gaan. Wijs vervolgens het “volgende” knooppunt van het eindknooppunt naar het nieuw gemaakte knooppunt. Als het hoofdknooppunt nul is, is het nieuwe knooppunt het hoofdknooppunt.

Dit zijn de stappen:

Stap 1) Beweeg totdat het “volgende” knooppunt van het huidige knooppunt nul wordt.

Stap 2) Maak een nieuw knooppunt met de opgegeven waarde.

Stap 3) Wijs het nieuwe knooppunt toe als het volgende knooppunt van het staartknooppunt.

De pseudocode voor het invoegen van een knooppunt aan de staart van een afzonderlijke lijst:

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

Invoeging na een knooppunt in een Singly Linked List

Invoegen na een knooppunt bestaat uit twee delen: zoeken naar het knooppunt en koppelen na het gezochte knooppunt. We moeten alle knooppunten doorkruisen. Voor elk knooppunt moeten we matchen met het zoekelement. Als er een overeenkomst is, voegen we het nieuwe knooppunt toe na het gezochte knooppunt.

Dit zijn de stappen:

Stap 1) Doorkruis het volgende knooppunt totdat de waarde van het huidige knooppunt gelijk is aan het zoekitem.

Stap 2) De volgende aanwijzer van het nieuwe knooppunt zal de volgende aanwijzer van het huidige knooppunt zijn.

Stap 3) Het volgende knooppunt van het huidige knooppunt zal het nieuwe knooppunt zijn.

Hier is de pseudocode voor het invoegen van een knooppunt na een knooppunt:

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

Invoeging vóór een knooppunt in een Singly Linked List

Deze functie lijkt veel op het invoegen na een knooppunt. We moeten een nieuw knooppunt maken en de gekoppelde lijst doorkruisen totdat het huidige knooppunt overeenkomt met het zoekknooppunt. Daarna zullen we het nieuwe knooppunt toevoegen als het vorige knooppunt van het huidige knooppunt.

Dit zijn de stappen:

Stap 1) Ga door totdat de waarde van het volgende knooppunt gelijk is aan het zoekitem.

Stap 2) Maak een nieuw knooppunt en wijs de “volgende” van het knooppunt toe aan het volgende knooppunt, naast het volgende knooppunt van het huidige knooppunt.

Stap 3) Wijs het nieuwe knooppunt toe als het volgende knooppunt van het huidige knooppunt.

Hier is de pseudocode:

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

Verwijder de kop van de enkelvoudig gekoppelde lijst

In elke functie van de gekoppelde lijst wordt de head pointer als parameter geleverd. U moet de head node verwijderen en de volgende node van de head node als de nieuwe head van de gekoppelde lijst maken. We moeten ook het geheugen van de verwijderde node vrijmaken. Anders wordt het geheugen gemarkeerd als bezet wanneer een ander programma er toegang toe probeert te krijgen.

Hier volgen de stappen voor het verwijderen van de kop van de enkelvoudig gekoppelde lijst:

Stap 1) Wijs het volgende knooppunt van het hoofdknooppunt toe als het nieuwe hoofd.

Stap 2) Maak het toegewezen geheugen vrij door het vorige hoofdknooppunt.

Stap 3) Retourneer het nieuwe hoofdknooppunt.

De pseudocode voor het verwijderen van het hoofdknooppunt:

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

Verwijder de staart van de afzonderlijk gekoppelde lijst

Het verwijderen van het staartknooppunt is meer bekend met het verwijderen van het hoofdknooppunt. Het verschil is dat we naar het einde van de gekoppelde lijst moeten gaan en deze moeten verwijderen. In de enkelvoudig gekoppelde lijst is het knooppunt met het volgende knooppunt als “NULL” het staartknooppunt.

Hier volgen de stappen voor het verwijderen van het staartknooppunt van de gekoppelde lijst:

Stap 1) Beweeg vóór het staartknooppunt. Sla het huidige knooppunt op.

Stap 2) Maak het geheugen vrij van het volgende knooppunt van het huidige knooppunt.

Stap 3) Stel het volgende knooppunt van het huidige knooppunt in als NULL.

Hier is de pseudocode voor het verwijderen van het staartknooppunt:

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

Zoek en verwijder een knooppunt uit een enkelvoudig gekoppelde lijst

Deze functie heeft twee taken: zoeken en verwijderen. We moeten zoeken tot het einde van de afzonderlijk gekoppelde lijsten. Als we een vergelijkbaar knooppunt vinden, zullen we dat verwijderen. Daarna moeten we de linker- en rechterknooppunten van het verwijderde knooppunt samenvoegen of koppelen. Hier zijn de stappen om dit te doen:

Stap 1) Doorloop tot het einde van de gekoppelde lijst. Controleer of het huidige knooppunt gelijk is aan het zoekknooppunt of niet.

Stap 2) Als een knooppunt overeenkomt, slaat u de knooppuntwijzer naar het huidige knooppunt op.

Stap 3) De “volgende” van het vorige knooppunt zal het volgende knooppunt van het huidige knooppunt zijn.

Stap 4) Verwijder het geheugen van het huidige knooppunt en maak het vrij.

Pseudocode voor het zoeken en verwijderen van een knooppunt uit een enkelvoudig gekoppelde lijst:

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)

Doorkruis een enkelvoudig gekoppelde lijst

Enkelvoudig gekoppelde lijst heeft alleen de functionaliteit voor het doorlopen van kop tot staart. Er zijn geen verwijzingspunten naar het vorige knooppunt; daarom kunnen we de Singly Linked List niet in omgekeerde volgorde doorkruisen. We zullen elk knooppunt doorlopen en de waarde van het huidige knooppunt afdrukken totdat we nul krijgen.

Dit zijn de stappen:

Stap 1) Doorkruis elk knooppunt totdat we nul krijgen als het volgende knooppunt.

Stap 2) Druk de waarde van het huidige knooppunt af.

Pseudocode voor het doorkruisen van een enkelvoudig gekoppelde lijst:

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

Voorbeeld van een enkelvoudig gekoppelde lijst in 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

Voorbeeld van een enkelvoudig gekoppelde lijst in Python Programma

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

Complexiteit van enkelvoudig gekoppelde lijst

Er zijn twee soorten complexiteit: tijdscomplexiteit en ruimtecomplexiteit. De slechtste en gemiddelde tijdscomplexiteit is hetzelfde voor de Singly Linked List.

De tijdcomplexiteit voor het beste geval:

• Inbrengen in het hoofd kan in O(1). Omdat we niet binnen de gekoppelde lijst hoeven te bladeren.
• Zoek- en verwijderbewerkingen kunnen worden uitgevoerd in O(1) als het zoekelement aanwezig is in het hoofdknooppunt.

De tijdcomplexiteit voor het gemiddelde geval:

• Voor het invoegen in een gekoppelde lijst is O(n) nodig als er “n”-elementen aanwezig zijn in de enkelvoudig gekoppelde lijst.
• Zoeken en verwijderen kan ook O(n) vereisen, omdat het zoekelement aanwezig kan zijn in het staartknooppunt. In dat geval moet u de hele lijst doorlopen.

Ruimtecomplexiteit van enkelvoudig gekoppelde lijst

Enkelvoudig gekoppelde lijst wijst dynamisch geheugen toe. Als we n elementen willen opslaan, zal het n geheugeneenheid toewijzen. Dus de ruimtecomplexiteit is O(n).