Dacă învățați structuri de date, o listă legată este o structură de date pe care ar trebui să o cunoașteți. Dacă nu înțelegeți cu adevărat sau cum este implementat în JavaScript, acest articol este aici pentru a vă ajuta.

În acest articol, vom discuta ce este o listă legată, cum este diferită de o matrice și cum să o implementăm în JavaScript. Să începem.

Ce este o listă legată?

O listă legată este o structură de date liniară similară cu o matrice. Cu toate acestea, spre deosebire de tablouri, elementele nu sunt stocate într-o anumită locație sau index de memorie. Mai degrabă fiecare element este un obiect separat care conține un indicator sau un link către următorul obiect din acea listă.

Fiecare element (denumit în mod obișnuit noduri) conține două elemente: datele stocate și un link către nodul următor. Datele pot fi orice tip de date valid. Puteți vedea acest lucru ilustrat în diagrama de mai jos.

Imagine a unei liste conectate

Punctul de intrare către o listă legată se numește cap. Capul este o referință la primul nod din lista legată. Ultimul nod din listă indică nul. Dacă o listă este goală, capul este o referință nulă.

ad-banner

În JavaScript, o listă legată arată astfel:

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

Un avantaj al listelor conectate

  • Nodurile pot fi ușor eliminate sau adăugate dintr-o listă legată fără a reorganiza întreaga structură de date. Acesta este un avantaj pe care îl are față de tablouri.

Dezavantaje ale listelor legate

  • Operațiunile de căutare sunt lente în listele legate. Spre deosebire de matrice, accesul aleatoriu al elementelor de date nu este permis. Nodurile sunt accesate secvențial începând de la primul nod.
  • Folosește mai multă memorie decât matrice din cauza stocării pointerelor.

Tipuri de liste legate

Există trei tipuri de liste legate:

  • Liste conectate individual: Fiecare nod conține doar un singur indicator către următorul nod. Despre asta am vorbit până acum.
  • Liste dublu legate: Fiecare nod conține doi indicatori, un pointer către nodul următor și un pointer către nodul anterior.
  • Liste circulare legate: Listele circulare legate sunt o variație a unei liste legate în care ultimul nod indică primul nod sau orice alt nod dinaintea acestuia, formând astfel o buclă.

Implementarea unui nod de listă în JavaScript

După cum sa menționat mai devreme, un nod de listă conține două elemente: datele și indicatorul către următorul nod. Putem implementa un nod de listă în JavaScript după cum urmează:

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

Implementarea unei liste conectate în JavaScript

Codul de mai jos prezintă implementarea unei clase de liste legate cu un constructor. Observați că dacă nodul de cap nu este trecut, capul este inițializat la nul.

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

Punând totul împreună

Să creăm o listă legată cu clasa pe care tocmai am creat-o. Mai întâi, creăm două noduri de listă, node1 și node2 și un indicator de la nodul 1 la nodul 2.

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

Apoi, vom crea o listă legată cu node1.

let list = new LinkedList(node1)

Să încercăm să accesăm nodurile din lista pe care tocmai am creat-o.

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

Unele metode LinkedList

În continuare, vom implementa patru metode de ajutor pentru lista legată. Sunt:

  1. mărimea()
  2. clar()
  3. getLast ()
  4. getFirst ()

1. dimensiune ()

Această metodă returnează numărul de noduri prezente în lista legată.

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

2. clear ()

Această metodă goleste lista.

clear() {
    this.head = null;
}

3. getLast ()

Această metodă returnează ultimul nod al listei conectate.

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

4. getFirst ()

Această metodă returnează primul nod al listei conectate.

getFirst() {
    return this.head;
}

rezumat

În acest articol, am discutat ce este o listă legată și cum poate fi implementată în JavaScript. De asemenea, am discutat despre diferitele tipuri de liste legate, precum și despre avantajele și dezavantajele lor generale.

Sper că ți-a plăcut să o citești.

Doriți să primiți o notificare când public un articol nou? Click aici.