Linked Lists

Introduzione

Le linked lists (liste collegate) sono una struttura dati fondamentale che differisce dagli array in alcuni aspetti chiave. Comprendere le linked lists è essenziale per capire come funzionano molte altre strutture dati più complesse.

Confronto con gli array

Le linked lists differiscono dagli array in alcuni aspetti fondamentali:

1. Nessun indice: gli array hanno indici che permettono l’accesso diretto agli elementi, le linked lists no
2. Memoria non contigua: gli array sono memorizzati in posizioni contigue in memoria, le linked lists possono essere sparse ovunque
3. Puntatori: ogni elemento in una linked list punta al successivo, creando una catena di nodi

Struttura delle Linked Lists

Componenti principali

Una linked list è composta da:

• Head: variabile che punta al primo elemento della lista
• Tail: variabile che punta all’ultimo elemento della lista
• Nodi: ogni elemento contiene un valore e un puntatore al nodo successivo
• Null terminated: l’ultimo nodo punta a null, indicando la fine della lista

1
// Rappresentazione grafica di una linked list
2
//  [11] → [3] → [23] → [7] → null
3
//    ↑                  ↑
4
//  Head                Tail

Ogni nodo punta al successivo, creando una catena. L’ultimo nodo punta a null, da qui il termine “null terminated list”.

Struttura interna dei nodi

Per capire come funziona una linked list, dobbiamo guardare cosa c’è realmente “sotto il cofano”.

Cosa è un nodo

Un nodo non è solo il valore che vediamo nella rappresentazione grafica. Un nodo è un oggetto composto da:

• value: il valore memorizzato nel nodo
• next: un puntatore al nodo successivo (o null se è l’ultimo)

1
// Rappresentazione grafica (semplificata)
2
// [7] → [4] → null
3

4
// Struttura reale in memoria
5
{
6
  value: 7,
7
  next: {
8
    value: 4,
9
    next: null
10
  }
11
}

Come funziona il puntamento

Quando diciamo che un nodo “punta” a un altro, stiamo in realtà impostando la proprietà next di un nodo per riferirsi all’oggetto del nodo successivo.

1
// Il nodo con valore 7 punta al nodo con valore 4
2
// facendo in modo che 7.next sia uguale all'oggetto del nodo 4
3
node7.next = node4; // Questo è come "puntare" al nodo successivo

Struttura completa di una linked list

Una linked list è quindi un insieme di oggetti annidati:

1
// Esempio: [11] → [3] → [23] → [7] → null
2
{
3
  head: {
4
    value: 11,
5
    next: {
6
      value: 3,
7
      next: {
8
        value: 23,
9
        next: {
10
          value: 7,
11
          next: null
12
        }
13
      }
14
    }
15
  },
16
  tail: {
17
    value: 7,
18
    next: null
19
  },
20
  length: 4
21
}

head punta al primo oggetto nodo, mentre tail punta all’ultimo oggetto nodo. Entrambi sono riferimenti (puntatori) agli stessi oggetti nella catena.

Complessità temporale (Big O)

Prima di implementare i metodi, analizziamo la complessità temporale delle operazioni principali sulle linked lists per capire quando usarle.

Operazioni di aggiunta

• Push (fine): O(1) - abbiamo già un puntatore all’ultimo nodo (tail)
• Unshift (inizio): O(1) - abbiamo già un puntatore al primo nodo (head)
• Insert (mezzo): O(n) - dobbiamo iterare fino alla posizione desiderata

Operazioni di rimozione

• Pop (fine): O(n) - dobbiamo iterare per trovare il penultimo nodo
• Shift (inizio): O(1) - abbiamo già un puntatore al primo nodo (head)
• Remove (mezzo): O(n) - dobbiamo iterare fino alla posizione desiderata

Operazioni di accesso

• Lookup by Index: O(n) - dobbiamo partire da head e iterare
• Lookup by Value: O(n) - dobbiamo iterare confrontando ogni valore

Nota importante: Negli array possiamo accedere a un indice in O(1), nelle linked lists dobbiamo sempre iterare. Questo è una differenza fondamentale.

Confronto Linked Lists vs Array

Ecco una tabella comparativa delle complessità temporali:

