Double Linked Lists

Introduzione

Le double linked lists (liste doppiamente collegate) sono una struttura dati che estende le linked lists semplici aggiungendo la capacità di navigare in entrambe le direzioni. Ogni nodo contiene un puntatore al nodo successivo (next) e uno al nodo precedente (prev), permettendo di attraversare la lista sia in avanti che all’indietro.

Confronto con Singly Linked Lists

Le double linked lists differiscono dalle singly linked lists in un aspetto fondamentale:

1. Navigazione bidirezionale: ogni nodo ha sia un puntatore next che prev
2. Pop più efficiente: rimuovere l’ultimo elemento è O(1) invece di O(n)
3. Get ottimizzato: il metodo get può partire da tail se l’indice è nella seconda metà della lista
4. Maggiore complessità: ogni operazione deve gestire sia i puntatori next che prev

Struttura delle Double Linked Lists

Componenti principali

Una double 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, un puntatore al nodo successivo (next) e uno al nodo precedente (prev)
• Null terminated: il primo nodo ha prev = null e l’ultimo nodo ha next = null

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

Ogni nodo punta sia al successivo che al precedente, creando una catena bidirezionale.

Struttura interna dei nodi

Cosa è un nodo

Un nodo in una double linked list è un oggetto composto da:

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

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

4
// Struttura reale in memoria
5
{
6
  value: 7,
7
  next: {
8
    value: 4,
9
    next: null,
10
    prev: { /* riferimento al nodo 7 */ }
11
  },
12
  prev: null
13
}

Come funziona il puntamento bidirezionale

Quando diciamo che un nodo “punta” a un altro, stiamo impostando sia next che prev:

1
// Il nodo con valore 7 punta al nodo con valore 4 (next)
2
// Il nodo con valore 4 punta al nodo con valore 7 (prev)
3
node7.next = node4;  // Puntatore in avanti
4
node4.prev = node7;  // Puntatore all'indietro

Struttura completa di una double linked list

Una double linked list è quindi un insieme di oggetti annidati con riferimenti bidirezionali:

1
// Esempio: null ← [11] ⇄ [3] ⇄ [23] ⇄ [7] → null
2
{
3
  head: {
4
    value: 11,
5
    next: { /* nodo 3 */ },
6
    prev: null
7
  },
8
  tail: {
9
    value: 7,
10
    next: null,
11
    prev: { /* nodo 23 */ }
12
  },
13
  length: 4
14
}

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

Complessità temporale (Big O)

Le double linked lists hanno complessità simili alle singly linked lists, con alcune differenze importanti:

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(1) - possiamo usare tail.prev direttamente (miglioramento rispetto a O(n) delle singly linked lists)
• 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) - ma può essere ottimizzato: se l’indice è nella prima metà parte da head, altrimenti da tail (O(n/2) nel caso migliore)
• Lookup by Value: O(n) - dobbiamo iterare confrontando ogni valore

Nota importante: Il metodo get può essere ottimizzato nelle double linked lists: se l’indice è nella seconda metà della lista, si parte da tail e si va all’indietro, riducendo il numero di iterazioni.

Confronto Double Linked Lists vs Singly Linked Lists

Ecco una tabella comparativa delle complessità temporali:

Legenda: Verde = O(1) efficiente | Giallo = O(n/2) ottimizzato | Rosso = O(n) meno efficiente

Nota: La differenza principale è che pop è O(1) nelle double linked lists grazie ai puntatori prev, e get può essere ottimizzato partendo da tail se l’indice è nella seconda metà.

Quando usare Double Linked Lists

Le double linked lists sono migliori quando:

• Devi rimuovere spesso dalla fine: pop è O(1) invece di O(n) delle singly linked lists
• Devi navigare all’indietro nella lista
• Hai bisogno di lookup ottimizzati quando l’indice è nella seconda metà della lista

Le singly linked lists sono migliori quando:

• Non hai bisogno di navigazione all’indietro
• Vuoi risparmiare memoria (ogni nodo ha un puntatore in meno)
• La semplicità del codice è più importante delle prestazioni

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 double linked list, creiamo una classe separata per i nodi. La differenza principale rispetto alle singly linked lists è la presenza del puntatore prev.

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 in avanti
7
    this.next = null;
8
    // Inizialmente il nodo non punta a nulla all'indietro
9
    this.prev = null;
10
  }
11
}
12

13
// Esempio di utilizzo
14
const newNode = new Node(4);
15
// Crea un oggetto: { value: 4, next: null, prev: 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 DoublyLinkedList

Il costruttore inizializza una double linked list con il primo nodo:

