Share
Cosa starai creandoDue delle strutture dati più comunemente insegnate nell'informatica sono la lista collegata separatamente e la lista doppiamente collegata.
Quando mi hanno insegnato queste strutture dati, ho chiesto ai miei colleghi di fare delle analogie per concettualizzarle. Quello che ho sentito sono stati diversi esempi, come un elenco di generi alimentari e un treno. Queste analogie, come appresi, non erano accurate. Una lista della spesa era più simile a una coda; un treno era più simile a un array.
Con il passare del tempo, alla fine scoprii un'analogia che descriveva accuratamente una lista collegata singolarmente e una lista doppiamente collegata: una caccia al tesoro. Se sei curioso della relazione tra una caccia al tesoro e una lista collegata, leggi sotto per la risposta!
Nell'informatica, una lista collegata singolarmente è una struttura di dati che contiene una sequenza di nodi collegati. Ogni nodo, a sua volta, contiene dati e un puntatore, che può puntare a un altro nodo.
I nodi di una lista collegata singolarmente sono molto simili ai passaggi di una caccia al tesoro. Ogni passaggio contiene un messaggio (ad esempio "Hai raggiunto la Francia") e i puntatori al passaggio successivo (ad esempio "Visita queste coordinate di latitudine e longitudine"). Quando iniziamo a sequenziare questi singoli passaggi per formare una sequenza di passaggi, stiamo creando una caccia al tesoro.
Ora che abbiamo un modello concettuale di una lista collegata singolarmente, esploriamo le operazioni di una lista collegata singolarmente.
Poiché un elenco collegato singolarmente contiene nodi, che possono essere un costruttore separato da un elenco collegato singolarmente, illustriamo le operazioni di entrambi i costruttori: Nodo e SinglyList.
Accentsconagua
dati memorizza un valore.Il prossimo punta al nodo successivo nell'elenco._lunghezza recupera il numero di nodi in una lista.capo assegna un nodo come capo di una lista.aggiungere valore) aggiunge un nodo ad una lista.searchNodeAt (posizione) cerca un nodo in posizione n nella nostra lista.rimuovere (posizione) rimuove un nodo da una lista.Per la nostra implementazione, prima definiremo un costruttore chiamato Nodo e poi un costruttore chiamato SinglyList.
Ogni istanza di Nodo ha bisogno della capacità di memorizzare i dati e la capacità di puntare a un altro nodo. Per aggiungere questa funzionalità, creeremo due proprietà: dati e Il prossimo, rispettivamente.
function Node (data) this.data = data; this.next = null;
Successivamente, dobbiamo definire SinglyList:
function SinglyList () this._length = 0; this.head = null;
Ogni istanza di SinglyList avrà due proprietà: _lunghezza e capo. Il primo è assegnato il numero di nodi in una lista; il secondo punta al capo della lista, il nodo in testa alla lista. Dal momento che ogni nuova istanza di SinglyList non contiene un nodo, il valore predefinito di capo è nullo e il valore predefinito di _lunghezza è 0.
Dobbiamo definire metodi che possono aggiungere, cercare e rimuovere un nodo da un elenco. Iniziamo con l'aggiunta di un nodo.
1 di 3: aggiungere valore)
Fantastico, implementiamo ora la funzionalità per aggiungere nodi a un elenco.
SinglyList.prototype.add = function (value) var node = new Node (valore), currentNode = this.head; // 1 ° caso d'uso: una lista vuota se (! CurrentNode) this.head = node; this._length ++; nodo di ritorno; // 2 ° caso d'uso: una lista non vuota mentre (currentNode.next) currentNode = currentNode.next; currentNode.next = node; this._length ++; nodo di ritorno; ;
L'aggiunta di un nodo alla nostra lista comporta molti passaggi. Cominciamo dall'inizio del nostro metodo. Usiamo l'argomento di aggiungere valore) per creare una nuova istanza di a Nodo, che è assegnato a una variabile chiamata nodo. Dichiariamo anche una variabile chiamata nodoCorrente e inizializzarlo al _capo della nostra lista. Se non ci sono nodi nell'elenco, allora il valore di capo è nullo.
Dopo questo punto nel nostro codice, gestiamo due casi d'uso.
Il primo caso d'uso considera l'aggiunta di un nodo a una lista vuota. Se capo non punta a un nodo, quindi assegna nodo come capo della nostra lista, incrementa la lunghezza della nostra lista di uno, e ritorna nodo.
Il secondo caso d'uso considera l'aggiunta di un nodo a una lista non vuota. Entriamo nel mentre loop, e durante ogni iterazione, valutiamo se currentNode.next punta a un altro nodo. (Durante la prima iterazione, nodoCorrente indica sempre la testa di una lista.)
Se la risposta è no, assegniamo nodo a currentNode.next e ritorno nodo.
Se la risposta è sì, entriamo nel corpo di mentre ciclo continuo. All'interno del corpo, ci riassegniamo nodoCorrente a currentNode.next. Questo processo è ripetuto fino a currentNode.next non punta più su un altro nodo. In altre parole, nodoCorrente punta all'ultimo nodo della nostra lista.
Il mentre loop break. Alla fine, assegniamo nodo a currentNode.next, noi incrementiamo _lunghezza per uno, e poi torniamo nodo.
2 di 3: searchNodeAt (posizione)
Ora possiamo aggiungere nodi alla nostra lista, ma non possiamo cercare nodi in posizioni specifiche nella nostra lista. Aggiungiamo questa funzionalità e creiamo un metodo chiamato searchNodeAt (posizione), che accetta un argomento chiamato posizione. Si presume che l'argomento sia un numero intero che indica un nodo in posizione n nella nostra lista.
SinglyList.prototype.searchNodeAt = function (position) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: nodo inesistente in questo elenco.'; // 1 ° caso d'uso: una posizione non valida se (lunghezza === 0 || posizione < 1 || position > length) throw new Error (message.failure); // 2 ° caso d'uso: una posizione valida mentre (conteggio < position) currentNode = currentNode.next; count++; return currentNode; ;
Il Se asserzioni per il primo caso d'uso: una posizione non valida è passata come argomento.
Se l'indice è passato a searchNodeAt (posizione) è valido, quindi raggiungiamo il secondo caso d'uso: il mentre ciclo continuo. Durante ogni iterazione del mentre ciclo continuo, nodoCorrente-che per prima cosa indica capo-viene riassegnato al nodo successivo nell'elenco. Questa iterazione continua fino a quando il conteggio è uguale alla posizione.
Quando il ciclo finalmente si rompe, nodoCorrente viene restituito.
3 di 3: rimuovere (posizione)
Il metodo finale che creeremo è chiamato rimuovere (posizione).
SinglyList.prototype.remove = function (position) var currentNode = this.head, length = this._length, count = 0, message = failure: 'Failure: nodo inesistente in questo elenco.', BeforeNodeToDelete = null , nodeToDelete = null, deletedNode = null; // 1 ° caso d'uso: una posizione non valida se (posizione < 0 || position > length) throw new Error (message.failure); // 2 ° caso d'uso: il primo nodo viene rimosso se (position === 1) this.head = currentNode.next; deletedNode = currentNode; currentNode = null; this._length--; return deletedNode; // 3rd use-case: qualsiasi altro nodo viene rimosso mentre (count < position) beforeNodeToDelete = currentNode; nodeToDelete = currentNode.next; count++; beforeNodeToDelete.next = nodeToDelete.next; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return deletedNode; ;
La nostra implementazione di rimuovere (posizione) comporta tre casi d'uso:
capo di una lista) è passato come argomento.Il primo e il secondo caso d'uso sono i più semplici da gestire. Per quanto riguarda il primo scenario, se la lista è vuota o viene passata una posizione inesistente, viene generato un errore.
Il secondo caso d'uso gestisce la rimozione del primo nodo nell'elenco, che è anche capo. Se questo è il caso, allora si verifica la seguente logica:
capo è riassegnato a currentNode.next.deletedNode punta a nodoCorrente. nodoCorrente è riassegnato a nullo. _lunghezza della nostra lista per uno.deletedNode viene restituito. Il terzo scenario è il più difficile da capire. La complessità deriva dalla necessità di tracciare due nodi durante ogni iterazione di a mentre ciclo continuo. Durante ogni iterazione del nostro ciclo, tracciamo sia il nodo che il nodo da eliminare e il nodo da cancellare. Quando il nostro loop raggiunge infine il nodo nella posizione che vogliamo rimuovere, il ciclo termina.
A questo punto, manteniamo i riferimenti a tre nodi: beforeNodeToDelete, nodeToDelete, e deletedNode. Prima dell'eliminazione nodeToDelete, dobbiamo assegnare il suo valore di Il prossimo al prossimo valore di beforeNodeToDelete. Se lo scopo di questo passaggio non è chiaro, ricordati che abbiamo un elenco di nodi collegati; la semplice rimozione di un nodo interrompe il collegamento dal primo nodo dell'elenco all'ultimo nodo della lista.
Successivamente, assegniamo deletedNode a nodeToDelete. Quindi impostiamo il valore di nodeToDelete a nullo, decrementa la lunghezza della lista di uno, e ritorna deletedNode.
L'implementazione completa della nostra lista è qui:
function Node (data) this.data = data; this.next = null; function SinglyList () this._length = 0; this.head = null; SinglyList.prototype.add = function (value) var node = new Node (valore), currentNode = this.head; // 1 ° caso d'uso: una lista vuota se (! CurrentNode) this.head = node; this._length ++; nodo di ritorno; // 2 ° caso d'uso: una lista non vuota mentre (currentNode.next) currentNode = currentNode.next; currentNode.next = node; this._length ++; nodo di ritorno; ; SinglyList.prototype.searchNodeAt = function (position) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: nodo inesistente in questo elenco.'; // 1 ° caso d'uso: una posizione non valida se (lunghezza === 0 || posizione < 1 || position > length) throw new Error (message.failure); // 2 ° caso d'uso: una posizione valida mentre (conteggio < position) currentNode = currentNode.next; count++; return currentNode; ; SinglyList.prototype.remove = function(position) var currentNode = this.head, length = this._length, count = 0, message = failure: 'Failure: non-existent node in this list.', beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (position < 0 || position > length) throw new Error (message.failure); // 2 ° caso d'uso: il primo nodo viene rimosso se (position === 1) this.head = currentNode.next; deletedNode = currentNode; currentNode = null; this._length--; return deletedNode; // 3rd use-case: qualsiasi altro nodo viene rimosso mentre (count < position) beforeNodeToDelete = currentNode; nodeToDelete = currentNode.next; count++; beforeNodeToDelete.next = nodeToDelete.next; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return deletedNode; ;
Impressionante, la nostra implementazione di un elenco collegato singolarmente è completa. Ora possiamo usare una struttura dati che aggiunge, rimuove e cerca nodi in una lista che occupa spazio non contiguo in memoria.
Tuttavia, in questo momento, tutte le nostre operazioni iniziano dall'inizio di un elenco e vengono eseguite fino alla fine di un elenco. In altre parole, sono unidirezionali.
Ci possono essere casi in cui vogliamo che le nostre operazioni siano bidirezionali. Se hai considerato questo caso d'uso, hai appena descritto una lista doppiamente collegata.
Una lista doppiamente collegata prende tutte le funzionalità di una lista collegata singolarmente e la estende per il movimento bidirezionale in una lista. Possiamo attraversare, in altre parole, una lista collegata dal primo nodo della lista all'ultimo nodo della lista; e possiamo passare dall'ultimo nodo della lista al primo nodo della lista.
In questa sezione, manterremo la nostra attenzione principalmente sulle differenze tra una lista doppiamente collegata e una lista collegata singolarmente.
La nostra lista includerà due costruttori: Nodo e DoublyList. Lasciateci delineare le loro operazioni.
dati memorizza un valore.Il prossimo punta al nodo successivo nell'elenco.precedente punta al nodo precedente nell'elenco._lunghezza recupera il numero di nodi in una lista.capo assegna un nodo come capo di una lista.coda assegna un nodo come coda di una lista.aggiungere valore) aggiunge un nodo ad una lista.searchNodeAt (posizione) cerca un nodo in posizione n nella nostra lista.rimuovere (posizione) rimuove un nodo da una lista.Lascia scrivere un codice!
Per la nostra implementazione, creeremo un costruttore chiamato Nodo:
function Node (value) this.data = value; this.previous = null; this.next = null;
Per creare il movimento bidirezionale di una lista doppiamente collegata, abbiamo bisogno di proprietà che puntino in entrambe le direzioni di una lista. Queste proprietà sono state nominate precedente e Il prossimo.
Successivamente, dobbiamo implementare a DoublyList e aggiungere tre proprietà: _lunghezza, capo, e coda. A differenza di un elenco collegato singolarmente, un elenco con collegamento doppio ha un riferimento sia all'inizio di un elenco che alla fine di un elenco. Poiché ogni istanza di a DoublyList viene istanziato senza nodi, i valori predefiniti di capo e coda sono impostati su nullo.
function DoublyList () this._length = 0; this.head = null; this.tail = null;
Ora esploreremo i seguenti metodi: aggiungere valore), rimuovere (posizione), e searchNodeAt (posizione). Tutti questi metodi sono stati usati per una lista collegata singolarmente; tuttavia, devono essere riscritti per il movimento bidirezionale.
1 di 3: aggiungere valore)
DoublyList.prototype.add = function (value) var node = new Node (value); if (this._length) this.tail.next = node; node.previous = this.tail; this.tail = node; else this.head = node; this.tail = node; this._length ++; nodo di ritorno; ;
In questo metodo, abbiamo due scenari. Innanzitutto, se una lista è vuota, assegnala alla sua capo e coda il nodo che viene aggiunto. In secondo luogo, se l'elenco contiene nodi, trova la coda dell'elenco e assegna a tail.next il nodo che viene aggiunto; allo stesso modo, dobbiamo configurare la nuova coda per il movimento bidirezionale. Abbiamo bisogno di impostare, in altre parole, tail.previous alla coda originale.
2 di 3: searchNodeAt (posizione)
L'implementazione di searchNodeAt (posizione) è identico a un elenco collegato singolarmente. Se hai dimenticato come implementarlo, l'ho incluso di seguito:
DoublyList.prototype.searchNodeAt = function (position) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: nodo inesistente in questo elenco.'; // 1 ° caso d'uso: una posizione non valida se (lunghezza === 0 || posizione < 1 || position > length) throw new Error (message.failure); // 2 ° caso d'uso: una posizione valida mentre (conteggio < position) currentNode = currentNode.next; count++; return currentNode; ;
3 di 3: rimuovere (posizione)
Questo metodo sarà il più difficile da capire. Visualizzerò il codice e poi lo spiegherò.
DoublyList.prototype.remove = function (position) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: nodo inesistente in questo elenco.', BeforeNodeToDelete = null , nodeToDelete = null, deletedNode = null; // 1 ° caso d'uso: una posizione non valida se (lunghezza === 0 || posizione < 1 || position > length) throw new Error (message.failure); // 2 ° caso d'uso: il primo nodo viene rimosso se (position === 1) this.head = currentNode.next; // 2 ° caso d'uso: esiste un secondo nodo se (! This.head) this.head.previous = null; // 2 ° caso d'uso: non esiste un secondo nodo else this.tail = null; // 3rd use-case: l'ultimo nodo viene rimosso else if (position === this._length) this.tail = this.tail.previous; this.tail.next = null; // 4 ° caso d'uso: un nodo centrale viene rimosso else while (count < position) currentNode = currentNode.next; count++; beforeNodeToDelete = currentNode.previous; nodeToDelete = currentNode; afterNodeToDelete = currentNode.next; beforeNodeToDelete.next = afterNodeToDelete; afterNodeToDelete.previous = beforeNodeToDelete; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return message.success; ;
rimuovere (posizione) gestisce quattro casi d'uso:
rimuovere (posizione) è inesistente In questo caso, abbiamo generato un errore. rimuovere (posizione) è il primo nodo (capo) di una lista. Se questo è il caso, assegneremo deletedNode a capo e quindi riassegnare capo al nodo successivo nell'elenco. In questo momento, dobbiamo considerare se la nostra lista ha più di un nodo. Se la risposta è no, capo sarà assegnato a nullo e noi entreremo nel Se parte del nostro se altro dichiarazione. Nel corpo di Se, dobbiamo anche impostare coda a nullo-in altre parole, torniamo allo stato originale di una lista vuota doppiamente collegata. Se stiamo rimuovendo il primo nodo in una lista e abbiamo più di un nodo nella nostra lista, entriamo nel altro sezione del nostro se altro dichiarazione. In questo caso, dobbiamo impostare correttamente il precedente proprietà di capo a nullo-non ci sono nodi prima del capo di una lista. rimuovere (posizione) è la coda di una lista. Primo, deletedNode è assegnato a coda. Secondo, coda viene riassegnato al nodo precedente alla coda. Terzo, la nuova coda non ha alcun nodo dopo di essa e ha bisogno del suo valore Il prossimo essere impostato su nullo. mentre loop una volta nodoCorrente sta puntando al nodo nella posizione che viene passato come argomento a rimuovere (posizione). In questo momento, riassegniamo il valore di beforeNodeToDelete.next al nodo dopo nodeToDelete e, al contrario, riassegniamo il valore di afterNodeToDelete.previous al nodo prima nodeToDelete. In altre parole, rimuoviamo i puntatori al nodo rimosso e li riassegniamo ai nodi corretti. Successivamente, assegniamo deletedNode a nodeToDelete. Alla fine, assegniamo nodeToDelete a nullo. Infine, decrementiamo la lunghezza della nostra lista e ritorniamo deletedNode.
Ecco l'intera implementazione:
function Node (value) this.data = value; this.previous = null; this.next = null; function DoublyList () this._length = 0; this.head = null; this.tail = null; DoublyList.prototype.add = function (value) var node = new Node (value); if (this._length) this.tail.next = node; node.previous = this.tail; this.tail = node; else this.head = node; this.tail = node; this._length ++; nodo di ritorno; ; DoublyList.prototype.searchNodeAt = function (position) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: nodo inesistente in questo elenco.'; // 1 ° caso d'uso: una posizione non valida se (lunghezza === 0 || posizione < 1 || position > length) throw new Error (message.failure); // 2 ° caso d'uso: una posizione valida mentre (conteggio < position) currentNode = currentNode.next; count++; return currentNode; ; DoublyList.prototype.remove = function(position) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: non-existent node in this list.', beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) throw new Error (message.failure); // 2 ° caso d'uso: il primo nodo viene rimosso se (position === 1) this.head = currentNode.next; // 2 ° caso d'uso: esiste un secondo nodo se (! This.head) this.head.previous = null; // 2 ° caso d'uso: non esiste un secondo nodo else this.tail = null; // 3rd use-case: l'ultimo nodo viene rimosso else if (position === this._length) this.tail = this.tail.previous; this.tail.next = null; // 4 ° caso d'uso: un nodo centrale viene rimosso else while (count < position) currentNode = currentNode.next; count++; beforeNodeToDelete = currentNode.previous; nodeToDelete = currentNode; afterNodeToDelete = currentNode.next; beforeNodeToDelete.next = afterNodeToDelete; afterNodeToDelete.previous = beforeNodeToDelete; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return message.success; ;
Abbiamo coperto molte informazioni in questo articolo. Se qualcuno di esso appare confuso, rileggerlo e sperimentare il codice. Quando alla fine ha senso per te, si senta orgoglioso. Hai appena scoperto i misteri di una lista collegata singolarmente e una lista doppiamente collegata. Puoi aggiungere queste strutture dati alla tua cintura degli strumenti di codifica!
