Enkelt länkad lista i datastrukturer

By: Sarah Chen Sarah Chen
Hours Uppdaterad

Vad är en enstaka länkad lista?

Singly Linked List är en linjär och enkelriktad datastruktur, där data sparas på noderna och varje nod är ansluten via en länk till nästa nod. Varje nod innehåller ett datafält och en länk till nästa nod. Enkelt länkade listor kan passeras i endast en riktning, medan dubbellänkade listor kan passeras i båda riktningarna.

Här är en nodstruktur för en Singly Linked List:

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

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

Det finns flera fall då det är bättre att använda den länkade listan istället för array. Här är några scenarier:

  • Okänt antal element: När du inte vet hur många element du behöver lagra under programmets körning, kan du använda den länkade listan. Minnet allokeras dynamiskt när du lägger till element i de länkade listorna.
  • Slumpmässig tillgång: I ett scenario, där du inte behöver använda slumpmässig åtkomst från elementen, kan du använda den länkade listan.
  • Insättning i mitten: Insättning i mitten av en array är en komplex uppgift. För du måste trycka andra element åt höger. Men en länkad lista låter dig lägga till ett element till vilken position du vill.

Operationer av Singly Linked List

Singly Linked List är bra för att dynamiskt allokera minne. Den tillhandahåller alla grundläggande funktioner för den länkade listan, dvs infogning, radering, sökning, uppdatering, sammanfogning av två länkade listor, korsning, etc.

Här kommer vi att diskutera följande funktion för den länkade listan:

  • 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
Exempel på en enda länkad lista

Infogning i spetsen för en Singly Linked List

Detta är en enkel operation. I allmänhet är det känt som att trycka på en enkellänkad lista. Du måste skapa en ny nod och placera denna högst upp i den länkade listan.

För att utföra denna operation måste vi följa två viktiga villkor. Det är de

  1. Om listan är tom kommer den nyskapade noden att vara huvudnoden, och nästa nod på huvudet kommer att vara ”NULL”.
  2. Om listan inte är tom kommer den nya noden att vara huvudnoden, och nästa kommer att peka på den föregående huvudnoden.

Här är pseudokoden för att infoga en nod i spetsen 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
Insättning vid huvudet

Infogning i slutet av en enkellänkad lista

Att infoga en nod i slutet av en länkad lista har vissa likheter med att infoga i huvudet. Allt du behöver göra är att gå till slutnoden eller svansnoden. Peka sedan "nästa" nod i slutnoden till den nyskapade noden. Om huvudnoden är noll kommer den nya noden att vara huvudnoden.

Här är stegen:

Steg 1) Traversera tills "nästa" nod för den aktuella noden blir noll.

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 en nod längst ner på en enda lista:

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
Insättning vid svansen
Insättning vid svansen

Infogning efter en nod i en Singly Linked List

Att infoga efter en nod har två delar: Sök efter noden och bifoga efter den sökta noden. Vi måste korsa alla noder. För varje nod måste vi matcha med sökelementet. Om det finns en matchning kommer vi att lägga till den nya noden efter den sökta noden.

Här är stegen:

Steg 1) Gå igenom nästa nod tills värdet på den aktuella noden är lika med sökobjektet.

Steg 2) Den nya nodens nästa pekare kommer att vara den nuvarande nodens nästa pekare.

Steg 3) Den nuvarande nodens nästa nod kommer att vara den nya noden.

Här är pseudokoden för att infoga en nod efter en nod:

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
Infoga en nod efter en nod i singelänkade lista
Infoga en nod efter en nod i Singly Linked List

RELATERADE ARTIKLAR

Infogning före en nod i en Singly Linked List

Denna funktion är mycket lik insättningen efter en nod. Vi måste skapa en ny nod och gå igenom den länkade listan tills den aktuella noden matchar söknoden. Efter det kommer vi att lägga till den nya noden som den tidigare noden för den aktuella noden.

