Lista legată individual în structurile de date

Ce este o listă legată individual?

Singly Linked List este o structură de date liniară și unidirecțională, în care datele sunt salvate pe noduri, iar fiecare nod este conectat printr-o legătură la următorul său nod. Fiecare nod conține un câmp de date și o legătură către următorul nod. Listele cu legături unice pot fi parcurse într-o singură direcție, în timp ce Lista cu legătură dublă poate fi parcursă în ambele direcții.

Iată o structură de noduri a unei liste legate individual:

De ce să folosiți lista legată peste matrice?

Există mai multe cazuri în care este mai bine să utilizați Lista legată decât lista Mulțime. Iată câteva scenarii:

• Număr necunoscut de elemente: Când nu știți câte elemente trebuie să stocați în timpul rulării programului, puteți utiliza Lista Legături. Memoria este alocată dinamic pe măsură ce adăugați elemente la listele legate.
• Acces aleator: Într-un scenariu, în care nu trebuie să utilizați accesul aleator de la elemente, puteți utiliza Lista Linked.
• Inserare la mijloc: Inserarea în mijlocul unui tablou este o sarcină complexă. Pentru că trebuie să împingi alte elemente spre dreapta. Cu toate acestea, o listă conectată vă permite să adăugați un element la orice poziție doriți.

Operalistei cu legături individuale

Lista legată individual este bună pentru alocarea dinamică a memoriei. Acesta oferă toate operațiunile de bază ale listei legate, adică inserarea, ștergerea, căutarea, actualizarea, îmbinarea a două liste legate, parcurgerea etc.

Aici vom discuta despre următoarea operațiune a listei legate:

• Inserarea la cap
• Inserarea la coada
• Inserarea după un nod
• Inserarea înaintea unui nod
• Ștergeți nodul principal
• Ștergeți nodul de coadă
• Căutați și ștergeți un nod
• Parcurgerea listei conectate

Iată un exemplu de listă legată cu patru noduri.

Inserarea în fruntea unei liste legate individual

Aceasta este o operațiune simplă. În general, este cunoscut ca împingerea unei liste conectate unic. Trebuie să creați un nou nod și să îl plasați în capul listei legate.

Pentru a efectua această operație, trebuie să respectăm două condiții importante. Ei sunt

1. Dacă lista este goală, atunci nodul nou creat va fi nodul principal, iar următorul nod al capului va fi „NULL”.
2. Dacă lista nu este goală, noul nod va fi nodul principal, iar următorul va indica nodul principal anterior.

Iată pseudo-codul pentru inserarea unui nod în capul unei liste legate:

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

Inserarea la sfârșitul unei liste conectate individual

Inserarea unui nod la sfârșitul unei liste legate are unele asemănări cu inserarea în cap. Tot ce trebuie să faceți este să traversați până la nodul final sau nodul de coadă. Apoi îndreptați nodul „următorul” al nodului final către nodul nou creat. Dacă nodul principal este nul, noul nod va fi nodul principal.

Iată pașii:

Pas 1) Traversați până când nodul „următorul” al nodului curent devine nul.

Pas 2) Creați un nou nod cu valoarea specificată.

Pas 3) Atribuiți noul nod ca următor nod al nodului de coadă.

Pseudo-codul pentru inserarea unui nod la coada unei liste individuale:

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

Inserarea după un nod într-o listă legată individual

Inserarea după un nod are două părți: Căutați nodul și atașați după nodul căutat. Trebuie să traversăm toate nodurile. Pentru fiecare nod, trebuie să se potrivească cu elementul de căutare. Dacă există o potrivire, atunci vom adăuga noul nod după nodul căutat.

Iată pașii:

Pas 1) Traversați următorul nod până când valoarea nodului curent este egală cu elementul de căutare.

Pas 2) Următorul pointer al nodului nou va fi următorul pointer al nodului curent.

Pas 3) Următorul nod al nodului curent va fi noul nod.

Iată pseudo-codul pentru inserarea unui nod după un 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

Inserarea înaintea unui nod într-o listă legată individual

Această funcție este mult asemănătoare cu inserarea după un nod. Trebuie să creăm un nou nod și să parcurgem lista legată până când nodul curent se potrivește cu nodul de căutare. După aceea, vom adăuga noul nod ca nod anterior al nodului curent.

Iată pașii:

