Einfach verknüpfte Liste in Datenstrukturen

Was ist eine einfach verknüpfte Liste?

Eine einfach verknüpfte Liste ist eine lineare und unidirektionale Datenstruktur, bei der Daten auf den Knoten gespeichert werden und jeder Knoten über einen Link mit seinem nächsten Knoten verbunden ist. Jeder Knoten enthält ein Datenfeld und einen Link zum nächsten Knoten. Einfach verknüpfte Listen können nur in eine Richtung durchlaufen werden, während doppelt verknüpfte Listen in beide Richtungen durchlaufen werden können.

Hier ist eine Knotenstruktur einer einfach verknüpften Liste:

Struktur eines Knotens in einer verknüpften Liste
Struktur eines Knotens in einer verknüpften Liste

Warum eine verknüpfte Liste anstelle eines Arrays verwenden?

Es gibt mehrere Fälle, in denen es besser ist, die verknüpfte Liste als die zu verwenden Feld. Hier sind einige Szenarien:

  • Unbekannte Anzahl Elemente: Wenn Sie nicht wissen, wie viele Elemente Sie während der Programmlaufzeit speichern müssen, können Sie die verknüpfte Liste verwenden. Der Speicher wird dynamisch zugewiesen, wenn Sie Elemente zu den verknüpften Listen hinzufügen.
  • Zufälliger Zugriff: In einem Szenario, in dem Sie den Direktzugriff der Elemente nicht benötigen, können Sie die verknüpfte Liste verwenden.
  • Einfügung in der Mitte: Das Einfügen in die Mitte eines Arrays ist eine komplexe Aufgabe. Denn Sie müssen andere Elemente nach rechts verschieben. Eine verknüpfte Liste ermöglicht es Ihnen jedoch, ein Element an jeder beliebigen Position hinzuzufügen.

Operationen der einfach verknüpften Liste

Eine einfach verknüpfte Liste eignet sich gut für die dynamische Speicherzuweisung. Sie bietet alle grundlegenden Operationen einer verknüpften Liste, d. h. Einfügen, Löschen, Suchen, Aktualisieren, Zusammenführen zweier verknüpfter Listen, Durchlaufen usw.

Hier besprechen wir die folgende Operation der verknüpften Liste:

  • Am Kopf einstecken
  • Am Schwanz einsteckbar
  • Einfügen nach einem Knoten
  • Einfügen vor einem Knoten
  • Löschen Sie den Hauptknoten
  • Löschen Sie den Endknoten
  • Suchen und löschen Sie einen Knoten
  • Durchlaufen der verknüpften Liste

Hier ist ein Beispiel einer verknüpften Liste mit vier Knoten.

Beispiel einer einfach verknüpften Liste
Beispiel einer einfach verknüpften Liste

Einfügen am Anfang einer einfach verknüpften Liste

Dies ist eine einfache Operation. Im Allgemeinen wird es als Pushen einer einfach verknüpften Liste bezeichnet. Sie müssen einen neuen Knoten erstellen und diesen an den Anfang der verknüpften Liste setzen.

Um diese Operation durchführen zu können, müssen wir zwei wichtige Bedingungen erfüllen. Sie sind

  1. Wenn die Liste leer ist, ist der neu erstellte Knoten der Kopfknoten und der nächste Knoten des Kopfes ist „NULL“.
  2. Wenn die Liste nicht leer ist, ist der neue Knoten der Kopfknoten und der nächste zeigt auf den vorherigen Kopfknoten.

Hier ist der Pseudocode zum Einfügen eines Knotens am Kopf einer verknüpften Liste:

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

Einfügen am Ende einer einfach verknüpften Liste

Das Einfügen eines Knotens am Ende einer verknüpften Liste weist einige Ähnlichkeiten mit dem Einfügen in den Kopf auf. Alles, was Sie tun müssen, ist, zum Endknoten oder zum Endknoten zu wechseln. Zeigen Sie dann mit dem „nächsten“ Knoten des Endknotens auf den neu erstellten Knoten. Wenn der Hauptknoten null ist, ist der neue Knoten der Hauptknoten.

Hier sind die Schritte:

