Enkelvoudig gekoppelde lijst in datastructuren

Wat is een enkelvoudig gekoppelde lijst?

Een enkelvoudig gekoppelde lijst is een lineaire en unidirectionele datastructuur waarbij gegevens worden opgeslagen in de knooppunten en elk knooppunt via een link is verbonden met het volgende knooppunt. Elk knooppunt bevat een gegevensveld en een link naar het volgende knooppunt. Enkelvoudig gekoppelde lijsten kunnen slechts in één richting worden doorlopen, terwijl een meervoudig gekoppelde lijst dat niet kan. Dubbel gelinkte lijst kan in beide richtingen worden doorkruist.

Hieronder ziet u de knoopstructuur van een enkelvoudig gekoppelde lijst:

Structuur van een knooppunt in een gekoppelde lijst

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

In verschillende scenario's is een gekoppelde lijst (Linked List) geschikter dan een reeks:

• Onbekend aantal elementen: Wanneer het benodigde aantal elementen niet bekend is tijdens het compileren, wijst een gekoppelde lijst dynamisch geheugen toe naarmate er elementen worden toegevoegd.
• Willekeurige toegang: Wanneer willekeurige toegang via een index niet nodig is, is een gekoppelde lijst een geschikte keuze.
• Inbrengen in het midden: Het invoegen van een element midden in een array vereist het verschuiven van elementen. Een gekoppelde lijst maakt invoegen op elke gewenste positie mogelijk door slechts enkele pointers te herschrijven.

Operavan Singly Linked List

Een enkelvoudig gekoppelde lijst is geschikt voor dynamische geheugenallocatie. Het ondersteunt de standaardbewerkingen van een gekoppelde lijst, zoals invoegen, verwijderen, zoeken, bijwerken, het samenvoegen van twee lijsten en het doorlopen van de lijst.

In dit artikel worden de volgende bewerkingen besproken:

• 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.

Voorbeeld van een enkelvoudig gekoppelde lijst

Invoegen aan het begin van een enkelvoudig gekoppelde lijst

Dit is een eenvoudige bewerking. Het wordt over het algemeen 'toevoegen aan een enkelvoudig gekoppelde lijst' genoemd. Er wordt een nieuw knooppunt aangemaakt en aan het begin van de lijst geplaatst.

Om deze bewerking uit te voeren, moet u aan twee belangrijke voorwaarden voldoen:

1. Als de lijst leeg is, wordt het nieuw gecreëerde knooppunt het hoofdknooppunt en zijn volgende De aanwijzer is NULL.
2. Als de lijst niet leeg is, wordt het nieuwe knooppunt het hoofdknooppunt en zijn volgende De aanwijzer wijst naar het vorige hoofdknooppunt.

Hieronder staat de pseudocode voor het invoegen van een knooppunt aan het begin 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

Inbrengen bij het hoofd

Invoegen aan het einde van een enkelvoudig gekoppelde lijst

Het invoegen van een knooppunt aan het einde van een gekoppelde lijst is vergelijkbaar met het invoegen aan het begin. Navigeer naar het eindknooppunt en wijs vervolgens naar het betreffende knooppunt. volgende Een aanwijzer naar het nieuwe knooppunt. Als de kop NULL is, wordt het nieuwe knooppunt de kop.

Stap 1) Ga verder tot de volgende De pointer naar het huidige knooppunt wordt NULL.

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 aan het einde van een lijst met afzonderlijke elementen:

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

Inbrengen bij de staart

Invoegen na een knooppunt in een enkelvoudig gekoppelde lijst

Het invoegen na een knooppunt bestaat uit twee delen: het zoeken naar het doelknooppunt en het toevoegen van een nieuw knooppunt erna. Doorloop de lijst totdat een overeenkomst is gevonden en voeg vervolgens het nieuwe knooppunt in.

Stap 1) Doorloop de knooppunten totdat de waarde van het huidige knooppunt gelijk is aan het zoekitem.

Stap 2) Stel de nieuwe node in volgende aanwijzer naar het huidige knooppunt volgende wijzer.

Stap 3) Wijs naar het huidige knooppunt volgende aanwijzer naar het nieuwe knooppunt.

Pseudocode:

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

Een knooppunt invoegen na een knooppunt in de Singly Linked List

Invoegen vóór een knooppunt in een enkelvoudig gekoppelde lijst

Dit is vergelijkbaar met het invoegen na een knooppunt. Doorloop de lus totdat het volgende knooppunt overeenkomt met de zoekwaarde en voeg vervolgens het nieuwe knooppunt ervoor in.

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

Stap 2) Maak een nieuw knooppunt aan en stel de volgende instellingen in: volgende aanwijzer naar het huidige knooppunt volgende.

Stap 3) Wijs naar het huidige knooppunt volgende naar het nieuwe knooppunt.

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

