Puteți explica ce reprezintă o listă legată și cum funcționează?

O listă legată este o structură de date formată din noduri, unde fiecare nod conține date și o referință la următorul nod din listă. Spre deosebire de array-uri, listele legate nu necesită un bloc de memorie contiguu și permit inserarea și ștergerea eficientă a elementelor.

Principalele tipuri de liste legate:

• Listă simplu legată: fiecare nod conține doar o referință la următorul nod.
• Listă dublu legată: fiecare nod conține referințe atât la următorul, cât și la nodul anterior.

Exemplu de listă simplu legată în JavaScript (Node.js):

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

  add(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }
}

Listele legate sunt utile atunci când este necesar să se schimbe dimensiunea structurii în mod dinamic și să se facă inserții/ștergeri frecvente de elemente.