Puoi spiegare cos'è una lista collegata e come funziona?

Una lista collegata è una struttura dati composta da nodi, dove ogni nodo contiene dati e un riferimento al nodo successivo nella lista. A differenza degli array, le liste collegate non richiedono un blocco di memoria contiguo e consentono di inserire e rimuovere elementi in modo efficiente.

Principali tipi di liste collegate:

• Lista semplicemente collegata: ogni nodo contiene solo un riferimento al nodo successivo.
• Lista doppiamente collegata: ogni nodo contiene riferimenti sia al nodo successivo che a quello precedente.

Esempio di lista semplicemente collegata in JavaScript (Node.js):

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  add(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }
}

Le liste collegate sono utili quando si necessita di modificare dinamicamente la dimensione della struttura e di frequenti inserimenti/cancellazioni di elementi.