Einfach verknüpfte Liste in Datenstrukturen

Was ist eine einfach verknüpfte Liste?

Eine einfach verkettete Liste ist eine lineare und unidirektionale Datenstruktur, in 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 verkettete Listen können nur in eine Richtung durchlaufen werden, während eine unidirektionale Liste Doppelt verknüpfte Liste kann in beide Richtungen durchquert werden.

Hier ist die Knotenstruktur einer einfach verketteten Liste:

Struktur eines Knotens in einer verknüpften Liste

Warum sollte man eine verkettete Liste einem Array vorziehen?

In einigen Szenarien ist eine verkettete Liste besser geeignet als eine Feld:

• Unbekannte Anzahl Elemente: Wenn die erforderliche Anzahl an Elementen zur Kompilierzeit nicht bekannt ist, allokiert eine verkettete Liste den Speicher dynamisch, sobald Elemente hinzugefügt werden.
• Zufälliger Zugriff: Wenn kein wahlfreier Indexzugriff erforderlich ist, ist eine verkettete Liste eine geeignete Wahl.
• Einfügung in der Mitte: Das Einfügen in die Mitte eines Arrays erfordert das Verschieben von Elementen. Eine verkettete Liste ermöglicht das Einfügen an jeder beliebigen Position, indem nur wenige Zeiger neu geschrieben werden.

Operationen der einfach verknüpften Liste

Eine einfach verkettete Liste eignet sich gut für die dynamische Speicherverwaltung. Sie unterstützt die Standardoperationen einer verketteten Liste, d. h. Einfügen, Löschen, Suchen, Aktualisieren, Zusammenführen zweier Listen und Traversieren.

In diesem Artikel werden folgende Vorgänge behandelt:

• 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 verketteten Liste mit vier Knoten.

Beispiel einer einfach verknüpften Liste

Einfügen am Anfang einer einfach verketteten Liste

Dies ist ein einfacher Vorgang. Er wird allgemein als „Hineinfügen“ in eine einfach verkettete Liste bezeichnet. Dabei wird ein neuer Knoten erstellt und an den Anfang der Liste gesetzt.

Für die Durchführung dieser Operation müssen zwei wichtige Bedingungen erfüllt sein:

1. Wenn die Liste leer ist, wird der neu erstellte Knoten zum Kopfknoten, und seine weiter Der Zeiger ist NULL.
2. Wenn die Liste nicht leer ist, wird der neue Knoten zum Kopfknoten und sein weiter Der Zeiger verweist auf den vorherigen Kopfknoten.

Hier ist der Pseudocode zum Einfügen eines Knotens am Anfang einer verketteten 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

Einfügen am Ende einer einfach verketteten Liste

Das Einfügen eines Knotens am Ende einer verketteten Liste ähnelt dem Einfügen am Anfang. Man durchläuft die Liste bis zum letzten Knoten und verweist dann auf dessen Zielknoten. weiter Zeiger auf den neuen Knoten. Wenn der Kopf NULL ist, wird der neue Knoten zum Kopf.

Schritt 1) Durchquere die Strecke bis zum weiter Der Zeiger des aktuellen Knotens wird zu NULL.

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 am Ende einer einfachen Liste:

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

Einsetzen am Schwanz

Einfügen nach einem Knoten in einer einfach verketteten Liste

Das Einfügen nach einem Knoten besteht aus zwei Schritten: Zuerst wird der Zielknoten gesucht und anschließend ein neuer Knoten daran angehängt. Die Liste wird durchlaufen, bis eine Übereinstimmung gefunden wird; dann wird der neue Knoten eingefügt.

Schritt 1) Durchlaufe die Liste, bis der Wert des aktuellen Knotens dem Suchwert entspricht.

Schritt 2) Setzen Sie die Einstellungen des neuen Knotens weiter Zeiger auf den aktuellen Knoten weiter Zeiger.

Schritt 3) Zeigen Sie auf den aktuellen Knoten weiter Zeiger auf den neuen Knoten.

Pseudocode:

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

Einfügen eines Knotens nach einem Knoten in der einfach verknüpften Liste

Einfügen vor einem Knoten in einer einfach verketteten Liste

Dies ähnelt dem Einfügen nach einem Knoten. Durchlaufe die Suche, bis der nächste Knoten dem Suchwert entspricht, und füge dann den neuen Knoten davor ein.

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

Schritt 2) Erstelle einen neuen Knoten und lege seine Eigenschaften fest. weiter Zeiger auf den aktuellen Knoten weiter.

Schritt 3) Zeigen Sie auf den aktuellen Knoten weiter zum neuen Knoten.

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

