Enkeltkoblet liste i datastrukturer

by: Sarah Chen Sarah Chen
Hours oppdatert

⚡ Smart oppsummering

En enkeltlenket liste er en lineær, ensrettet datastruktur der hver node lagrer data og en enkelt peker til den neste noden, slik at traverseringen bare beveger seg fra topp til hale og minne allokeres dynamisk etter hvert som nye noder legges til.

  • 🧩 Nodestruktur: Hver node inneholder ett datafelt og ett neste pekeren til den følgende noden; halenodens neste pekeren er NULL.
  • 📦 Liste vs. array: Enkeltlenkede lister foretrekkes når elementantallet er ukjent, tilfeldig tilgang ikke er nødvendig, og innsetting midt i listen er vanlig.
  • ➕ Innsettinger: Noder kan legges til ved hodet, ved halen, etter en matchet node eller før en matchet node ved hjelp av omskrivninger av neste peker.
  • ➖ Slettinger: Hvis du fjerner hodet, halen eller en søkt node, oppdateres nabopekere og frigjør det frigjorte minnet for å unngå lekkasjer.
  • 🔁 Gjennomgang: Bare fremovergående traversering støttes fordi det ikke finnes noen tidligere peker, så det er ikke mulig å gå bakover i en enkeltlenket liste.
  • 💻 C++ og Python Code: Komplette implementeringer viser rutiner for innsetting, sletting, søk og gjennomgang med kjørbar utdata.
  • 📊 kompleksitet: Innsetting eller sletting av hode er O(1); søk og andre innsettinger og slettinger er O(n); romkompleksitet er O(n).
Les mer

Enkeltlenket liste

Hva er en enkeltkoblet liste?

En enkeltlenket liste er en lineær og enveis datastruktur der data lagres på nodene, og hver node er koblet til sin neste node via en lenke. Hver node inneholder et datafelt og en lenke til den neste noden. Enkeltlenkede lister kan bare navigeres i én retning, mens en Dobbeltkoblet liste kan krysses i begge retninger.

Her er nodestrukturen til en enkeltkoblet liste:

Strukturen til en node i en koblet liste

Strukturen til en node i en koblet liste

Hvorfor bruke en lenket liste over en array?

Flere scenarier favoriserer en lenket liste fremfor en Array:

  • Ukjent antall elementer: Når det nødvendige elementantallet ikke er kjent ved kompileringstidspunktet, tildeler en lenket liste minne dynamisk etter hvert som elementer legges til.
  • Tilfeldig tilgang: Når tilfeldig indeksert tilgang ikke er nødvendig, er en lenket liste et passende valg.
  • Innsetting i midten: Innsetting midt i en matrise krever forskyvning av elementer. En lenket liste tillater innsetting på en hvilken som helst posisjon ved å omskrive bare noen få pekere.

Operasjoner av Singly Linked List

En enkeltkoblet liste er bra for dynamisk allokering av minne. Den støtter standardoperasjonene til den koblede listen, dvs. innsetting, sletting, søking, oppdatering, sammenslåing av to lister og gjennomgang.

Følgende operasjoner diskuteres i denne artikkelen:

  • Innsetting ved hodet
  • Innsetting ved halen
  • Setter inn etter en node
  • Setter inn før en node
  • Slett hodenoden
  • Slett haleknuten
  • Søk og slett en node
  • Gå gjennom den koblede listen

Her er et eksempel på en lenket liste med fire noder.

Eksempel på en enkeltkoblet liste

Eksempel på en enkeltkoblet liste

Innsetting i toppen av en enkeltkoblet liste

Dette er en enkel operasjon. Det er generelt kjent som å pushe på en enkeltkoblet liste. En ny node opprettes og plasseres øverst i listen.

For å utføre denne operasjonen, følg to viktige betingelser:

  1. Hvis listen er tom, blir den nyopprettede noden hovednoden, og dens neste pekeren er NULL.
  2. Hvis listen ikke er tom, blir den nye noden hovednoden, og dens neste Pekeren peker på den forrige hodenoden.