1
class DoublyLinkedList {
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 myDoublyLinkedList = new DoublyLinkedList(4);
20
// Crea una double 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, next: null e prev: 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, prev: null },
3
  tail: { value: 4, next: null, prev: 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. Il nuovo nodo punta all’ultimo nodo (newNode.prev = tail) - differenza rispetto alle singly linked lists
4. 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 (puntatore in avanti)
11
    this.tail.next = newNode;
12
    // Il nuovo nodo punta all'ultimo nodo (puntatore all'indietro)
13
    newNode.prev = this.tail;
14
    // Tail viene aggiornato per puntare al nuovo nodo
15
    this.tail = newNode;
16
  }
17

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

Differenza con singly linked lists: L’unica riga aggiuntiva è newNode.prev = this.tail, che collega il puntatore all’indietro del nuovo nodo.

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 (newNode.next = this.head)
3. Il primo nodo punta al nuovo nodo (this.head.prev = newNode) - differenza rispetto alle singly linked lists
4. 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 (puntatore in avanti)
11
    newNode.next = this.head;
12
    // Il primo nodo punta al nuovo nodo (puntatore all'indietro)
13
    this.head.prev = newNode;
14
    // Head viene aggiornato per puntare al nuovo nodo
15
    this.head = newNode;
16
  }
17

18
  // Incrementa la lunghezza
19
  this.length++;
20
  return this;
21
}

Differenza con singly linked lists: La riga aggiuntiva è this.head.prev = newNode, che collega il puntatore all’indietro del primo nodo.

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 false
2. Trova il nodo precedente all’indice desiderato
3. Il nuovo nodo punta al nodo che era all’indice (newNode.next = after)
4. Il nodo precedente punta al nuovo nodo (before.next = newNode)
5. Gestione puntatori prev: collega i puntatori all’indietro (newNode.prev = before e after.prev = newNode)

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 false;
10

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

14
  // Trova il nodo precedente all'indice desiderato
15
  const before = this.get(index - 1);
16
  // Trova il nodo che sarà dopo il nuovo nodo (più efficiente di usare get di nuovo)
17
  const after = before.next;
18

19
  // Il nodo precedente punta al nuovo nodo (puntatore in avanti)
20
  before.next = newNode;
21
  // Il nuovo nodo punta al nodo precedente (puntatore all'indietro)
22
  newNode.prev = before;
23
  // Il nuovo nodo punta al nodo che era all'indice (puntatore in avanti)
24
  newNode.next = after;
25
  // Il nodo dopo punta al nuovo nodo (puntatore all'indietro)
26
  after.prev = newNode;
27

28
  // Incrementa la lunghezza
29
  this.length++;
30

31
  return true;
32
}

Differenza con singly linked lists: Aggiungiamo due righe per gestire i puntatori prev: newNode.prev = before e after.prev = newNode.

Operazioni di rimozione

Pop - Rimuovere dalla fine

Rimuove l’ultimo nodo dalla lista e lo ritorna. Complessità: O(1) - miglioramento rispetto a O(n) delle singly linked lists!

Logica:

1. Salva il riferimento all’ultimo nodo (temp = this.tail)
2. Sposta tail all’indietro usando tail.prev - vantaggio delle double linked lists
3. Imposta tail.next = null per rimuovere il collegamento
4. Imposta temp.prev = null per rimuovere il collegamento all’indietro
5. 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) return undefined;
4

5
  // Salva il riferimento all'ultimo nodo
6
  let temp = this.tail;
7

8
  // Edge case: se c'è un solo nodo
9
  if (this.length === 1) {
10
    this.head = null;
11
    this.tail = null;
12
  } else {
13
    // Sposta tail all'indietro usando prev (vantaggio delle double linked lists!)
14
    this.tail = this.tail.prev;
15
    // Rimuove il collegamento in avanti
16
    this.tail.next = null;
17
    // Rimuove il collegamento all'indietro del nodo rimosso
18
    temp.prev = null;
19
  }
20

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

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

Vantaggio rispetto alle singly linked lists: Non dobbiamo iterare attraverso tutta la lista per trovare il penultimo nodo. Possiamo usare direttamente tail.prev!

Shift - Rimuovere dall’inizio

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

Logica:

1. Salva il riferimento al primo nodo (temp = this.head)
2. Sposta head al nodo successivo (head = head.next)
3. Rimuove il collegamento all’indietro del nuovo primo nodo (head.prev = null)
4. Rimuove il collegamento in avanti del nodo rimosso (temp.next = null)
5. 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.length === 0) return undefined;
4

5
  // Salva il riferimento al primo nodo
6
  let temp = this.head;
7

8
  // Edge case: se c'è un solo nodo