Legenda: Verde = O(1) efficiente | Rosso = O(n) meno efficiente

Nota: Le operazioni evidenziate mostrano dove una struttura dati è più efficiente dell’altra. Le linked lists sono migliori per operazioni all’inizio (shift/unshift), mentre gli array sono migliori per pop e lookup by index.

Quando usare Linked Lists

Le linked lists sono migliori quando:

• Devi aggiungere/rimuovere spesso dall’inizio: unshift e shift sono O(1) invece di O(n) degli array
• Non hai bisogno di lookup by index frequente

Gli array sono migliori quando:

• Devi accedere spesso per indice (lookup by index): O(1) vs O(n) delle linked lists
• Devi rimuovere dalla fine: pop è O(1) vs O(n) delle linked lists

La scelta dipende dalle operazioni che esegui più frequentemente. Considera la Big O delle operazioni principali per il tuo caso d’uso specifico.

Implementazione

Classe Node

Prima di implementare la linked list, creiamo una classe separata per i nodi. Questo ci permette di riutilizzare il codice di creazione dei nodi in più metodi (constructor, push, unshift, insert).

1
// Classe per creare un singolo nodo
2
class Node {
3
  constructor(value) {
4
    // Assegna il valore passato al costruttore
5
    this.value = value;
6
    // Inizialmente il nodo non punta a nulla
7
    this.next = null;
8
  }
9
}
10

11
// Esempio di utilizzo
12
const newNode = new Node(4);
13
// Crea un oggetto: { value: 4, next: null }

Perché una classe separata? I metodi constructor, push, unshift e insert hanno tutti bisogno di creare nuovi nodi. Invece di riscrivere il codice ogni volta, usiamo la classe Node.

Costruttore della LinkedList

Il costruttore inizializza una linked list con il primo nodo:

1
class LinkedList {
2
  constructor(value) {
3
    // Crea il primo nodo con il valore passato
4
    const newNode = new Node(value);
5

6
    // Head punta al primo nodo (il nuovo nodo appena creato)
7
    this.head = newNode;
8

9
    // Tail punta allo stesso nodo di head (quando c'è un solo nodo)
10
    // Equivale a: this.tail = newNode
11
    this.tail = this.head;
12

13
    // La lista inizia con lunghezza 1
14
    this.length = 1;
15
  }
16
}
17

18
// Esempio di utilizzo
19
const myLinkedList = new LinkedList(4);
20
// Crea una linked list con un nodo di valore 4
21
// head e tail puntano entrambi a questo nodo
22
// length = 1

Spiegazione del costruttore:

1. Crea il primo nodo: new Node(value) crea un oggetto con value e next: null
2. Imposta head: this.head = newNode fa sì che head punti al nuovo nodo
3. Imposta tail: this.tail = this.head fa sì che tail punti allo stesso oggetto di head (quando c’è un solo nodo, sono la stessa cosa)
4. Inizializza length: this.length = 1 perché abbiamo creato un nodo

Risultato in memoria:

1
{
2
  head: { value: 4, next: null },
3
  tail: { value: 4, next: null },  // punta allo stesso oggetto di head
4
  length: 1
5
}

head e tail sono entrambi riferimenti allo stesso oggetto nodo. Quando aggiungeremo altri nodi, tail verrà aggiornato per puntare all’ultimo nodo della catena.

Operazioni di aggiunta

Push - Aggiungere alla fine

Aggiunge un nodo alla fine della lista. Complessità: O(1)

Logica:

1. Crea un nuovo nodo
2. L’ultimo nodo punta al nuovo nodo (tail.next = newNode)
3. tail viene aggiornato per puntare al nuovo nodo

Edge case: Se la lista è vuota, head e tail puntano entrambi al nuovo nodo.

1
push(value) {
2
  // Crea il nuovo nodo
3
  const newNode = new Node(value);
4

5
  // Se la lista è vuota, head e tail puntano al nuovo nodo
6
  if (!this.head) {
7
    this.head = newNode;
8
    this.tail = newNode;
9
  } else {
10
    // L'ultimo nodo punta al nuovo nodo
11
    this.tail.next = newNode;
12
    // Tail viene aggiornato per puntare al nuovo nodo
13
    this.tail = newNode;
14
  }
15

16
  // Incrementa la lunghezza
17
  this.length++;
18
  return this; // Ritorna l'intera linked list
19
}