Her er pseudokoden for å sette inn en node øverst i en lenket liste:

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

Innsetting ved hodet

Innsetting ved hodet

Innsetting på slutten av en enkeltkoblet liste

Å sette inn en node på slutten av en lenket liste er likt å sette inn i toppen. Gå til halenoden, og pek deretter dens neste pekeren til den nye noden. Hvis hodet er NULL, blir den nye noden hodet.

Trinn 1) Gå gjennom til neste Pekeren til den gjeldende noden blir NULL.

Trinn 2) Opprett en ny node med den angitte verdien.

Trinn 3) Tilordne den nye noden som den neste noden i halenoden.

Pseudokoden for å sette inn i slutten av en enkeltliste:

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

Innsetting ved halen

Innsetting ved halen

Innsetting etter en node i en enkeltkoblet liste

Å sette inn etter en node har to deler: søk etter målnoden og legg til en ny node etter den. Bla gjennom listen til du finner et treff, og skjøt deretter den nye noden inn.

Trinn 1) Gå gjennom til verdien til gjeldende node er lik søkeelementet.

Trinn 2) Angi den nye nodens neste pekeren til den gjeldende nodens neste pekeren.

Trinn 3) Peke på gjeldende nodes neste pekeren til den nye noden.

Pseudokode:

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

Sette inn en node etter en node i enkeltlenket liste

Sette inn en node etter en node i Singly Linked List

Innsetting før en node i en enkeltkoblet liste

Dette ligner på innsetting etter en node. Gå gjennom den til neste node samsvarer med søkeverdien, og sett deretter inn den nye noden før den.

Trinn 1) Gå til neste nodes verdi er lik søkeelementet.

Trinn 2) Opprett en ny node og sett dens neste pekeren til den gjeldende nodens neste.

Trinn 3) Peke på gjeldende nodes neste til den nye noden.

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

Sette inn en node før en node i enkeltlenket liste

Sette inn en node før en node i Singly Linked List

RELATERTE ARTIKLER

Slett overskriften på den enkeltkoblede listen

Hodepekeren er oppgitt som parameter. Hodenoden fjernes, og den neste noden blir den nye hodenoden. Minnet til den slettede noden må frigjøres for å unngå minnelekkasjer.

Trinn 1) Tilordne den neste noden i hodet som det nye hodet.

Trinn 2) Frigjør det tildelte minnet til den forrige head-noden.

Trinn 3) Returner den nye hodenoden.

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

Sletting av hodet på en koblet liste

Sletter hodet til en koblet liste

Slett halen av den enkeltkoblede listen

Å slette halenoden ligner på å slette hodenoden. Forskjellen er at det kreves traversering til slutten av listen. I en enkeltkoblet liste er noden hvis neste pekeren er NULL er halenoden.

Trinn 1) Traverser til rett før halenoden. Lagre gjeldende node.

Trinn 2) Frigjør minnet til neste node (halen).

Trinn 3) Sett den neste noden i den gjeldende noden til NULL.

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

Sletter halen av enkeltlenket liste

Sletter halen av enkeltlenket liste

Søk etter og slett en node fra en enkeltkoblet liste

Denne funksjonen utfører to oppgaver: søke og slette. Bla gjennom til slutten av listen. Hvis en samsvarende node blir funnet, fjern den og koble den forrige nodens til på nytt. neste pekeren.

Trinn 1) Gå til slutten av listen. Sjekk om gjeldende node er lik søkenoden.

Trinn 2) Hvis det finnes et treff, lagrer du en peker til den gjeldende noden.

Trinn 3) Ocuco neste til den forrige noden blir den neste noden til den nåværende noden.

Trinn 4) Slett den gjeldende noden og frigjør minnet.

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øk og slett en node fra enkeltlenket liste

Søk og slett en node fra Liste over enkeltlenkede

Gå gjennom en enkeltkoblet liste

