Come implementare una struttura dei dati dell'elenco collegato in JavaScript?

JavaScript è un linguaggio di programmazione web utilizzato per rendere le nostre pagine Web e le applicazioni Web dinamiche e interattive dando loro la possibilità di pensare e agire. Come qualsiasi altro linguaggio di programmazione, JavaScript ci offre array che sono una raccolta di diversi elementi memorizzati in una singola variabile. La limitazione di un array è che è memorizzato consecutivamente in una memoria particolare nel nostro sistema, quindi per risolvere questo problema utilizziamo un elenco collegato.

Lista collegata

Gli elenchi collegati sono come array, tranne che in un elenco collegato gli elementi non vengono salvati in una posizione o indice di memoria specifica e ogni elemento è un oggetto indipendente separato che è collegato all'elemento successivo avendo un puntatore o un collegamento a quell'elemento.

Ogni elenco collegato contiene una proprietà testa (primo nodo), lunghezza (dimensione dell'elenco collegato) e una proprietà di coda (ultimo nodo) e ogni elemento in un elenco collegato viene chiamato nodo e ogni nodo ha un valore memorizzato in esso e Il collegamento al nodo successivo. Se il nodo corrente è la coda, il collegamento sarà nullo che non punta a nessun altro nodo. L'elenco collegato non contiene indici a differenza degli array che hanno indici E.g 0,1,2 ... e così via.

Gli elenchi collegati in JavaScript possono essere dimostrati come segue:

// Lista collegata
const LinkedList =
// Ogni nodo ha un valore e un puntatore
// Il primo puntatore è l'intestazione
Testa:
Valore: 6
Prossimo:
Valore: 10
Prossimo:
Valore: 12
Prossimo:
Valore: 3
Avanti: NULL





;

Il vantaggio dell'elenco collegato è che gli elementi (nodi) vengono facilmente aggiunti e rimossi dall'elenco collegato senza regolare l'intero elenco collegato. Lo svantaggio di un elenco collegato è che richiede più memoria per l'archiviazione poiché ora abbiamo un puntatore aggiuntivo che stiamo memorizzando insieme al valore dell'elemento.

Gli elenchi collegati sono di tre tipi descritti di seguito:

• L'elenco singolarmente collegato ha un solo puntatore che punta al nodo accanto ad esso.
• Il doppiamente collegato si basa su due puntatori in cui il primo indica il nodo dietro di esso e il secondo indica il nodo accanto ad esso.
• L'elenco circolare collegato la cui coda contiene un puntatore alla testa e quindi forma un ciclo.

Implementazione dell'elenco collegato

Creiamo innanzitutto un nodo che abbia due proprietà un valore e un puntatore per il quale creeremo una classe con il nome di ListNode Questo ha queste due proprietà:

Class ListNode
costruttore (valore)
Questo.valore = valore
Questo.Next = null

Ora che sappiamo come creare un nodo, consenterci di creare un elenco collegato in cui il valore predefinito della testa sarà nullo:

class LinkedList
costruttore (head = null)
Questo.testa = testa

Inizializziamo ora l'elenco collegato con due nodi e aggiungiamo un puntatore dalla testa o dal nodo 1 al secondo nodo:

var node1 = new ListNode (3);
var node2 = new ListNode (4);
nodo1.Next = node2;

Il prossimo passo è inizializzare l'elenco collegato con Node1 nel modo seguente:

var list = new LinkedList (node1);

L'intero codice è riportato di seguito con la registrazione della console il valore node2:

// Creazione di nodo
Class ListNode
costruttore (valore)
// Valore di inizializzazione del costruttore e il puntatore successivo
Questo.valore = valore
Questo.Next = null


class LinkedList
// costruttore di elenchi collegati
costruttore (head = null)
Questo.testa = testa


// Inizializzazione dei nodi creati
var node1 = new ListNode (3);
var node2 = new ListNode (4);
nodo1.Next = node2;
// Inizializzazione dell'elenco collegato
var list = new LinkedList (node1);
// che mostra l'output del secondo nodo
console.registro (elenco.Testa.Prossimo.valore) // 4

Metodi di elenco collegati

Ora che abbiamo finito con l'implementazione dell'elenco collegato, riproduciamo o manipola l'elenco collegato implementando più metodi per utilizzare gli elenchi collegati (metodi helper):

Il primo metodo Helper che definiremo è il misurare() Metodo della classe Lista collegata che restituirà la lunghezza dell'elenco collegato:

size = () =>
let count = 0;
lascia nodo = questo.Testa;
// loop per iterare l'elenco collegato
while (nodo)
conta ++;
nodo = nodo.Prossimo

Conteggio di ritorno;

In questo codice prima, stiamo dichiarando una variabile fittizia contare memorizzando 0 in esso e poi conserva il puntatore della testa nel nodo variabile. Quindi abbiamo dichiarato un ciclo che iterirà nell'elenco collegato e increderà il contare variabile.

Il prossimo metodo Helper sarà il getFirst () Metodo in cui verrà restituito il puntatore del capo:

getFirst = () =>
Restituisci questo.Testa.valore;

Possiamo anche ottenere l'ultimo nodo dell'elenco collegato nel modo seguente:

getLast = () =>
lascia che lastnode = questo.Testa;
if (lastnode)
mentre (LastNode.Prossimo)
LastNode = LastNode.Prossimo


Restituisci LastNode.valore

Di seguito è ora riportato l'intero codice che mostra l'output del valore del secondo nodo, la dimensione dell'elenco collegato, il valore del primo nodo e il valore dell'ultimo nodo nello stesso ordine:

// Creazione di nodo
Class ListNode
costruttore (valore)
Questo.valore = valore
Questo.Next = null


// Creazione di un elenco collegato
class LinkedList
costruttore (head = null)
Questo.testa = testa

size = () =>
let count = 0;
lascia nodo = questo.Testa;
// loop per iterare l'elenco collegato
while (nodo)
conta ++;
nodo = nodo.Prossimo

Conteggio di ritorno;

getFirst = () =>
Restituisci questo.Testa.valore;

getLast = () =>
lascia che lastnode = questo.Testa;
if (lastnode)
mentre (LastNode.Prossimo)
LastNode = LastNode.Prossimo


Restituisci LastNode.valore


// Inizializzazione dei nodi creati
var node1 = new ListNode (3);
var node2 = new ListNode (4);
nodo1.Next = node2;
// Inizializzazione dell'elenco collegato
var list = new LinkedList (node1);
// che mostra l'output del secondo nodo
console.log ("Valore del secondo nodo:", elenco.Testa.Prossimo.valore) // 4
// che mostra le dimensioni dell'elenco collegato
console.Log ("Dimensione dell'elenco collegato:", Elenco.misurare());
// che mostra il valore del primo nodo
console.log ("Valore del primo nodo:", elenco.getFirst ());
// che mostra il valore dell'ultimo nodo
console.Log ("Valore dell'ultimo nodo:", Elenco.getLast ());

Conclusione

Dopo gli array, un elenco collegato è la seconda struttura di dati più utilizzata in qualsiasi linguaggio di programmazione. Un elenco collegato è come un array che memorizza una raccolta di diversi elementi con la differenza è che ogni elemento (nodo) di un elenco collegato è un oggetto contenente un valore dell'elemento e un puntatore che punta al nodo successivo, quindi collegando ogni elemento e La seconda differenza è che gli elementi non vengono salvati in una posizione di memoria specifica in un elenco collegato.

In questo post, abbiamo visto quali sono gli elenchi collegati, i vantaggi e gli svantaggi degli elenchi collegati, i tipi di elenchi collegati e come implementare la struttura dei dati degli elenchi collegati in JavaScript.