Unshift - Aggiungere all’inizio

Aggiunge un nodo all’inizio della lista. Complessità: O(1)

Logica:

1. Crea un nuovo nodo
2. Il nuovo nodo punta al nodo attualmente puntato da head
3. head viene aggiornato per puntare al nuovo nodo

Edge case: Se la lista è vuota, head e tail puntano entrambi al nuovo nodo.

1
unshift(value) {
2
  // Crea il nuovo nodo
3
  const newNode = new Node(value);
4

5
  // Se la lista è vuota, head e tail puntano al nuovo nodo
6
  if (!this.head) {
7
    this.head = newNode;
8
    this.tail = newNode;
9
  } else {
10
    // Il nuovo nodo punta al primo nodo attuale
11
    newNode.next = this.head;
12
    // Head viene aggiornato per puntare al nuovo nodo
13
    this.head = newNode;
14
  }
15

16
  // Incrementa la lunghezza
17
  this.length++;
18
  return this;
19
}

Insert - Inserire in una posizione specifica

Inserisce un nuovo nodo all’indice specificato. Complessità: O(n)

Logica:

1. Edge cases:
   • Indice 0: usa unshift
   • Indice = length: usa push
   • Indice non valido: ritorna undefined
2. Trova il nodo precedente all’indice desiderato
3. Il nuovo nodo punta al nodo che era all’indice
4. Il nodo precedente punta al nuovo nodo

1
insert(index, value) {
2
  // Edge case: inserimento all'inizio
3
  if (index === 0) return this.unshift(value);
4

5
  // Edge case: inserimento alla fine
6
  if (index === this.length) return this.push(value);
7

8
  // Edge case: indice non valido
9
  if (index < 0 || index > this.length) return undefined;
10

11
  // Crea il nuovo nodo
12
  const newNode = new Node(value);
13

14
  // Trova il nodo precedente all'indice desiderato
15
  const temp = this.get(index - 1);
16

17
  // Il nuovo nodo punta al nodo che era all'indice
18
  newNode.next = temp.next;
19
  // Il nodo precedente punta al nuovo nodo
20
  temp.next = newNode;
21

22
  // Incrementa la lunghezza
23
  this.length++;
24

25
  return true;
26
}

Operazioni di rimozione

Pop - Rimuovere dalla fine

Rimuove l’ultimo nodo dalla lista e lo ritorna. Complessità: O(n)

Logica:

1. Trova il penultimo nodo (iterando da head)
2. Aggiorna tail per puntare al penultimo nodo
3. Imposta tail.next = null per rimuovere l’ultimo nodo
4. Ritorna il nodo rimosso

Edge cases:

• Lista vuota: ritorna undefined
• Un solo nodo: dopo la rimozione, head e tail devono puntare a null

1
pop() {
2
  // Se la lista è vuota, ritorna undefined
3
  if (this.length === 0) {
4
    return undefined;
5
  }
6

7
  // Due variabili per iterare: temp (ultimo nodo) e pre (penultimo nodo)
8
  let temp = this.head;
9
  let pre = this.head;
10

11
  // Itera fino alla fine: quando temp.next è null, temp è l'ultimo nodo
12
  while (temp.next) {
13
    pre = temp;        // pre diventa il nodo precedente
14
    temp = temp.next;  // temp si sposta al nodo successivo
15
  }
16

17
  // Aggiorna tail per puntare al penultimo nodo
18
  this.tail = pre;
19
  // Rimuove il collegamento all'ultimo nodo
20
  this.tail.next = null;
21

22
  // Decrementa la lunghezza
23
  this.length--;
24

25
  // Edge case: se dopo la rimozione la lista è vuota
26
  if (this.length === 0) {
27
    this.head = null;
28
    this.tail = null;
29
  }
30

31
  // Ritorna il nodo rimosso
32
  return temp;
33
}

Shift - Rimuovere dall’inizio

Rimuove il primo nodo dalla lista e lo ritorna. Complessità: O(1)

Logica:

1. Sposta head al nodo successivo (head = head.next)
2. Rimuove il collegamento del primo nodo (temp.next = null)
3. Ritorna il nodo rimosso