En enkeltlenket liste støtter bare traversering fra topp til hale. Det finnes ingen peker til forrige node, så omvendt traversering er ikke mulig. Hver node besøkes etter tur, og verdien skrives ut til NULL nås.

Trinn 1) Gå gjennom hver node til NULL er nådd.

Trinn 2) Skriv ut verdien til gjeldende node.

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

Eksempel på enkeltlenket 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);
}

Produksjon

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

Produksjon

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 til enkeltlenkede liste

Det finnes to typer kompleksitet: tidskompleksitet og romkompleksitet. Den verste og gjennomsnittlige tidskompleksiteten er den samme for en enkeltlenket liste.

Best-case tidskompleksitet:

  • Innsetting ved hodet kan gjøres i O(1). Ingen traversering innenfor listen er nødvendig.
  • Søk og sletting kan gjøres i O(1) hvis målelementet er ved hovednoden.

Gjennomsnittlig sakstidskompleksitet:

  • Innsetting i en lenket liste tar O(n), hvor n er det totale antallet elementer.
  • Søk og sletting kan også ta O(n), fordi målelementet kan befinne seg hvor som helst opp til halenoden.

Romkompleksitet av enkeltlenket liste

En enkeltkoblet liste allokerer minne dynamisk. For å lagre n elementer, tildeler den n minneenheter. Så romkompleksiteten er O(n).

Bruksområder for enkeltlenket liste

Enkeltkoblede lister vises mange steder der kun fremoverrettet traversering og dynamisk minne er nyttige:

  • Stabler og køer: Underliggende lagring for LIFO-stabler og FIFO-køer bygget fra noder.
  • Kjeding av hash-tabeller: Kollisjoner løses ved å kjede sammen oppføringer i en enkeltkoblet liste per bøtte.
  • Nærhetslister: Sparse grafer bruker en enkeltkoblet liste over naboer for hvert hjørne.
  • Symboltabeller: Kompilatorer og tolker kjeder identifikatorer til en enkeltkoblet liste per omfang.
  • Minneallokatorer: Gratislistetildelere track frie blokker som en enkeltlenket liste.

Spørsmål og svar

Enkeltkoblede lister kjeder treningseksempler, minibatcher og ledige minneblokker i AI-rammeverk, noe som muliggjør dynamiske køer for strømming av inndata og låsefrie datapipeliner som skaleres med modellens etterspørsel.

Ja. GitHub Copilot og GPT kan produsere en fullstendig enkeltlenket liste i C. C++, Java, Pythoneller JavaSkript, inkludert innsetting, sletting, reversering, syklusdeteksjon og enhetstester.

En enkeltlenket liste har én nestepeker og beveger seg bare fremover. En dobbeltlenket liste har både neste- og forrigepekere og beveger seg i begge retninger, men bruker mer minne per node.

Vanlige bruksområder inkluderer stakk- og køimplementeringer, hash-tabellkjedening, tilstøtende lister for sparsomme grafer, symboltabeller i kompilatorer, frilistetildelere og angrehistorikk i lette editorer.

Innsetting eller sletting ved hodet er O(1). Innsetting ved halen, søk, innsetting ved en posisjon og sletting av en spesifikk node koster alle O(n) fordi traversering er nødvendig fra hodet.

Lenkede lister vokser og krymper under kjøretid, setter inn eller sletter i O(1) når posisjonen er kjent, og trenger aldri sammenhengende minne. Arrayer tilbyr O(1) tilfeldig tilgang og bedre hurtigbufferlokalitet.

Gå gjennom listen med tre pekere, prev, curr og next. Lagre curr.next på hvert trinn, pek curr.next på prev, og flytt prev og curr fremover. Returner prev som den nye overskriften.

Floyds skilpadde-og-hare-algoritme bruker to pekere som beveger seg med ulik hastighet. Hvis de noen gang møtes, inneholder listen en syklus. Ellers når den raske pekeren NULL, og ingen syklus eksisterer.

Oppsummer dette innlegget med: