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

O listă legată este o structură de date formată din elemente (nodi), fiecare conținând date și o referință (pointer) către elementul următor din listă. Spre deosebire de un array, elementele listei legate nu trebuie să fie stocate contiguu în memorie.

Exemplu de listă legată simplă în Swift:

class Node {
    var value: Int
    var next: Node?

    init(value: Int) {
        self.value = value
    }
}

// Crearea listei: 1 -> 2 -> 3
let first = Node(value: 1)
let second = Node(value: 2)
let third = Node(value: 3)
first.next = second
second.next = third

Această listă permite inserarea și ștergerea elementelor eficient, fără a deplasa celelalte, dar accesul la elemente după index necesită parcurgerea secvențială.