Edge cases:

• Lista vuota: ritorna undefined
• Un solo nodo: dopo la rimozione, tail deve puntare a null

1
shift() {
2
  // Se la lista è vuota, ritorna undefined
3
  if (!this.head) return undefined;
4

5
  // Salva il riferimento al primo nodo
6
  let temp = this.head;
7
  // Sposta head al nodo successivo
8
  this.head = this.head.next;
9
  // Rimuove il collegamento del nodo rimosso
10
  temp.next = null;
11

12
  // Decrementa la lunghezza
13
  this.length--;
14

15
  // Edge case: se dopo la rimozione la lista è vuota
16
  if (this.length === 0) {
17
    this.tail = null;
18
  }
19

20
  // Ritorna il nodo rimosso
21
  return temp;
22
}

Remove - Rimuovere da una posizione specifica

Rimuove il nodo all’indice specificato e lo ritorna. Complessità: O(n)

Logica:

1. Edge cases:
   • Indice 0: usa shift
   • Indice = length - 1: usa pop
   • Indice non valido: ritorna undefined
2. Trova il nodo precedente a quello da rimuovere
3. Il nodo precedente punta al nodo successivo a quello rimosso
4. Rimuove il collegamento del nodo rimosso
5. Ritorna il nodo rimosso

1
remove(index) {
2
  // Edge case: rimozione dall'inizio
3
  if (index === 0) return this.shift();
4

5
  // Edge case: rimozione dalla fine
6
  if (index === this.length - 1) return this.pop();
7

8
  // Edge case: indice non valido
9
  if (index < 0 || index >= this.length) return undefined;
10

11
  // Trova il nodo precedente a quello da rimuovere
12
  const before = this.get(index - 1);
13
  // Il nodo da rimuovere (più efficiente di usare get di nuovo)
14
  const temp = before.next;
15

16
  // Il nodo precedente punta al nodo successivo a quello rimosso
17
  before.next = temp.next;
18
  // Rimuove il collegamento del nodo rimosso
19
  temp.next = null;
20

21
  // Decrementa la lunghezza
22
  this.length--;
23

24
  // Ritorna il nodo rimosso
25
  return temp;
26
}

Operazioni di accesso e modifica

Get - Ottenere un nodo per indice

Ritorna il nodo all’indice specificato. Complessità: O(n)

Logica:

1. Valida l’indice (deve essere >= 0 e < length)
2. Itera dalla testa fino all’indice desiderato
3. Ritorna il nodo trovato

1
get(index) {
2
  // Valida l'indice: deve essere valido
3
  if (index < 0 || index >= this.length) {
4
    return undefined;
5
  }
6

7
  // Parte dalla testa
8
  let temp = this.head;
9

10
  // Itera fino all'indice desiderato
11
  for (let i = 0; i < index; i++) {
12
    temp = temp.next; // Sposta temp al nodo successivo
13
  }
14

15
  // Ritorna il nodo all'indice specificato
16
  return temp;
17
}

Set - Modificare il valore di un nodo

Cambia il valore del nodo all’indice specificato. Complessità: O(n)

Logica:

1. Usa il metodo get per trovare il nodo
2. Se il nodo esiste, aggiorna il suo valore
3. Ritorna true se l’operazione è riuscita, false altrimenti

1
set(index, value) {
2
  // Usa get per trovare il nodo all'indice specificato
3
  let temp = this.get(index);
4

5
  // Se il nodo esiste, aggiorna il valore
6
  if (temp) {
7
    temp.value = value;
8
    return true; // Operazione riuscita
9
  }
10

11
  // Se l'indice non è valido, ritorna false
12
  return false;
13
}

Operazioni speciali

Reverse - Invertire la lista

Inverte l’ordine dei nodi nella lista. Complessità: O(n)

Logica:

1. Scambia head e tail
2. Itera attraverso la lista invertendo le direzioni dei puntatori
3. Usa tre variabili: temp (nodo corrente), next (prossimo nodo), prev (nodo precedente)