Här är stegen:

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

Steg 2) Skapa en ny nod och tilldela nodens "nästa" med nästa till nästa nod i den aktuella noden.

Steg 3) Tilldela den nya noden som nästa nod för den aktuella noden.

Här är 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
Infoga en nod före en nod i singelänkade lista
Infoga en nod före en nod i Singly Linked List

Ta bort huvudet på den enkellänkade listan

I varje funktion i den länkade listan tillhandahålls huvudpekaren som parameter. Du måste ta bort huvudnoden och göra nästa nod för huvudnoden som den nya huvudnoden för den länkade listan. Vi måste också frigöra minnet för den borttagna noden. Annars kommer minnet att markeras som upptaget när ett annat program försöker komma åt det.

Här är stegen för att ta bort huvudet på den enkellänkade listan:

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

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

Steg 3) Returnera den nya huvudnoden.

Pseudokoden för att ta bort huvudnoden:

function deleteHead( head ):
	temp = head
	head = head.next
	free( temp )
	return head
Ta bort huvudet för en länkad lista
Ta bort huvudet på en länkad lista

Ta bort svansen på den enkellänkade listan

Att ta bort svansnoden är mer bekant med att ta bort huvudnoden. Skillnaden är att vi måste gå till slutet av den länkade listan och ta bort den. I den enkellänkade listan är noden med nästa nod som "NULL" svansnoden.

Här är stegen för att ta bort svansnoden i den länkade listan:

Steg 1) Traverse före svansnoden. Spara den aktuella noden.

Steg 2) Frigör minnet för nästa nod i den aktuella noden.

Steg 3) Ställ in nästa nod för den aktuella noden som NULL.

Här är pseudokoden för att ta bort svansnoden:

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
Ta bort svansen av enbart länkad lista

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

Denna funktion har två uppgifter, sök och radera. Vi måste söka till slutet av de enkellänkade listorna. Om vi ​​hittar någon liknande nod kommer vi att ta bort den. Efter det måste vi slå samman eller länka vänster och höger noder för den borttagna noden. Här är stegen för att göra detta:

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

Steg 2) Om någon nod matchar, lagra nodpekaren till den aktuella noden.

Steg 3) "Nästa" av föregående nod kommer att vara nästa nod för den aktuella noden.

Steg 4) Ta bort och frigör minnet för den aktuella noden.

Pseudokod för sökning och radering av en nod från en enkellänkad lista:

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

Gå igenom en enskild länkad lista

Enbart länkad lista har bara funktionen för att korsa topp till svans. Det finns inga pekare till föregående nod; det är därför vi inte kan gå igenom den enkellänkade listan i omvänd ordning. Vi kommer att korsa varje nod och skriva ut den aktuella nodens värde tills vi får null.

Här är stegen:

Steg 1) Traversera varje nod tills vi får noll som nästa nod.

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

Pseudokod för att gå igenom en enkellänkad lista:

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

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 Prográmma

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

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 rymdkomplexitet. Den värsta och genomsnittliga falltidskomplexiteten är densamma för listan med enkel länk.

Tidskomplexiteten för bästa fall:

  • Insättning i huvudet kan göras i O(1). Eftersom vi inte behöver gå inuti den länkade listan.
  • Sök- och raderingsoperation kan göras i O(1) om sökelementet finns i huvudnoden.

Tidskomplexiteten för det genomsnittliga fallet:

  • Infogning i en länkad lista kommer att ta O(n) om "n" element finns i listan med enkel länk.
  • Sök och ta bort kan också ta O(n), eftersom sökelementet kan finnas i svansnoden. I så fall bör du gå igenom hela listan.

Utrymmeskomplexiteten för enbart länkad lista

Singly Linked List allokerar dynamiskt minne. Om vi ​​vill lagra n element kommer den att allokera n minnesenhet. Så rymdkomplexiteten är O(n).