Enkeltforbundet liste i datastrukturer

Hvad er en enkeltstående liste?

En enkeltstående linket liste er en lineær og ensrettet datastruktur, hvor data gemmes på noderne, og hver node er forbundet via et link til sin næste node. Hver node indeholder et datafelt og et link til den næste node. Enkeltstående linkede lister kan kun gennemløbes i én retning, hvorimod en Dobbeltforbundet liste kan gennemkøres i begge retninger.

Her er nodestrukturen for en enkeltstående linket liste:

Struktur af en node i en sammenkædet liste

Hvorfor bruge en linket liste frem for et array?

Flere scenarier favoriserer en linket liste frem for en Array:

• Ukendt antal elementer: Når det nødvendige antal elementer ikke er kendt på kompileringstidspunktet, allokerer en linket liste hukommelse dynamisk, efterhånden som elementer tilføjes.
• Tilfældig adgang: Når tilfældig indekseret adgang ikke er nødvendig, er en linket liste et passende valg.
• Indsættelse i midten: Indsættelse midt i et array kræver forskydning af elementer. En linket liste tillader indsættelse på en hvilken som helst position ved kun at omskrive et par pointere.

Operationer af Singly Linked List

En enkeltstående linket liste er god til dynamisk allokering af hukommelse. Den understøtter standardoperationerne for den linkede liste, dvs. indsættelse, sletning, søgning, opdatering, sammenlægning af to lister og gennemgang.

Følgende operationer diskuteres i denne artikel:

• 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 linket liste med fire noder.

Eksempel på en enkeltstående liste

Indsættelse i toppen af ​​en enkeltstående linket liste

Dette er en simpel operation. Det er generelt kendt som at pushe til en enkeltstående linket liste. En ny node oprettes og placeres øverst på listen.

For at udføre denne operation skal du følge to vigtige betingelser:

1. Hvis listen er tom, bliver den nyoprettede node hovednoden, og dens næste pointeren er NULL.
2. Hvis listen ikke er tom, bliver den nye node hovednoden, og dens næste Markøren peger på den forrige hovedknude.

Her er pseudokoden til at indsætte en node i toppen 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 ved hovedet

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

Indsættelse af en node i slutningen af ​​en linket liste svarer til at indsætte i toppen. Gå til den bageste node, og peg derefter dens næste pegeren til den nye node. Hvis head er NULL, bliver den nye node til head.

Trin 1) Gennemgå indtil næste Pointeren for den aktuelle node bliver NULL.

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 indsættelse i slutningen 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:
    head = head.next
  head.next = newNode
  newNode.next = NULL

Indføring ved halen

Indsættelse efter en node i en enkeltstående linket liste

Indsættelse efter en node har to dele: søg efter målnoden og tilføj en ny node efter den. Gennemgå listen, indtil der findes et match, og splejs derefter den nye node ind.

Trin 1) Gennemgå indtil værdien af ​​den aktuelle node er lig med søgeelementet.

Trin 2) Indstil den nye nodes næste peger til den aktuelle nodes næste markør.

Trin 3) Peg på den nuværende nodes næste pegeren til den nye node.

Pseudokode:

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

Indsættelse af en node efter en node i Singly Linked List

Indsættelse før en node i en enkeltstående linket liste

Dette svarer til indsættelse efter en node. Gå gennem søgefeltet, indtil den næste node matcher søgeværdien, og indsæt derefter den nye node før den.

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

Trin 2) Opret en ny node og indstil dens næste peger til den aktuelle nodes næste.

Trin 3) Peg på den nuværende nodes næste til den nye node.

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

Indsættelse af en node før en node i Singly Linked List

Slet overskriften på den enkeltvis sammenkædede liste

Hovedpointen angives som parameter. Hovednoden fjernes, og den næste node bliver den nye hovednode. Hukommelsen for den slettede node skal frigøres for at undgå hukommelseslækager.

Trin 1) Tildel den næste node i hovedet som det nye hoved.

Trin 2) Frigør den allokerede hukommelse fra den forrige head node.

Trin 3) Returner den nye hovedknude.

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

Sletning af hovedet på en linket liste

Slet halen af ​​den enkeltvis sammenkædede liste

Sletning af halenoden svarer til sletning af hovednoden. Forskellen er, at det er nødvendigt at gå til slutningen af ​​listen. I en enkeltstående linket liste er den node, hvis næste pointeren er NULL er haleknuden.

Trin 1) Gå indtil lige før haleknuden. Gem den aktuelle node.

Trin 2) Frigør hukommelsen til den næste node (halen).

Trin 3) Sæt den næste node i den aktuelle node til NULL.

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

Sletning af halen af ​​enkeltforbundet liste

Søg og slet en node fra en enkeltstående linket liste

Denne funktion udfører to opgaver: søgning og sletning. Naviger til slutningen af ​​listen. Hvis der findes en matchende node, skal du fjerne den og linke den forrige nodes sammen igen. næste markør.

Trin 1) Gå til slutningen af ​​listen. Kontroller, om den aktuelle node er lig med søgenoden.

Trin 2) Hvis der findes et match, gemmes en pointer til den aktuelle node.

Trin 3) næste for den forrige node bliver den næste node for den nuværende node.

Trin 4) Slet den aktuelle node og frigør dens hukommelse.

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)

Søg og slet en node fra Liste med enkelt lænker

Gennemgå en enkeltstående linket liste

En enkeltstående linket liste understøtter kun gennemgang fra top til hale. Der er ingen pointer til den forrige node, så omvendt gennemgang er ikke mulig. Hver node besøges efter tur, og dens værdi udskrives, indtil NULL nås.

Trin 1) Gennemløb hver node, indtil NULL er nået.

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

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

Produktion

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

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

Produktion

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 typer kompleksitet: tidskompleksitet og rumkompleksitet. Den værste og gennemsnitlige tidskompleksitet er den samme for en enkeltstående linket liste.

Bedste-case tidskompleksitet:

• Indsættelse ved toppen kan udføres i O(1). Ingen gennemgang inden for listen er nødvendig.
• Søgning og sletning kan udføres i O(1), hvis målelementet er ved hovednoden.

Gennemsnitlig sagstidskompleksitet:

• Indsættelse i en linket liste kræver O(n), hvor n er det samlede antal elementer.
• Søgning og sletning kan også tage O(n), fordi målelementet kan befinde sig hvor som helst op til haleknuden.

Rumkompleksitet af enkelttilknyttede lister

En enkeltstående linket liste allokerer dynamisk hukommelse. For at gemme n elementer, den allokerer n hukommelsesenheder. Så rumkompleksiteten er O(n).

Anvendelser af enkeltstående linkede lister

Enkeltforbundne lister vises mange steder, hvor kun fremadrettet gennemgang og dynamisk hukommelse er nyttige:

• Stakke og køer: Underliggende lagring til LIFO-stakke og FIFO-køer bygget fra noder.
• Hash-tabelkæde: Kollisioner løses ved at kæde poster sammen i en enkeltstående linket liste pr. bucket.
• Nærliggende lister: Sparse grafer bruger en enkeltstående linket liste over naboer for hvert hjørne.
• Symboltabeller: Compilere og fortolkere kæder identifikatorer sammen til en enkeltstående linket liste pr. scope.
• Hukommelsesallokatorer: Gratislistetildelere track frie blokke som en enkeltstående linket liste.

Ofte Stillede Spørgsmål