9
  if (this.length === 1) {
10
    this.head = null;
11
    this.tail = null;
12
  } else {
13
    // Sposta head al nodo successivo
14
    this.head = this.head.next;
15
    // Rimuove il collegamento all'indietro del nuovo primo nodo
16
    this.head.prev = null;
17
    // Rimuove il collegamento in avanti del nodo rimosso
18
    temp.next = null;
19
  }
20

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

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

Differenza con singly linked lists: Aggiungiamo this.head.prev = null per rimuovere il collegamento all’indietro.

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 da rimuovere usando get
3. Usa i puntatori prev e next per collegare i nodi adiacenti - più semplice rispetto alle singly linked lists
4. Rimuove i collegamenti 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 da rimuovere
12
  let temp = this.get(index);
13

14
  // Collega il nodo precedente al nodo successivo (puntatore in avanti)
15
  temp.prev.next = temp.next;
16
  // Collega il nodo successivo al nodo precedente (puntatore all'indietro)
17
  temp.next.prev = temp.prev;
18
  // Rimuove i collegamenti del nodo rimosso
19
  temp.next = null;
20
  temp.prev = null;
21

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

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

Vantaggio rispetto alle singly linked lists: Non abbiamo bisogno di una variabile before perché possiamo usare direttamente temp.prev e temp.next per collegare i nodi adiacenti.

Operazioni di accesso e modifica

Get - Ottenere un nodo per indice

Ritorna il nodo all’indice specificato. Complessità: O(n/2) nel caso migliore - ottimizzazione rispetto a O(n) delle singly linked lists!

Logica:

1. Valida l’indice (deve essere >= 0 e < length)
2. Ottimizzazione: se l’indice è nella prima metà, parte da head e va in avanti
3. Ottimizzazione: se l’indice è nella seconda metà, parte da tail e va all’indietro
4. 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
  let temp;
8

9
  // Ottimizzazione: se l'indice è nella prima metà, parte da head
10
  if (index < this.length / 2) {
11
    temp = this.head;
12
    // Itera in avanti fino all'indice desiderato
13
    for (let i = 0; i < index; i++) {
14
      temp = temp.next;
15
    }
16
  } else {
17
    // Ottimizzazione: se l'indice è nella seconda metà, parte da tail
18
    temp = this.tail;
19
    // Itera all'indietro fino all'indice desiderato
20
    for (let i = this.length - 1; i > index; i--) {
21
      temp = temp.prev;
22
    }
23
  }
24

25
  // Ritorna il nodo all'indice specificato
26
  return temp;
27
}

Vantaggio rispetto alle singly linked lists: Possiamo partire da tail se l’indice è nella seconda metà, riducendo il numero di iterazioni da O(n) a O(n/2) nel caso migliore.

Set - Modificare il valore di un nodo

Cambia il valore del nodo all’indice specificato. Complessità: O(n/2) nel caso migliore grazie all’ottimizzazione di get.

Logica:

1. Usa il metodo get per trovare il nodo (che è ottimizzato per partire da tail se necessario)
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 (ottimizzato!)
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
}

Nota: Il codice è identico a quello delle singly linked lists, ma get è più efficiente grazie all’ottimizzazione bidirezionale.

Implementazione completa

Ecco il codice completo delle classi Node e DoublyLinkedList:

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

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

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

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

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

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

77
  get(index) {
78
    if (index < 0 || index >= this.length) return undefined;
79
    let temp;
80
    if (index < this.length / 2) {
81
      temp = this.head;
82
      for (let i = 0; i < index; i++) {
83
        temp = temp.next;
84
      }
85
    } else {
86
      temp = this.tail;
87
      for (let i = this.length - 1; i > index; i--) {
88
        temp = temp.prev;
89
      }
90
    }
91
    return temp;
92
  }
93

94
  set(index, value) {
95
    let temp = this.get(index);
96
    if (temp) {
97
      temp.value = value;
98
      return true;
99
    }
100
    return false;
101
  }
102

103
  insert(index, value) {
104
    if (index === 0) return this.unshift(value);
105
    if (index === this.length) return this.push(value);
106
    if (index < 0 || index > this.length) return false;
107
    const newNode = new Node(value);
108
    const before = this.get(index - 1);
109
    const after = before.next;
110
    before.next = newNode;
111
    newNode.prev = before;
112
    newNode.next = after;
113
    after.prev = newNode;
114
    this.length++;
115
    return true;
116
  }
117

118
  remove(index) {
119
    if (index === 0) return this.shift();
120
    if (index === this.length - 1) return this.pop();
121
    if (index < 0 || index >= this.length) return undefined;
122
    let temp = this.get(index);
123
    temp.prev.next = temp.next;
124
    temp.next.prev = temp.prev;
125
    temp.next = null;
126
    temp.prev = null;
127
    this.length--;
128
    return temp;
129
  }
130
}

Esercizi e problemi comuni

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