Quindi, parlami degli elenchi collegati
Mi sono recentemente laureato in un bootcamp di codifica, ho studiato a fondo le strutture di dati e gli algoritmi per migliorare le mie conoscenze fondamentali. Gli elenchi collegati sono una struttura di dati relativamente semplice, ma è la base per strutture di dati più complesse che vanno avanti. Questo articolo discuterà degli elenchi collegati: i loro punti di forza, di debolezza e come implementarli.
Le strutture dati sono, in parole povere, modi per organizzare e conservare i dati in modo efficiente
Cosa sono le strutture dati?
Le strutture dati sono, in parole povere, modi per organizzare e conservare i dati in modo efficiente. Questi ci consentono di conservare le informazioni in modo che possiamo accedervi in seguito, cercando un elemento specifico o ordinandole per avere un certo ordine o persino gestendo grandi set di dati. JavaScript ha strutture di dati che probabilmente conosci molto bene: array e oggetti. Si tratta di strutture dati primitive native della lingua. Le strutture dati non primitive sono strutture dati definite dal programmatore. Gli esempi includono pile, code, alberi, grafici e tabelle hash.
Cosa sono gli elenchi collegati?
Un elenco collegato è una struttura dati lineare che contiene gli elementi in ordine sequenziale. Suona familiare? Sono simili agli array ma non sono proprio la stessa cosa. Gli array sono indicizzati a zero , il che significa che ogni indice è mappato a un valore e il primo elemento dell'array inizia con un indice di 0. È possibile estrarre facilmente gli elementi dall'array, purché si conosca l'indice.
D'altra parte, un elenco collegato è costituito da nodi che puntano ad altri nodi. Ogni nodo conosce solo se stesso e il nodo successivo. Come struttura dati lineare, gli elementi sono disposti in ordine. Potresti pensarlo come un treno: ogni vagone è collegato al vagone successivo e così via. Gli elenchi collegati non sono indicizzati , quindi non puoi accedere direttamente al quinto elemento. Dovresti iniziare dall'inizio, passare al successivo e andare al successivo finché non trovi il quinto elemento. Il primo nodo è chiamato la testa e l'ultimo nodo è chiamato la coda. Esistono vari tipi di elenchi collegati: elenco collegato singolarmente, elenco collegato doppiamente e elenco collegato circolare. Per il bene di questo articolo, mi concentrerò sull'elenco collegato singolarmente.
L'accesso agli elementi in tutto l'array è più semplice, ma ha un costo.
Perché utilizzare elenchi collegati su array?
Forse ti starai chiedendo, ma perché usarlo se posso accedere agli elementi direttamente con gli array? Questo è vero! L'accesso agli elementi in tutto l'array è più semplice, ma ha un costo.
Gli array sono indicizzati , quindi ogni volta che devi rimuovere un elemento dall'inizio o dal centro, tutti i seguenti indici devono essere spostati. Questo vale anche se è necessario inserire un elemento: tutti gli elementi seguenti devono essere reindicizzati. Quando si inseriscono o si rimuovono elementi da un elenco collegato, non è necessario reindicizzare: tutto ciò che interessa è il nodo a cui punta .
Implementazione di un elenco collegato singolarmente
Esistono vari tipi di elenchi collegati: singolarmente, doppiamente e circolari. Gli elenchi collegati singolarmente sono un tipo di elenco collegato in cui ogni nodo ha un valore e un puntatore al nodo successivo (null se è il nodo di coda). Gli elenchi doppiamente concatenati, invece, hanno un ulteriore puntatore al nodo precedente. Gli elenchi collegati circolari sono il punto in cui il nodo della coda punta di nuovo al nodo della testa.
Nota: se sei un principiante visivo, VisuAlgo è un ottimo posto per giocare e vedere la struttura dei dati subire modifiche.
Se vuoi saltare avanti per il codice completo: controlla questa sintesi di GitHub .
Creazione di un nodo
Cominciamo costruendo un nodo da usare. Avrà un valore e un puntatore successivo, che indicherà il suo prossimo vicino.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
Inizieremo costruendo una classe chiamata SinglyLinkedList e forniremo una base per la testa, la coda e la lunghezza dell'elenco.
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
Per aggiungere un nodo alla fine, controlliamo se c'è una testina già dichiarata nell'elenco. In caso contrario, imposta la testa e la coda come nodo appena creato. Se è già presente una proprietà head, impostare la proprietà successiva sulla coda sul nuovo nodo e la proprietà tail come nuovo nodo. Aumenteremo la lunghezza di 1.
push(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++;
return this;
}
Per rimuovere un nodo alla fine, dobbiamo prima controllare se ci sono nodi nell'elenco. Se ci sono nodi, dobbiamo scorrere l'elenco fino a raggiungere la coda. Imposteremo la proprietà successiva del penultimo nodo su null, imposteremo la proprietà tail su quel nodo, diminuiremo la lunghezza di 1 e restituiremo il valore del nodo rimosso.
pop() {
if (!this.head) return undefined;
var current = this.head
var newTail = current
while (current.next) {
newTail = current
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
Per rimuovere il nodo dall'inizio, controlliamo se ci sono nodi nell'elenco. Memorizzeremo la proprietà head corrente in una variabile e imposteremo head in modo che sia il nodo successivo dell'head corrente. Diminuisci la lunghezza di 1 e restituisci il valore del nodo rimosso.
shift() {
if (!this.head) return undefined
var oldHead = this.head;
this.head = oldHead.next;
this.length--
if (this.length===0) {
this.head = null;
this.tail = null;
}
return oldHead
}
Per aggiungere un nodo all'inizio, creiamo prima il nodo e controlliamo se c'è una proprietà head nell'elenco. In tal caso, imposta la proprietà successiva del nodo appena creato sull'intestazione corrente, imposta la testa sul nuovo nodo e aumenta la lunghezza.
unshift(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++
return this
}
Per accedere a un nodo in base alla sua posizione nell'elenco, controlliamo prima se l'indice è un indice valido. Dopo, scorreremo l'elenco, mantenendo una variabile contatore. Una volta che la variabile counter corrisponde all'indice, restituiremo il nodo trovato
get(idx) {
if (idx < 0 || idx >= this.length) return null
var counter = 0;
var current = this.head
while (counter !== idx) {
current = current.next;
counter++;
}
return current;
}
Per modificare un nodo in base alla sua posizione, per prima cosa troviamo il nodo, utilizzando il metodo get e impostiamo il valore sul nuovo valore.
set(idx, val) {
var foundNode = this.get(idx)
if (foundNode) {
foundNode.val = val
return true;
}
return false;
}
Per inserire un nodo, controlliamo prima l'indice. Se è uguale a 0, usiamo il nostro metodo unshift. Se è uguale alla lunghezza, lo inseriamo nell'elenco. Altrimenti, otterremo il nodo before utilizzando il metodo get a uno in meno rispetto all'indice. Essenzialmente, dobbiamo tenere traccia del nodo prima e dopo l'indice selezionato per assicurarci che i nostri puntatori siano diretti verso il nodo corretto.
insert(idx, val) {
if (idx < 0 || idx > this.length) return false;
if (idx === 0) {
this.unshift(val)
return true;
};
if (idx === this.length) {
this.push(val);
return true;
};
var newNode = new Node(val);
var beforeNode = this.get(idx-1);
var afterNode = beforeNode.next;
beforeNode.next = newNode;
newNode.next = afterNode;
this.length++;
return true;
}
Per rimuovere un nodo in base alla posizione, useremo di nuovo il nostro metodo get e utilizzeremo lo stesso principio che abbiamo usato per inserire un nodo. Tenendo traccia del nodo precedente all'indice scelto, possiamo manovrare i nostri puntatori.
remove(idx) {
if (idx < 0 || idx > this.length) return undefined;
if (idx === this.length-1) {
this.pop()
}
if (idx === 0) {
this.shift()
}
var prevNode = this.get(idx-1)
var removeNode = prevNode.next
prevNode.next = removeNode.next
this.length--;
return removeNode;
}
Punti di forza degli elenchi collegati
Il vantaggio dell'utilizzo di un elenco collegato è la possibilità di inserire e rimuovere rapidamente elementi. Poiché gli elenchi collegati non sono indicizzati, l'inserimento di elementi è relativamente semplice e veloce.
L'aggiunta alla fine dell'elenco collegato richiede semplicemente che la vecchia coda punti al nuovo nodo e che la proprietà tail sia impostata sul nuovo nodo. L'aggiunta all'inizio dell'elenco collegato è la stessa premessa, ma il nuovo nodo punta alla vecchia testata e la proprietà head è impostata sul nuovo nodo. Fondamentalmente stesse azioni, quindi l'inserimento è O (1).
Nota: l'inserimento nel mezzo di un elenco collegato, richiede la ricerca per trovare il proprio nodo (O (N)) e quindi l'inserimento del nodo (O (1)).
Rimuovere un nodo dall'elenco collegato può essere facile ... ma anche no. Dipende da dove. Rimuovere un nodo dall'inizio della lista è semplice: il secondo nodo diventa il nuovo head e impostiamo il puntatore successivo del vecchio head su null. La rimozione dalla fine è più complicata perché ciò richiede di esaminare l'intero elenco e fermarsi al penultimo nodo. Caso peggiore O (N) e caso migliore O (1).
Debolezze degli elenchi collegati
I punti deboli di un elenco collegato sono causati dalla sua mancanza di reindicizzazione. Poiché non è possibile accedere direttamente agli elementi, rende più difficile la ricerca e l'accesso agli elementi.
La ricerca e l'accesso a un nodo in un elenco collegato richiede di iniziare dall'inizio dell'elenco e seguire la traccia dei breadcrumb lungo l'elenco. Se stiamo cercando il nodo alla fine della lista, dovremo passare attraverso l'intera lista collegata, rendendo effettivamente la complessità temporale O (N). Man mano che l'elenco cresce, il numero di operazioni aumenta. Rispetto a un array con accesso casuale, richiede tempo costante per accedere a un elemento.
Questo è tutto!
Gli elenchi collegati sono ottime alternative agli array quando l'inserimento e l'eliminazione all'inizio sono azioni chiave. Gli array sono indicizzati, mentre gli elenchi collegati non lo sono. Gli elenchi collegati sono anche la struttura dati di base da cui sono costruiti stack e code, di cui parlerò in un articolo successivo. Se sei arrivato fin qui, complimenti a te e spero che tu abbia imparato un po 'di pepita durante il tuo viaggio di programmazione!
