Enkeltkoblet liste i datastrukturer

by: Sarah Chen Sarah Chen
Hours oppdatert

Hva er en enkeltkoblet liste?

Singly Linked List er en lineær og ensrettet datastruktur, der data lagres på nodene, og hver node kobles via en lenke til sin neste node. Hver node inneholder et datafelt og en lenke til neste node. Enkeltkoblede lister kan krysses i bare én retning, mens dobbeltkoblede lister kan krysses i begge retninger.

Her er en nodestruktur for en enkeltlenket liste:

Strukturen til en node i en koblet liste
Strukturen til en node i en koblet liste

Hvorfor bruke koblet liste over array?

Det er flere tilfeller der det er bedre å bruke den koblede listen i stedet for Array. Her er noen scenarier:

  • Ukjent antall elementer: Når du ikke vet hvor mange elementer du trenger å lagre i løpet av programmets kjøretid, kan du bruke Linked List. Minne tildeles dynamisk når du legger til elementer i de koblede listene.
  • Tilfeldig tilgang: I et scenario der du ikke trenger å bruke tilfeldig tilgang fra elementene, kan du bruke den koblede listen.
  • Innsetting i midten: Innsetting i midten av en matrise er en kompleks oppgave. Fordi du må skyve andre elementer til høyre. En koblet liste lar deg imidlertid legge til et element til hvilken som helst posisjon du ønsker.

Operasjoner av Singly Linked List

Singly Linked List er bra for dynamisk tildeling av minne. Den gir alle de grunnleggende operasjonene til den koblede listen, dvs. innsetting, sletting, søk, oppdatering, sammenslåing av to koblede lister, kryssing, etc.

Her vil vi diskutere følgende operasjon av den koblede listen:

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

Eksempel på en enkeltkoblet liste
Eksempel på en enkeltkoblet liste

Innsetting i toppen av en enkeltlenket liste

Dette er en enkel operasjon. Vanligvis er det kjent som å skyve en enkeltlenket liste. Du må opprette en ny node og plassere denne i toppen av den koblede listen.

For å utføre denne operasjonen må vi følge to viktige forhold. Det er de

  1. Hvis listen er tom, vil den nyopprettede noden være hodenoden, og den neste noden i hodet vil være "NULL".
  2. Hvis listen ikke er tom, vil den nye noden være hodenoden, og den neste vil peke på den forrige hodenoden.

Her er pseudokoden for å sette inn en node på toppen av en koblet 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 enkeltlenket liste

Å sette inn en node på slutten av en koblet liste har noen likheter med å sette inn i hodet. Alt du trenger å gjøre er å gå til sluttnoden eller halenoden. Pek deretter den "neste" noden til sluttnoden til den nyopprettede noden. Hvis hodenoden er null, vil den nye noden være hodenoden.

Her er trinnene:

Trinn 1) Gå til "neste" node til gjeldende node 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 en node på halen av en enkelt liste:

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
Innsetting ved halen
Innsetting ved halen

Innsetting etter en node i en enkeltlenket liste

Innsetting etter en node har to deler: Søk etter noden og fest etter den søkte noden. Vi må krysse alle nodene. For hver node må vi matche med søkeelementet. Hvis det er et samsvar, vil vi legge til den nye noden etter den søkte noden.

Her er trinnene:

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

Trinn 2) Den nye nodens neste peker vil være den nåværende nodens neste peker.

Trinn 3) Nåværende nodes neste node vil være den nye noden.

Her er pseudokoden for å sette inn en node etter en node:

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
Sette inn en node etter en node i enkeltlenket liste
Sette inn en node etter en node i Singly Linked List

RELATERTE ARTIKLER

Innsetting før en node i en enkeltlenket liste

Denne funksjonen ligner mye på innsettingen etter en node. Vi må opprette en ny node og krysse den koblede listen til den gjeldende noden samsvarer med søkenoden. Etter det vil vi legge til den nye noden som den forrige noden til den nåværende noden.

Her er trinnene:

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

Trinn 2) Opprett en ny node og tilordne nodens "neste" med neste til neste node i gjeldende node.

Trinn 3) Tilordne den nye noden som den neste noden til den gjeldende noden.

Her er pseudokoden:

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
Sette inn en node før en node i enkeltlenket liste
Sette inn en node før en node i Singly Linked List

Slett toppen av den enkeltlenkede listen

I hver funksjon av den koblede listen er hodepekeren gitt som parameter. Du må slette hodenoden og gjøre den neste knuten til hodenoden som den nye hoden for den koblede listen. Vi må også frigjøre minnet til den slettede noden. Ellers vil minnet bli merket som opptatt når et annet program prøver å få tilgang til det.

Her er trinnene for å slette hodet på den enkeltlenkede listen:

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

Trinn 2) Frigjør det tildelte minnet ved forrige hodenode.

Trinn 3) Returner den nye hodenoden.

Pseudokoden for å slette 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 enkeltlenkede listen

Å slette haleknuten er mer kjent med å slette hodenoden. Forskjellen er at vi må gå til slutten av den koblede listen og slette den. I den enkeltlenkede listen er noden med neste node som "NULL" halenoden.

Her er trinnene for å slette halenoden til den koblede listen:

Trinn 1) Traverser før haleknuten. Lagre gjeldende node.

Trinn 2) Frigjør minnet til neste node i gjeldende node.

Trinn 3) Sett neste node i gjeldende node som NULL.

Her er pseudokoden for å slette haleknuten:

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

Denne funksjonen har to oppgaver, søk og slett. Vi må søke til slutten av de enkeltlenkede listene. Hvis vi finner en lignende node, vil vi slette den. Etter det må vi slå sammen eller koble venstre og høyre noder til den slettede noden. Her er trinnene for å gjøre dette:

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

Trinn 2) Hvis noen node samsvarer, lagre nodepekeren til gjeldende node.

Trinn 3) Den "neste" av forrige node vil være den neste noden til gjeldende node.

Trinn 4) Slett og frigjør minnet til gjeldende node.

Pseudokode for søk og sletting av en node fra en enkeltlenket 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)
Søk og slett en node fra enkeltlenket liste
Søk og slett en node fra Liste over enkeltlenkede

Gå gjennom en enkeltlenket liste

Enkeltlenket liste har kun funksjonalitet for å krysse hode til hale. Det er ingen pekerpunkter til forrige node; det er derfor vi ikke kan krysse den enkeltlenkede listen i omvendt rekkefølge. Vi vil krysse hver node og skrive ut gjeldende nodes verdi til vi får null.

Her er trinnene:

Trinn 1) Gå gjennom hver node til vi får null som neste node.

Trinn 2) Skriv ut verdien til gjeldende node.

Pseudokode for å krysse en enkeltlenket liste:

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

Utgang:

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 Program

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

Utgang:

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 er to typer kompleksitet: tidskompleksitet og romkompleksitet. Den verste og gjennomsnittlige sakstidskompleksiteten er den samme for Singly Linked List.

Tidskompleksiteten for det beste tilfellet:

  • Innsetting i hodet kan gjøres i O(1). Siden vi ikke trenger å krysse innsiden av den koblede listen.
  • Søke- og sletteoperasjon kan gjøres i O(1) hvis søkeelementet er tilstede i hodenoden.

Tidskompleksiteten for gjennomsnittssaken:

  • Innsetting i en koblet liste vil ta O(n) hvis "n" elementer er til stede i den enkeltlenkede listen.
  • Søk og slett kan også ta O(n), da søkeelementet kan være tilstede i halenoden. I så fall bør du gå gjennom hele listen.

Plasskompleksiteten til enkeltlenkede liste

Singly Linked List tildeler minne dynamisk. Hvis vi ønsker å lagre n elementer, vil det tildele n minneenhet. Så romkompleksiteten er O(n).