1
reverse() {
2
  // Scambia head e tail
3
  let temp = this.head;
4
  this.head = this.tail;
5
  this.tail = temp;
6

7
  // Variabili per iterare e invertire i puntatori
8
  let next = temp.next; // Prossimo nodo dopo temp
9
  let prev = null;      // Nodo precedente (inizia da null)
10

11
  // Itera attraverso tutta la lista
12
  for (let i = 0; i < this.length; i++) {
13
    // Salva il prossimo nodo prima di modificare temp.next
14
    next = temp.next;
15
    // Inverte il puntatore: temp punta al nodo precedente
16
    temp.next = prev;
17
    // prev si sposta al nodo corrente
18
    prev = temp;
19
    // temp si sposta al prossimo nodo
20
    temp = next;
21
  }
22

23
  return this;
24
}

Implementazione completa

Ecco il codice completo delle classi Node e LinkedList:

1
// Classe per creare un singolo nodo
2
class Node {
3
  constructor(value) {
4
    this.value = value;
5
    this.next = null;
6
  }
7
}
8

9
// Classe per la linked list
10
class LinkedList {
11
  constructor(value) {
12
    const newNode = new Node(value);
13
    this.head = newNode;
14
    this.tail = this.head;
15
    this.length = 1;
16
  }
17

18
  push(value) {
19
    const newNode = new Node(value);
20
    if (!this.head) {
21
      this.head = newNode;
22
      this.tail = newNode;
23
    } else {
24
      this.tail.next = newNode;
25
      this.tail = newNode;
26
    }
27
    this.length++;
28
    return this;
29
  }
30

31
  pop() {
32
    if (this.length === 0) return undefined;
33
    let temp = this.head;
34
    let pre = this.head;
35
    while (temp.next) {
36
      pre = temp;
37
      temp = temp.next;
38
    }
39
    this.tail = pre;
40
    this.tail.next = null;
41
    this.length--;
42
    if (this.length === 0) {
43
      this.head = null;
44
      this.tail = null;
45
    }
46
    return temp;
47
  }
48

49
  unshift(value) {
50
    const newNode = new Node(value);
51
    if (!this.head) {
52
      this.head = newNode;
53
      this.tail = newNode;
54
    } else {
55
      newNode.next = this.head;
56
      this.head = newNode;
57
    }
58
    this.length++;
59
    return this;
60
  }
61

62
  shift() {
63
    if (!this.head) return undefined;
64
    let temp = this.head;
65
    this.head = this.head.next;
66
    temp.next = null;
67
    this.length--;
68
    if (this.length === 0) {
69
      this.tail = null;
70
    }
71
    return temp;
72
  }
73

74
  get(index) {
75
    if (index < 0 || index >= this.length) return undefined;
76
    let temp = this.head;
77
    for (let i = 0; i < index; i++) {
78
      temp = temp.next;
79
    }
80
    return temp;
81
  }
82

83
  set(index, value) {
84
    let temp = this.get(index);
85
    if (temp) {
86
      temp.value = value;
87
      return true;
88
    }
89
    return false;
90
  }
91

92
  insert(index, value) {
93
    if (index === 0) return this.unshift(value);
94
    if (index === this.length) return this.push(value);
95
    if (index < 0 || index > this.length) return undefined;
96
    const newNode = new Node(value);
97
    const temp = this.get(index - 1);
98
    newNode.next = temp.next;
99
    temp.next = newNode;
100
    this.length++;
101
    return true;
102
  }
103

104
  remove(index) {
105
    if (index === 0) return this.shift();
106
    if (index === this.length - 1) return this.pop();
107
    if (index < 0 || index >= this.length) return undefined;
108
    const before = this.get(index - 1);
109
    const temp = before.next;
110
    before.next = temp.next;
111
    temp.next = null;
112
    this.length--;
113
    return temp;
114
  }
115

116
  reverse() {
117
    let temp = this.head;
118
    this.head = this.tail;
119
    this.tail = temp;
120
    let next = temp.next;
121
    let prev = null;
122
    for (let i = 0; i < this.length; i++) {
123
      next = temp.next;
124
      temp.next = prev;
125
      prev = temp;
126
      temp = next;
127
    }
128
    return this;
129
  }
130
}

Esercizi e problemi comuni

Per praticare e approfondire le linked lists, consulta la sezione dedicata agli esercizi e problemi comuni