Schritt 1) Durchlaufen, bis der „nächste“ Knoten des aktuellen Knotens null wird.

Schritt 2) Erstellen Sie einen neuen Knoten mit dem angegebenen Wert.

Schritt 3) Weisen Sie den neuen Knoten als nächsten Knoten des Endknotens zu.

Der Pseudocode zum Einfügen eines Knotens am Ende einer Einzelliste:

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
Einsetzen am Schwanz
Einsetzen am Schwanz

Einfügen nach einem Knoten in einer einfach verknüpften Liste

Das Einfügen nach einem Knoten besteht aus zwei Teilen: Suchen nach dem Knoten und Anhängen nach dem gesuchten Knoten. Wir müssen alle Knoten durchlaufen. Für jeden Knoten müssen wir mit dem Suchelement übereinstimmen. Wenn es eine Übereinstimmung gibt, fügen wir den neuen Knoten nach dem gesuchten Knoten hinzu.

Hier sind die Schritte:

Schritt 1) Durchlaufen Sie den nächsten Knoten, bis der Wert des aktuellen Knotens dem Suchelement entspricht.

Schritt 2) Der nächste Zeiger des neuen Knotens ist der nächste Zeiger des aktuellen Knotens.

Schritt 3) Der nächste Knoten des aktuellen Knotens ist der neue Knoten.

Hier ist der Pseudocode zum Einfügen eines Knotens nach einem Knoten:

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
Einfügen eines Knotens nach einem Knoten in einer einfach verknüpften Liste
Einfügen eines Knotens nach einem Knoten in der einfach verknüpften Liste

Einfügen vor einem Knoten in einer einfach verknüpften Liste

Diese Funktion ähnelt stark dem Einfügen nach einem Knoten. Wir müssen einen neuen Knoten erstellen und die verknüpfte Liste durchlaufen, bis der aktuelle Knoten mit dem Suchknoten übereinstimmt. Danach fügen wir den neuen Knoten als vorherigen Knoten des aktuellen Knotens hinzu.

Hier sind die Schritte:

Schritt 1) Durchlaufen, bis der Wert des nächsten Knotens dem Suchelement entspricht.

Schritt 2) Erstellen Sie einen neuen Knoten und weisen Sie den „next“ des Knotens dem nächsten Knoten des aktuellen Knotens zu.

Schritt 3) Weisen Sie den neuen Knoten als nächsten Knoten des aktuellen Knotens zu.

Hier ist der 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
Einfügen eines Knotens vor einem Knoten in einer einfach verknüpften Liste
Einfügen eines Knotens vor einem Knoten in der einfach verknüpften Liste

Löschen Sie den Kopf der einfach verknüpften Liste

In jeder Funktion der verknüpften Liste wird der Kopfzeiger als Parameter bereitgestellt. Sie müssen den Kopfknoten löschen und den nächsten Knoten des Kopfknotens zum neuen Kopf der verknüpften Liste machen. Wir müssen auch den Speicher des gelöschten Knotens freigeben. Andernfalls wird der Speicher als belegt markiert, wenn ein anderes Programm versucht, darauf zuzugreifen.

Hier sind die Schritte zum Löschen des Kopfes der einfach verknüpften Liste:

Schritt 1) Weisen Sie den nächsten Knoten des Kopfknotens als neuen Kopf zu.

Schritt 2) Geben Sie den vom vorherigen Hauptknoten zugewiesenen Speicher frei.

Schritt 3) Geben Sie den neuen Hauptknoten zurück.

Der Pseudocode zum Löschen des Hauptknotens:

function deleteHead( head ):
	temp = head
	head = head.next
	free( temp )
	return head
Löschen des Kopfes einer verknüpften Liste
Den Kopf einer verknüpften Liste löschen

Löschen Sie das Ende der einfach verknüpften Liste

Das Löschen des Endknotens ist mit dem Löschen des Kopfknotens vertrauter. Der Unterschied besteht darin, dass wir zum Ende der verknüpften Liste gehen und sie löschen müssen. In der einfach verknüpften Liste ist der Knoten mit dem nächsten Knoten „NULL“ der Endknoten.

Hier sind die Schritte zum Löschen des Endknotens der verknüpften Liste:

Schritt 1) Vor dem Endknoten durchqueren. Speichern Sie den aktuellen Knoten.

Schritt 2) Geben Sie den Speicher des nächsten Knotens des aktuellen Knotens frei.

Schritt 3) Setzen Sie den nächsten Knoten des aktuellen Knotens auf NULL.

Hier ist der Pseudocode zum Löschen des Endknotens:

function deleteTail( head ):
	while head.next.next is not NULL:
		head = head.next
	free( head.next )
	head.next = NULL
Löschen des Endes der einfach verknüpften Liste
Löschen des Endes der einfach verknüpften Liste

Suchen und löschen Sie einen Knoten aus einer einfach verknüpften Liste

Diese Funktion hat zwei Aufgaben: Suchen und Löschen. Wir müssen bis zum Ende der einfach verknüpften Listen suchen. Wenn wir einen ähnlichen Knoten finden, löschen wir diesen. Danach müssen wir die linken und rechten Knoten des gelöschten Knotens zusammenführen oder verknüpfen. Hier sind die Schritte dazu:

Schritt 1) Durchlaufen Sie bis zum Ende der verknüpften Liste. Überprüfen Sie, ob der aktuelle Knoten mit dem Suchknoten übereinstimmt oder nicht.

Schritt 2) Wenn ein Knoten übereinstimmt, speichern Sie den Knotenzeiger auf den aktuellen Knoten.

Schritt 3) Der „nächste“ des vorherigen Knotens ist der nächste Knoten des aktuellen Knotens.

Schritt 4) Löschen Sie den Speicher des aktuellen Knotens und geben Sie ihn frei.

Pseudocode zum Suchen und Löschen eines Knotens aus einer einfach verknüpften 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)
Suchen und löschen Sie einen Knoten aus der einfach verknüpften Liste
Suchen und löschen Sie einen Knoten aus der einfach verknüpften Liste

Durchlaufen Sie eine einfach verknüpfte Liste

Eine einfach verknüpfte Liste bietet nur die Funktionalität zum Durchlaufen von Kopf bis Ende. Es gibt keine Zeigerpunkte auf den vorherigen Knoten. Aus diesem Grund können wir die einfach verknüpfte Liste nicht in umgekehrter Reihenfolge durchlaufen. Wir durchlaufen jeden Knoten und geben den Wert des aktuellen Knotens aus, bis wir Null erhalten.

Hier sind die Schritte:

Schritt 1) Durchlaufen Sie jeden Knoten, bis wir als nächsten Knoten null erhalten.

Schritt 2) Gibt den Wert des aktuellen Knotens aus.

Pseudocode zum Durchlaufen einer einfach verknüpften Liste:

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

Beispiel einer einfach verketteten Liste 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);
}

Ausgang:

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

Beispiel einer einfach verketteten Liste in Python Mentessa for Good

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()

Ausgang:

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

Komplexität einer einfach verketteten Liste

Es gibt zwei Arten von Komplexität: Zeitkomplexität und Raumkomplexität. Die Zeitkomplexität im schlimmsten und durchschnittlichen Fall ist für die einfach verkettete Liste gleich.

Die Zeitkomplexität für den Best Case:

  • Das Einfügen in den Kopf kann in O(1) erfolgen. Da wir nicht innerhalb der verknüpften Liste durchlaufen müssen.
  • Such- und Löschvorgänge können in O(1) durchgeführt werden, wenn das Suchelement im Kopfknoten vorhanden ist.

Die Zeitkomplexität für den Durchschnittsfall:

  • Das Einfügen in eine verknüpfte Liste erfordert O(n), wenn „n“ Elemente in der einfach verknüpften Liste vorhanden sind.
  • Suchen und Löschen können ebenfalls O(n) annehmen, da das Suchelement im Endknoten vorhanden sein kann. In diesem Fall sollten Sie die gesamte Liste durchlaufen.

Speicherkomplexität einer einfach verketteten Liste

Einfach verknüpfte Listen reservieren dynamisch Speicher. Wenn wir n Elemente speichern möchten, werden n Speichereinheiten reserviert. Die Speicherkomplexität beträgt also O(n).