Enkelt länkad lista i datastrukturer

Vad är en enstaka länkad lista?

En enkellänkad lista är en linjär och enkelriktad datastruktur där data sparas på noderna, och varje nod är ansluten via en länk till sin nästa nod. Varje nod innehåller ett datafält och en länk till nästa nod. Enkellänkade listor kan endast navigeras i en riktning, medan en Dubbelt länkad lista kan passeras i båda riktningarna.

Här är nodstrukturen för en enkellänkad lista:

Struktur för en nod i en länkad lista

Varför använda en länkad lista över en array?

Flera scenarier gynnar en länkad lista framför en array:

• Okänt antal element: När det erforderliga elementantalet inte är känt vid kompileringstillfället allokerar en länkad lista minne dynamiskt allt eftersom element läggs till.
• Slumpmässig tillgång: När slumpmässig indexerad åtkomst inte behövs är en länkad lista ett lämpligt val.
• Insättning i mitten: Att infoga mitt i en array kräver att elementen flyttas. En länkad lista tillåter infogning på valfri position genom att bara skriva om några få pekare.

Operationer av Singly Linked List

En enkellänkad lista är bra för dynamisk minnesallokering. Den stöder standardoperationerna för den länkade listan, dvs. infogning, borttagning, sökning, uppdatering, sammanslagning av två listor och bläddring.

Följande operationer diskuteras i den här artikeln:

• Insättning vid huvudet
• Insättning i svansen
• Infogar efter en nod
• Infogar före en nod
• Ta bort huvudnoden
• Ta bort svansnoden
• Sök och ta bort en nod
• Gå igenom den länkade listan

Här är ett exempel på en länkad lista med fyra noder.

Exempel på en enda länkad lista

Infogning i början av en enkellänkad lista

Detta är en enkel operation. Det är allmänt känt som att pusha till en enkellänkad lista. En ny nod skapas och placeras högst upp i listan.

För att utföra denna operation, följ två viktiga villkor:

1. Om listan är tom blir den nyskapade noden huvudnoden, och dess Nästa pekaren är NULL.
2. Om listan inte är tom blir den nya noden huvudnoden, och dess Nästa Pekaren pekar på föregående huvudnod.

Här är pseudokoden för att infoga en nod i början av en länkad lista:

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

Insättning vid huvudet

Infogning i slutet av en enkellänkad lista

Att infoga en nod i slutet av en länkad lista liknar att infoga i början. Gå till den bakre noden och peka sedan dess Nästa pekaren till den nya noden. Om head-värdet är NULL blir den nya noden head-värdet.

Steg 1) Gå igenom tills Nästa pekaren för den aktuella noden blir NULL.

Steg 2) Skapa en ny nod med det angivna värdet.

Steg 3) Tilldela den nya noden som nästa nod i svansnoden.

Pseudokoden för att infoga i slutet av en singellista:

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

Insättning vid svansen

Infogning efter en nod i en enkellänkad lista

Att infoga efter en nod har två delar: sök efter målnoden och lägg till en ny nod efter den. Bläddra igenom listan tills en matchning hittas och skarva sedan in den nya noden.

Steg 1) Gå igenom rutan tills värdet för den aktuella noden är lika med sökobjektet.

Steg 2) Ställ in den nya nodens Nästa pekaren till den aktuella nodens Nästa pekare.

Steg 3) Peka den aktuella nodens Nästa pekaren till den nya noden.

Pseudokod:

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

Infoga en nod efter en nod i Singly Linked List

Infogning före en nod i en enkellänkad lista

Detta liknar infogning efter en nod. Gå tills nästa nod matchar sökvärdet och infoga sedan den nya noden före den.

Steg 1) Traversera tills nästa nods värde är lika med sökobjektet.

Steg 2) Skapa en ny nod och ange dess Nästa pekaren till den aktuella nodens Nästa.

