Qual a vantagem das listas encadeadas (linked lists) sobre os arrays?
Sendo bem direto: uso de memória.
Os arrays armazenam seus elementos em locais contínuos de memória. Por exemplo, se eu tenho um array com quatro elementos:
arr = [1, 2, 3, 4]
eu precisaria de 4 espaços contínuos de memória, ou seja, quatro espaços um do lado do outro para armazenar o array. Se esse array passasse a ter ter 10 elementos, eu precisaria procurar um lugar na memória que tivesse pelo menos 10 espaços disponíveis.
Por outro lado, as listas encadeadas (linked lists) funcionam de forma totalmente diferente. Se no array era preciso espaços contínuos de memória, na lista encadeada eu posso ter os elementos em qualquer lugar da memória.
Mas como eu relaciono esses elementos, se eles estão "perdidos" na memória, sem relacão nenhuma uns com os outros?
Cada nó da lista (ou seja, cada elemento da lista) deve possuir pelo menos duas propriedades obrigatórias: um valor e um ponteiro.
Digamos que eu tenha dois valores na lista: 2 e 5: o primeiro elemento da lista é o 2, portanto a sua estrutura seria algo parecido com Node(value: 2, next: 5). O 5 é o último elemento da lista, portanto não "aponta" para nenhum outro elemento, tendo seu ponteiro como nulo: Node(value: 5, next: None).
Entretanto, se a lista encadeada ganha em uso de memória, ela pode perder em performance, já que sempre que você quiser acessar um elemento da lista precisará percorrê-la por inteiro, diferentemento do array, que é possível acessar seus elementos através de índices.
Obs: Estou estudando sobre o assunto agora, então caso eu tenha deixado de explicar algo de forma correta, por favor, me corrija nos comentários!