Elenco collegato singolarmente nelle strutture dati

Che cos'è una lista collegata singolarmente?

La lista collegata singolarmente è una struttura dati lineare e unidirezionale, in cui i dati vengono salvati sui nodi e ciascun nodo è collegato tramite un collegamento al nodo successivo. Ogni nodo contiene un campo dati e un collegamento al nodo successivo. Le liste collegate singolarmente possono essere attraversate in una sola direzione, mentre le liste collegate doppiamente possono essere attraversate in entrambe le direzioni.

Ecco una struttura dei nodi di una lista collegata singolarmente:

Perché utilizzare l'elenco collegato su array?

Esistono diversi casi in cui è meglio utilizzare l'elenco collegato anziché il file Italia. Ecco alcuni scenari:

• Numero sconosciuto di elementi: Quando non sai quanti elementi devi memorizzare durante l'esecuzione del programma, puoi utilizzare la Lista collegata. La memoria viene allocata dinamicamente man mano che aggiungi elementi agli elenchi collegati.
• Accesso casuale: In uno scenario in cui non è necessario utilizzare l'accesso casuale dagli elementi, è possibile utilizzare la Lista collegata.
• Inserimento al centro: L'inserimento nel mezzo di un array è un compito complesso. Perché devi spingere altri elementi verso destra. Tuttavia, una Lista concatenata ti consente di aggiungere un elemento in qualsiasi posizione tu voglia.

Operazioni della lista collegata singolarmente

Singly Linked List è utile per allocare dinamicamente la memoria. Fornisce tutte le operazioni di base della lista concatenata, ovvero inserimento, eliminazione, ricerca, aggiornamento, fusione di due liste concatenate, attraversamento, ecc.

Qui discuteremo la seguente operazione della lista concatenata:

• Inserimento in testa
• Inserimento in coda
• Inserimento dopo un nodo
• Inserimento prima di un nodo
• Elimina il nodo principale
• Elimina il nodo della coda
• Cerca ed elimina un nodo
• Attraversamento della lista collegata

Ecco un esempio di un elenco collegato con quattro nodi.

Inserimento in testa ad una Lista Singolamente Concatenata

Questa è un'operazione semplice. In genere, è noto come push di un elenco collegato singolarmente. È necessario creare un nuovo nodo e posizionarlo in testa all'elenco collegato.

Per eseguire questa operazione dobbiamo seguire due importanti condizioni. Loro sono

1. Se l'elenco è vuoto, il nodo appena creato sarà il nodo testa e il nodo successivo della testa sarà "NULL".
2. Se l'elenco non è vuoto, il nuovo nodo sarà il nodo testa e il successivo punterà al nodo testa precedente.

Ecco lo pseudo-codice per inserire un nodo all'inizio di una lista concatenata:

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

Inserimento alla fine di una Lista Singolamente Concatenata

L'inserimento di un nodo alla fine di una lista concatenata presenta alcune somiglianze con l'inserimento nella testa. Tutto quello che devi fare è attraversare il nodo finale o il nodo di coda. Quindi puntare il nodo "successivo" del nodo finale sul nodo appena creato. Se il nodo testa è nullo, il nuovo nodo sarà il nodo testa.

Ecco i passaggi:

Passo 1) Attraversa fino a quando il nodo "successivo" del nodo corrente diventa nullo.

Passo 2) Crea un nuovo nodo con il valore specificato.

Passo 3) Assegnare il nuovo nodo come nodo successivo del nodo di coda.

Lo pseudo-codice per inserire un nodo alla fine di una singola 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

Inserimento dopo un nodo in una Lista Singolamente Concatenata

L'inserimento dopo un nodo è composto da due parti: ricerca del nodo e collegamento dopo il nodo cercato. Dobbiamo attraversare tutti i nodi. Per ogni nodo, dobbiamo corrispondere all'elemento di ricerca. Se c'è una corrispondenza, aggiungeremo il nuovo nodo dopo il nodo cercato.

Ecco i passaggi:

Passo 1) Attraversa il nodo successivo finché il valore del nodo corrente non equivale all'elemento di ricerca.

Passo 2) Il puntatore successivo del nuovo nodo sarà il puntatore successivo del nodo corrente.

Passo 3) Il nodo successivo del nodo corrente sarà il nuovo nodo.

Ecco lo pseudo-codice per inserire un nodo dopo un nodo:

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

Inserimento prima di un nodo in una Lista Singolamente concatenata

Questa funzione è molto simile all'inserimento dopo un nodo. Dobbiamo creare un nuovo nodo e attraversare l'elenco collegato finché il nodo corrente non corrisponde al nodo di ricerca. Successivamente, aggiungeremo il nuovo nodo come nodo precedente del nodo corrente.

