Elenco collegato singolarmente nelle strutture dati

Che cos'è una lista collegata singolarmente?

La lista concatenata singola è una struttura dati lineare e unidirezionale in cui i dati vengono salvati sui nodi e ogni nodo è collegato tramite un collegamento al nodo successivo. Ogni nodo contiene un campo dati e un collegamento al nodo successivo. Le liste concatenate singole possono essere attraversate in una sola direzione, mentre una lista concatenata singola può essere percorsa in una sola direzione. Elenco doppiamente collegato può essere percorso in entrambe le direzioni.

Ecco la struttura dei nodi di una lista concatenata singola:

Struttura di un nodo in una lista concatenata

Perché utilizzare una lista concatenata anziché un array?

Diversi scenari favoriscono una lista concatenata rispetto a un Italia:

• Numero sconosciuto di elementi: Quando il numero di elementi richiesti non è noto in fase di compilazione, una lista concatenata alloca la memoria dinamicamente man mano che vengono aggiunti gli elementi.
• Accesso casuale: Quando non è necessario l'accesso casuale indicizzato, una lista concatenata rappresenta una scelta adeguata.
• Inserimento al centro: L'inserimento al centro di un array richiede lo spostamento degli elementi. Una lista concatenata consente l'inserimento in qualsiasi posizione riscrivendo solo pochi puntatori.

Operazioni della lista collegata singolarmente

Una lista concatenata singola è ideale per l'allocazione dinamica della memoria. Supporta le operazioni standard delle liste concatenate, ovvero inserimento, cancellazione, ricerca, aggiornamento, unione di due liste e attraversamento.

In questo articolo vengono trattate le seguenti operazioni:

• 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 lista concatenata con quattro nodi.

Esempio di un elenco collegato singolarmente

Inserimento all'inizio di una lista concatenata singolarmente

Si tratta di un'operazione semplice, generalmente nota come "inserimento" in una lista concatenata singolarmente. Viene creato un nuovo nodo che viene posizionato all'inizio della lista.

Per eseguire questa operazione, è necessario rispettare due condizioni importanti:

1. Se l'elenco è vuoto, il nodo appena creato diventa il nodo principale e il suo GENERAZIONE Il puntatore è NULL.
2. Se l'elenco non è vuoto, il nuovo nodo diventa il nodo principale e il suo GENERAZIONE Il puntatore punta al nodo di testa precedente.

Ecco lo pseudocodice 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 in testa

Inserimento alla fine di una lista concatenata singolarmente

Inserire un nodo alla fine di una lista concatenata è simile a inserirlo all'inizio. Attraversa fino al nodo di coda, quindi punta il suo GENERAZIONE Puntatore al nuovo nodo. Se head è NULL, il nuovo nodo diventa head.

Passo 1) Attraversare fino al GENERAZIONE Il puntatore del nodo corrente diventa NULL.

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

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

Pseudocodice per l'inserimento in coda a una lista singola:

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

Inserimento in coda

Inserimento dopo un nodo in una lista concatenata singolarmente

L'inserimento dopo un nodo si compone di due fasi: cercare il nodo di destinazione e aggiungere un nuovo nodo dopo di esso. Si scorre l'elenco fino a trovare una corrispondenza, quindi si inserisce il nuovo nodo.

Passo 1) Procedi fino a quando il valore del nodo corrente non corrisponde all'elemento cercato.

Passo 2) Imposta il nuovo nodo GENERAZIONE puntatore al nodo corrente GENERAZIONE puntatore.

Passo 3) Puntare il nodo corrente GENERAZIONE puntatore al nuovo nodo.

Pseudo-codice:

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

Inserimento di un nodo dopo un nodo nella Lista concatenata singolarmente

Inserimento prima di un nodo in una lista concatenata singolarmente

Questo è simile all'inserimento dopo un nodo. Si scorre fino al nodo successivo che corrisponde al valore di ricerca, quindi si inserisce il nuovo nodo prima di esso.

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

Passo 2) Crea un nuovo nodo e impostalo GENERAZIONE puntatore al nodo corrente GENERAZIONE.

Passo 3) Puntare il nodo corrente GENERAZIONE al nuovo nodo.

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