Steg 3) Peka den aktuella nodens Nästa till den nya noden.

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

Infoga en nod före en nod i Singly Linked List

Ta bort huvudet på den enkellänkade listan

Head-pekaren anges som parameter. Head-noden tas bort och nästa nod blir den nya head-noden. Minnet för den borttagna noden måste frigöras för att undvika minnesläckor.

Steg 1) Tilldela nästa nod i huvudet som det nya huvudet.

Steg 2) Frigör det allokerade minnet för den föregående huvudnoden.

Steg 3) Returnera den nya huvudnoden.

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

Ta bort huvudet på en länkad lista

Ta bort slutet av den enkellänkade listan

Att ta bort svansnoden liknar att ta bort huvudnoden. Skillnaden är att det krävs att man går till slutet av listan. I en enkellänkad lista är noden vars Nästa pekaren är NULL är svansnoden.

Steg 1) Traversera tills strax före svansnoden. Spara den aktuella noden.

Steg 2) Frigör minnet för nästa nod (svansen).

Steg 3) Sätt nästa nod i den aktuella noden till NULL.

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

Ta bort svansen av enbart länkad lista

Sök och ta bort en nod från en enskilt länkad lista

Den här funktionen utför två uppgifter: sök och radera. Bläddra till slutet av listan. Om en matchande nod hittas, ta bort den och länka om den föregående nodens. Nästa pekare.

Steg 1) Gå till slutet av listan. Kontrollera om den aktuella noden är lika med söknoden.

Steg 2) Om en matchning hittas, lagra en pekare till den aktuella noden.

Steg 3) Ocuco-landskapet Nästa för den föregående noden blir nästa nod för den aktuella noden.

Steg 4) Ta bort den aktuella noden och frigör dess minne.

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 och ta bort en nod från listan med enkel länk

Gå igenom en enskilt länkad lista

En enkellänkad lista stöder endast traversering från topp till svans. Det finns ingen pekare till föregående nod, så omvänd traversering är inte möjlig. Varje nod besöks i tur och ordning och skrivs ut sitt värde tills NULL nås.

Steg 1) Gå igenom varje nod tills NULL nås.

Steg 2) Skriv ut värdet för den aktuella noden.

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

Exempel på Singly Linked List 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);
}

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

Exempel på Singly Linked List 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()

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

Komplexiteten av enbart länkad lista

Det finns två typer av komplexitet: tidskomplexitet och rumskomplexitet. Den värsta och genomsnittliga tidskomplexiteten är densamma för en enkellänkad lista.

Bästa tänkbara tidskomplexitet:

• Insättning vid början kan göras i O(1). Ingen genomgång inom listan krävs.
• Sökning och borttagning kan göras i O(1) om målelementet finns vid huvudnoden.

Genomsnittlig tidskomplexitet för fall:

• Insättning i en länkad lista tar O(n), där n är det totala antalet element.
• Sökning och borttagning kan också ta O(n), eftersom målelementet kan finnas var som helst upp till svansnoden.

Rymdkomplexitet för enkellänkad lista

En enkellänkad lista allokerar minne dynamiskt. För att lagra n element, allokerar den n minnesenheter. Så rymdkomplexiteten är O(n).

Tillämpningar av enkellänkade listor

Enkelt länkade listor förekommer på många ställen där endast framåtriktad traversal och dynamiskt minne är användbara:

• Staplar och köer: Underliggande lagring för LIFO-stackar och FIFO-köer byggda från noder.
• Kedjning av hashtabeller: Kollisioner löses genom att kedja samman poster i en enkellänkad lista per bucket.
• Närliggande listor: Glesa grafer använder en enkellänkad lista med grannar för varje toppunkt.
• Symboltabeller: Kompilatorer och tolkar kedjeidentifierare till en enkellänkad lista per omfång.
• Minnesallokatorer: Gratislisttilldelare track fria block som en enkellänkad lista.

Vanliga frågor