Pas 1) Traversați până când valoarea nodului următor este egală cu elementul de căutare.

Pas 2) Creați un nod nou și atribuiți „următorul” nodului cu următorul nod al nodului curent.

Pas 3) Atribuiți noul nod ca următor nod al nodului curent.

Iată pseudo-codul:

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

Ștergeți capul listei conectate individual

În fiecare funcție a listei legate, indicatorul de cap este furnizat ca parametru. Trebuie să ștergeți nodul principal și să faceți următorul nod al nodului principal ca noul cap al listei legate. De asemenea, trebuie să eliberăm memoria nodului șters. În caz contrar, memoria va fi marcată ca ocupată atunci când un alt program încearcă să o acceseze.

Iată pașii pentru ștergerea capului listei conectate individual:

Pas 1) Atribuiți următorul nod al nodului principal ca noul cap.

Pas 2) Eliberați memoria alocată de către nodul principal anterior.

Pas 3) Reveniți noul nod principal.

Pseudo-codul pentru ștergerea nodului principal:

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

Ștergeți coada listei conectate individual

Ștergerea nodului de coadă este mai familiară cu ștergerea nodului principal. Diferența este că trebuie să traversăm până la sfârșitul listei legate și să o ștergem. În lista legată individual, nodul cu următorul nod ca „NULL” este nodul de coadă.

Iată pașii pentru ștergerea nodului de coadă al listei legate:

Pas 1) Traversați înainte de nodul de coadă. Salvați nodul curent.

Pas 2) Eliberați memoria următorului nod al nodului curent.

Pas 3) Setați următorul nod al nodului curent ca NULL.

Iată pseudo-codul pentru ștergerea nodului de coadă:

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

Căutați și ștergeți un nod dintr-o listă legată individual

Această funcție are două sarcini, căutare și ștergere. Trebuie să căutăm până la sfârșitul listelor legate individual. Dacă găsim vreun nod similar, îl vom șterge. După aceea, trebuie să îmbinăm sau să legăm nodurile stânga și dreapta ale nodului șters. Iată pașii pentru a face acest lucru:

Pas 1) Traversați până la sfârșitul listei conectate. Verificați dacă nodul curent este egal cu nodul de căutare sau nu.

Pas 2) Dacă vreun nod se potrivește, stocați pointerul nodului către nodul curent.

Pas 3) „Următorul” nodului anterior va fi următorul nod al nodului curent.

Pas 4) Ștergeți și eliberați memoria nodului curent.

Pseudo-cod pentru căutarea și ștergerea unui nod dintr-o listă legată individual:

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)

Parcurgeți o listă conectată individual

Lista legată individual are doar funcționalitatea de a parcurge cap la coadă. Nu există puncte pointer către nodul anterior; de aceea nu putem parcurge Lista cu legături individuale în ordine inversă. Vom parcurge fiecare nod și vom imprima valoarea nodului curent până când vom obține nul.

Iată pașii:

Pas 1) Traversați fiecare nod până când obținem nul ca următorul nod.

Pas 2) Tipăriți valoarea nodului curent.

Pseudo-cod pentru parcurgerea unei liste conectate unic:

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

Exemplu de listă conectată individual în 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);
}

ieșire:

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

Exemplu de listă conectată individual în 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()

ieșire:

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

Complexitatea listei legate individual

Există două tipuri de complexitate: complexitatea timpului și complexitatea spațiului. Complexitatea timpului cel mai rău și mediu al cazului este aceeași pentru Lista legată individual.

Complexitatea timpului pentru cel mai bun caz:

• Inserarea în cap se poate face în O(1). Deoarece nu trebuie să traversăm în interiorul listei legate.
• Operația de căutare și ștergere se poate face în O(1) dacă elementul de căutare este prezent în nodul principal.

Complexitatea timpului pentru cazul mediu:

• Inserarea într-o listă legată va lua O(n) dacă „n” elemente sunt prezente în lista legată individual.
• Căutarea și ștergerea pot lua și O(n), deoarece elementul de căutare poate fi prezent în nodul de coadă. În acest caz, ar trebui să parcurgeți întreaga listă.

Complexitatea spațială a listei legate individual

Singly Linked List alocă dinamic memorie. Dacă dorim să stocăm n elemente, va aloca n unități de memorie. Deci, complexitatea spațiului este O(n).