Inserimento di un nodo prima di un nodo nella Lista concatenata singolarmente

Elimina l'intestazione della lista concatenata singolarmente

Il puntatore alla testa del nodo viene fornito come parametro. Il nodo di testa viene rimosso e il nodo successivo diventa la nuova testa. La memoria del nodo eliminato deve essere liberata per evitare perdite di memoria.

Passo 1) Assegna il nodo successivo alla testa come nuova testa.

Passo 2) Liberare la memoria allocata dal nodo precedente.

Passo 3) Restituisce il nuovo nodo head.

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

Eliminazione dell'inizio di una lista concatenata

Elimina la coda della lista concatenata singolarmente

L'eliminazione del nodo di coda è simile all'eliminazione del nodo di testa. La differenza è che è necessario attraversare la fine della lista. In una lista concatenata singolarmente, il nodo il cui GENERAZIONE il puntatore è NULL è il nodo di coda.

Passo 1) Proseguite fino a poco prima del nodo terminale. Salvate il nodo corrente.

Passo 2) Libera la memoria del nodo successivo (la coda).

Passo 3) Imposta il nodo successivo al nodo corrente su NULL.

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

Eliminazione della coda della lista collegata singolarmente

Cercare ed eliminare un nodo da una lista concatenata singolarmente

Questa funzione esegue due compiti: ricerca ed eliminazione. Attraversa fino alla fine dell'elenco. Se viene trovato un nodo corrispondente, rimuovilo e ricollega il nodo precedente. GENERAZIONE puntatore.

Passo 1) Scorri l'elenco fino alla fine. Verifica se il nodo corrente corrisponde al nodo cercato.

Passo 2) Se viene trovata una corrispondenza, memorizza un puntatore al nodo corrente.

Passo 3) Migliori GENERAZIONE del nodo precedente diventa il nodo successivo del nodo corrente.

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

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)

Cerca ed elimina un nodo dall'elenco collegato singolarmente

Attraversare una lista concatenata singolarmente

Una lista concatenata singola supporta solo l'attraversamento dalla testa alla coda. Non esiste un puntatore al nodo precedente, quindi l'attraversamento inverso non è possibile. Ogni nodo viene visitato a turno, stampandone il valore fino a quando non viene raggiunto NULL.

Passo 1) Percorri ciascun nodo fino a raggiungere NULL.

Passo 2) Stampa il valore del nodo corrente.

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

Uscita

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

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

Uscita

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à: la complessità temporale e la complessità spaziale. La complessità temporale nel caso peggiore e nel caso medio è la stessa per una lista concatenata singola.

Complessità temporale nel caso migliore:

• L'inserimento all'inizio può essere effettuato in O(1). Non è necessario attraversare l'interno della lista.
• La ricerca e la cancellazione possono essere effettuate in O(1) se l'elemento di destinazione si trova nel nodo iniziale.

Complessità temporale media:

• L'inserimento in una lista concatenata richiede O(n), dove n è il numero totale di elementi.
• Anche le operazioni di ricerca e cancellazione possono richiedere O(n), poiché l'elemento di destinazione può trovarsi ovunque, fino al nodo finale.

Complessità spaziale della lista concatenata singola

Una lista concatenata singola alloca dinamicamente la memoria. Per memorizzare n elementi, assegna n unità di memoria. Quindi la complessità spaziale è O(n).

Applicazioni delle liste concatenate singolarmente

Le liste concatenate singolarmente compaiono in molti contesti in cui l'attraversamento in avanti e la memoria dinamica risultano utili:

• Pile e code: Archiviazione sottostante per stack LIFO e code FIFO costruite a partire dai nodi.
• Concatenamento delle tabelle hash: Le collisioni vengono risolte concatenando le voci in una lista concatenata singola per ogni bucket.
• Liste di adiacenza: I grafi sparsi utilizzano una lista concatenata singola (Singly Linked List) dei vicini per ogni vertice.
• Tabelle dei simboli: I compilatori e gli interpreti concatenano gli identificatori in una lista concatenata singola per ogni ambito.
• Allocatori di memoria: Allocatori di liste libere track blocchi liberi come lista concatenata singolarmente.

DOMANDE FREQUENTI