Articolo originale: https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/

Se stai imparando le strutture di dati, un elenco collegato è una struttura di dati che dovresti conoscere. Se non lo comprendi totalmente o come viene implementato in JavaScript, questo articolo è qui per aiutarti.

In questo articolo, discuteremo cos'è un elenco collegato, in che modo è diverso da un array e come implementarlo in JavaScript. Iniziamo.

Che cos'è un elenco collegato?


Un elenco collegato è una struttura di dati lineare simile a un array. Tuttavia, a differenza degli array, gli elementi non vengono archiviati in una particolare posizione di memoria o indice . Piuttosto ogni elemento è un oggetto separato che contiene un puntatore o un collegamento all'oggetto successivo in quell'elenco.

Ogni elemento (comunemente chiamato nodo) contiene due elementi: i dati memorizzati e un collegamento al nodo successivo. I dati possono essere qualsiasi tipo di dati valido. Puoi vederlo illustrato nel diagramma seguente.

Immagine di un elenco collegato

Il punto di ingresso di un elenco collegato è chiamato testa. La testa è un riferimento al primo nodo nell'elenco collegato. L'ultimo nodo dell'elenco punta a null. Se un elenco è vuoto, l'intestazione è un riferimento nullo.

In JavaScript, un elenco collegato è simile al seguente:

const list = {
    head: {
        value: 6
        next: {
            value: 10                                             
            next: {
                value: 12
                next: {
                    value: 3
                    next: null	
                    }
                }
            }
        }
    }
};

Un vantaggio delle liste collegate

  • I nodi possono essere facilmente rimossi o aggiunti da un elenco collegate senza riorganizzare l'intera struttura dei dati. Questo è un vantaggio rispetto agli array.

Svantaggi delle liste collegate

  • Le operazioni di ricerca sono lente negli elenchi collegati. A differenza degli array, non è consentito l'accesso casuale agli elementi di dati. Si accede ai nodi in modo sequenziale a partire dal primo nodo.
  • Utilizza più memoria degli array a causa dell'archiviazione dei puntatori.

Tipi di elenchi collegati

Esistono tre tipi di elenchi collegati:

  • Elenchi collegati singolarmente : ogni nodo contiene un solo puntatore al nodo successivo. Questo è ciò di cui abbiamo parlato finora.
  • Elenchi doppiamente collegati: ogni nodo contiene due puntatori, un puntatore al nodo successivo e un puntatore al nodo precedente.
  • Elenchi collegati circolari: gli elenchi collegati circolari sono una variazione di un elenco collegato in cui l'ultimo nodo punta al primo nodo o a qualsiasi altro nodo precedente, formando così un anello.

Implementazione di un nodo elenco in JavaScript

Come affermato in precedenza, un nodo elenco contiene due elementi: i dati e il puntatore al nodo successivo. Possiamo implementare un nodo elenco in JavaScript come segue:

class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

Implementazione di un elenco collegato in JavaScript

Il codice seguente mostra l'implementazione di una classe di elenco collegato con un costruttore. Si noti che se l'head del nodo non viene passato, l'head viene inizializzato su null.

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

Mettiamo tutto insieme

Creiamo un elenco collegato con la classe che abbiamo appena creato. Innanzitutto, creiamo due nodi elenco node1 e node2 e un puntatore dal nodo 1 al nodo 2.

let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2

Successivamente, creeremo un elenco collegato con node1.

let list = new LinkedList(node1)

Proviamo ad accedere ai nodi nella lista che abbiamo appena creato.

console.log(list.head.next.data) // restituisce 5

Alcuni metodi LinkedList

Successivamente, implementeremo quattro metodi di supporto per l'elenco collegato. Questi sono:

  1. size()
  2. clear()
  3. getLast()
  4. getFirst()

1. size()

Questo metodo restituisce il numero di nodi presenti nell'elenco collegato.

size() {
    let count = 0; 
    let node = this.head;
    while (node) {
        count++;
        node = node.next
    }
    return count;
}

2. clear()

Questo metodo svuota l'elenco.

clear() {
    this.head = null;
}

3. getLast()

Questo metodo restituisce l'ultimo nodo dell'elenco collegato.

getLast() {
    let lastNode = this.head;
    if (lastNode) {
        while (lastNode.next) {
            lastNode = lastNode.next
        }
    }
    return lastNode
}

4. getFirst()

Questo metodo restituisce il primo nodo dell'elenco collegato.

getFirst() {
    return this.head;
}

In questo articolo, abbiamo discusso di cos'è un elenco collegato e di come può essere implementato in JavaScript. Abbiamo anche discusso i diversi tipi di elenchi collegati, nonché i loro complessivi vantaggi e svantaggi .

Spero che ti sia piaciuto leggerlo.

Vuoi ricevere una notifica quando pubblico un nuovo articolo? Clicca qui .