Een knooppunt invoegen vóór een knooppunt in de Singly Linked List

Verwijder het hoofd van de enkelvoudig gekoppelde lijst.

De pointer naar het hoofdknooppunt wordt als parameter meegegeven. Het hoofdknooppunt wordt verwijderd en het volgende knooppunt wordt het nieuwe hoofdknooppunt. Het geheugen van het verwijderde knooppunt moet worden vrijgegeven om geheugenlekken te voorkomen.

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

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

Stap 3) Retourneer het nieuwe hoofdknooppunt.

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

De kop van een gekoppelde lijst verwijderen

Verwijder het einde van de enkelvoudig gekoppelde lijst

Het verwijderen van het eindknooppunt is vergelijkbaar met het verwijderen van het beginknooppunt. Het verschil is dat er tot het einde van de lijst moet worden doorgelopen. In een enkelvoudig gekoppelde lijst is het knooppunt waarvan het eindknooppunt zich bevindt het knooppunt waarvan het eindknooppunt zich bevindt het eindknooppunt. volgende Als de aanwijzer NULL is, bevindt deze zich in het eindknooppunt.

Stap 1) Doorloop de route tot vlak voor het eindknooppunt. Sla het huidige knooppunt op.

Stap 2) Maak het geheugen van het volgende knooppunt (de staart) vrij.

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

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

Het verwijderen van de staart van de Singly Linked List

Een knooppunt zoeken en verwijderen uit een enkelvoudig gekoppelde lijst.

Deze functie voert twee taken uit: zoeken en verwijderen. Doorloop de lijst tot het einde. Als een overeenkomend knooppunt wordt gevonden, verwijder het dan en koppel het vorige knooppunt opnieuw. volgende wijzer.

Stap 1) Doorloop de lijst tot het einde. Controleer of het huidige knooppunt gelijk is aan het gezochte knooppunt.

Stap 2) Als er een overeenkomst wordt gevonden, sla dan een verwijzing naar het huidige knooppunt op.

Stap 3) De volgende Het knooppunt van het vorige knooppunt wordt het volgende knooppunt van het huidige knooppunt.

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

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)

Zoek en verwijder een knooppunt uit de Singly Linked List

Een enkelvoudig gekoppelde lijst doorlopen

Een enkelvoudig gekoppelde lijst ondersteunt alleen doorloop van kop naar staart. Er is geen verwijzing naar het vorige knooppunt, dus doorloop in omgekeerde richting is niet mogelijk. Elk knooppunt wordt achtereenvolgens bezocht en de waarde ervan wordt afgedrukt totdat NULL wordt bereikt.

Stap 1) Doorloop elk knooppunt totdat NULL wordt bereikt.

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

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

uitgang

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

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

uitgang

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 bestaan ​​twee soorten complexiteit: tijdscomplexiteit en ruimtecomplexiteit. De tijdscomplexiteit in het slechtste en gemiddelde geval is gelijk voor een enkelvoudig gekoppelde lijst.

Tijdcomplexiteit in het beste geval:

• Invoegen aan het begin kan in O(1) worden gedaan. Er is geen doorloop van de lijst nodig.
• Zoeken en verwijderen kan in O(1) tijd als het doelelement zich in het hoofdknooppunt bevindt.

Gemiddelde tijdcomplexiteit:

• Invoegen in een gekoppelde lijst kost O(n), waarbij n is het totale aantal elementen.
• Zoeken en verwijderen kan ook O(n) tijd kosten, omdat het doelelement zich overal tot aan het eindknooppunt kan bevinden.

Ruimtecomplexiteit van een enkelvoudig gekoppelde lijst

Een enkelvoudig gekoppelde lijst wijst dynamisch geheugen toe. Om gegevens op te slaan n elementen, het wijst toe n geheugeneenheden. De ruimtecomplexiteit is dus O(n).

Toepassingen van enkelvoudig gekoppelde lijsten

Enkelvoudig gekoppelde lijsten komen op veel plaatsen voor waar alleen voorwaartse traversering en dynamisch geheugen nuttig zijn:

• Stapels en wachtrijen: Onderliggende opslag voor LIFO-stacks en FIFO-wachtrijen die zijn opgebouwd uit knooppunten.
• Hash-tabelkoppeling: Botsingen worden opgelost door items per bucket aan elkaar te koppelen in een enkelvoudig gekoppelde lijst.
• Aangrenzende lijsten: Bij dunne grafieken wordt voor elk knooppunt een enkelvoudig gekoppelde lijst van buren gebruikt.
• Symbolentabellen: Compilers en interpreters koppelen identificatoren per bereik aan elkaar tot een enkelvoudig gekoppelde lijst.
• Geheugenallocators: Toewijzing van vrije lijsten track vrije blokken als een enkelvoudig gekoppelde lijst.

Veelgestelde vragen