Ce este o listă legată (LinkedList)?

O listă înlănțuită este o structură de date liniară în care elementele nu sunt stocate în celule de memorie adiacente. În schimb, fiecare element, numit nod, conține date și o referință (sau pointer) către următorul nod din secvență.

Există diferite tipuri de liste înlănțuite:

• Listă simplu înlănțuită: Fiecare nod conține doar o referință către următorul nod.
• Listă dublu înlănțuită: Fiecare nod conține referințe atât către următorul, cât și către nodul anterior.
• Listă circulară înlănțuită: Ultimul nod face referire la primul, formând un ciclu.

Operații principale pe o listă înlănțuită:

• Inserție: Adăugarea unui nou nod în listă.
• Ștergere: Eliminarea unui nod din listă.
• Căutare: Căutarea unui nod după valoare.
• Parcurgere: Acces secvențial la toți nodurile listei.

Avantaje:

• Flexibilitate în inserarea și ștergerea elementelor în orice poziție.
• Gestionare eficientă a memoriei, deoarece elementele nu necesită blocuri continue.

Dezavantaje:

• Acces lent la elemente aleatorii (se necesită parcurgere secvențială).
• Este nevoie de memorie suplimentară pentru stocarea referințelor.

Exemplu de structură a unui nod într-o listă simplu înlănțuită:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}