Ecco i passaggi:

Passo 1) Attraversa finché il valore del nodo successivo non equivale all'elemento di ricerca.

Passo 2) Crea un nuovo nodo e assegna il nodo "successivo" al nodo successivo del nodo corrente.

Passo 3) Assegna il nuovo nodo come nodo successivo del nodo corrente.

Ecco lo pseudo-codice:

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

Elimina l'inizio dell'elenco collegato singolarmente

In ogni funzione della lista concatenata, il puntatore di testa è fornito come parametro. Devi eliminare il nodo di testa e rendere il nodo successivo del nodo di testa il nuovo capo della lista concatenata. Dobbiamo anche liberare la memoria del nodo eliminato. Altrimenti, la memoria verrà contrassegnata come occupata quando un altro programma cercherà di accedervi.

Ecco i passaggi per eliminare l'inizio dell'elenco collegato singolarmente:

Passo 1) Assegna il nodo successivo del nodo head come nuova testa.

Passo 2) Liberare la memoria allocata dal nodo head precedente.

Passo 3) Restituisce il nuovo nodo head.

Lo pseudo-codice per eliminare il nodo head:

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

Elimina la coda dell'elenco collegato singolarmente

L'eliminazione del nodo coda ha più familiarità con l'eliminazione del nodo testa. La differenza è che dobbiamo andare alla fine dell'elenco collegato ed eliminarlo. Nell'elenco collegato singolarmente, il nodo con il nodo successivo come "NULL" è il nodo di coda.

Ecco i passaggi per eliminare il nodo coda dell'elenco collegato:

Passo 1) Attraversare prima del nodo della coda. Salva il nodo corrente.

Passo 2) Libera la memoria del nodo successivo del nodo corrente.

Passo 3) Imposta il nodo successivo del nodo corrente come NULL.

Ecco lo pseudo-codice per eliminare il nodo coda:

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

Cerca ed elimina un nodo da un elenco collegato singolarmente

Questa funzione ha due attività, ricerca ed eliminazione. Dobbiamo cercare fino alla fine degli elenchi collegati singolarmente. Se troviamo un nodo simile, lo elimineremo. Successivamente, dobbiamo unire o collegare i nodi sinistro e destro del nodo eliminato. Ecco i passaggi per eseguire questa operazione:

Passo 1) Attraversa fino alla fine dell'elenco collegato. Controlla se il nodo corrente è uguale al nodo di ricerca oppure no.

Passo 2) Se qualche nodo corrisponde, memorizza il puntatore del nodo sul nodo corrente.

Passo 3) Il “successivo” del nodo precedente sarà il nodo successivo del nodo corrente.

Passo 4) Elimina e libera la memoria del nodo corrente.

Pseudo-codice per cercare ed eliminare un nodo da una lista collegata singolarmente:

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)

Attraversa un elenco collegato singolarmente

L'elenco collegato singolarmente ha solo la funzionalità per l'attraversamento dalla testa alla coda. Non sono presenti puntatori al nodo precedente; ecco perché non possiamo percorrere la Lista concatenata singolarmente in ordine inverso. Attraverseremo ciascun nodo e stamperemo il valore del nodo corrente finché non otterremo null.

Ecco i passaggi:

Passo 1) Attraversa ogni nodo finché non otteniamo null come nodo successivo.

Passo 2) Stampa il valore del nodo corrente.

Pseudo-codice per attraversare un elenco concatenato singolarmente:

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

Esempio di elenco collegato singolarmente 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);
}

Produzione:

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

Esempio di elenco collegato singolarmente in Python Programma

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

Produzione:

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

Complessità della lista semplicemente collegata

Esistono due tipi di complessità: complessità temporale e complessità spaziale. La complessità temporale del caso peggiore e medio è la stessa per la Singly Linked List.

La complessità temporale per il caso migliore:

• L'inserimento nella testa può essere effettuato in O(1). Poiché non è necessario spostarsi all'interno dell'elenco collegato.
• L'operazione di ricerca ed eliminazione può essere eseguita in O(1) se l'elemento di ricerca è presente nel nodo head.

La complessità temporale per il caso medio:

• L'inserimento all'interno di una lista concatenata richiederà O(n) se nella Lista concatenata sono presenti “n” elementi.
• Anche la ricerca e l'eliminazione possono richiedere O(n), poiché l'elemento di ricerca può essere presente nel nodo coda. In tal caso, dovresti attraversare l'intero elenco.

Complessità spaziale di una lista concatenata singolarmente

Singly Linked List alloca dinamicamente la memoria. Se vogliamo memorizzare n elementi, allocherà n unità di memoria. Quindi, la complessità dello spazio è O(n).