Einfügen eines Knotens vor einem Knoten in der einfach verknüpften Liste

Löschen Sie den Kopf der einfach verketteten Liste

Der Kopfzeiger wird als Parameter übergeben. Der Kopfknoten wird entfernt, und der nächste Knoten wird zum neuen Kopfknoten. Der Speicher des gelöschten Knotens muss freigegeben werden, um Speicherlecks zu vermeiden.

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

Schritt 2) Den vom vorherigen Kopfknoten belegten Speicher freigeben.

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

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

Den Kopf einer verknüpften Liste löschen

Lösche das Ende der einfach verketteten Liste

Das Löschen des letzten Knotens ähnelt dem Löschen des ersten Knotens. Der Unterschied besteht darin, dass die Liste bis zum Ende durchlaufen werden muss. In einer einfach verketteten Liste ist der Knoten, dessen weiter Der Zeiger ist NULL und befindet sich am Ende des Knotens.

Schritt 1) Durchlaufe den Pfad bis kurz vor den Endknoten. Speichere den aktuellen Knoten.

Schritt 2) Den Speicher des nächsten Knotens (des Endes) freigeben.

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

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

Einen Knoten aus einer einfach verketteten Liste suchen und löschen

Diese Funktion führt zwei Aufgaben aus: Suchen und Löschen. Sie durchläuft die Liste bis zum Ende. Wird ein passender Knoten gefunden, wird dieser entfernt und der vorherige Knoten neu verknüpft. weiter Zeiger.

Schritt 1) Durchlaufe die Liste bis zum Ende. Prüfe, ob der aktuelle Knoten mit dem Suchknoten übereinstimmt.

Schritt 2) Wird eine Übereinstimmung gefunden, wird ein Zeiger auf den aktuellen Knoten gespeichert.

Schritt 3) Das weiter Der vorherige Knoten wird zum nächsten Knoten des aktuellen Knotens.

Schritt 4) Löschen Sie den aktuellen Knoten und geben Sie seinen Speicher frei.

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)

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

Durchlaufen einer einfach verketteten Liste

Eine einfach verkettete Liste unterstützt nur die Traversierung vom Anfang zum Ende. Es gibt keinen Zeiger auf den vorherigen Knoten, daher ist eine umgekehrte Traversierung nicht möglich. Jeder Knoten wird der Reihe nach besucht und sein Wert ausgegeben, bis NULL erreicht wird.

Schritt 1) Durchlaufe jeden Knoten, bis NULL erreicht wird.

Schritt 2) Gibt den Wert des aktuellen Knotens aus.

function traverse(head):
  while head is not NULL:
    print head.value
    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);
    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);
}

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

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

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 Speicherkomplexität. Die Zeitkomplexität im schlechtesten und im durchschnittlichen Fall ist für eine einfach verkettete Liste gleich.

Zeitkomplexität im besten Fall:

• Das Einfügen am Anfang kann in O(1) erfolgen. Es ist kein Durchlauf innerhalb der Liste erforderlich.
• Suchen und Löschen kann in O(1) erfolgen, wenn sich das Zielelement am Kopfknoten befindet.

Durchschnittliche Zeitkomplexität:

• Das Einfügen in eine verkettete Liste benötigt O(n), wobei n ist die Gesamtzahl der Elemente.
• Suchen und Löschen kann auch O(n) dauern, da sich das Zielelement an jeder beliebigen Stelle bis zum letzten Knoten befinden kann.

Speicherkomplexität einer einfach verketteten Liste

Eine einfach verkettete Liste allokiert dynamisch Speicher. Zum Speichern n Elemente, die es zuweist n Speichereinheiten. Die Speicherkomplexität beträgt also O(n).

Anwendungen von einfach verketteten Listen

Einfach verkettete Listen kommen an vielen Stellen vor, wo Vorwärtstraversierung und dynamischer Speicher nützlich sind:

• Stapel und Warteschlangen: Zugrundeliegender Speicher für LIFO-Stapel und FIFO-Warteschlangen, die aus Knoten aufgebaut sind.
• Hash-Tabellenverkettung: Kollisionen werden durch Verkettung der Einträge in einer einfach verketteten Liste pro Bucket aufgelöst.
• Adjazenzlisten: Bei dünn besetzten Graphen wird für jeden Knoten eine einfach verkettete Liste von Nachbarn verwendet.
• Symboltabellen: Compiler und Interpreter ordnen Bezeichner pro Gültigkeitsbereich in einer einfach verketteten Liste an.
• Speicherallokatoren: Freilistenverteiler track freie Blöcke als einfach verkettete Liste.

Häufig gestellte Fragen