Pode explicar o que é uma lista ligada e como ela funciona?

Uma lista ligada é uma estrutura de dados composta por elementos (nós), cada um contendo dados e uma referência (ponteiro) para o próximo elemento da lista. Ao contrário de um array, os elementos de uma lista ligada não precisam estar armazenados de forma contígua na memória.

Exemplo de uma lista ligada simples em Swift:

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

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

// Criando a lista: 1 -> 2 -> 3
let first = Node(value: 1)
let second = Node(value: 2)
let third = Node(value: 3)
first.next = second
second.next = third

Essa lista permite inserir e remover elementos de forma eficiente sem deslocar os demais, mas o acesso aos elementos por índice requer percorrê-la sequencialmente.