O que será isto das listas? Uma lista é uma estrutura de dados sequencial que resolve o típico problema dos arrays. E qual é o problema do arrays (vectores) poderá pensar o leitor? Se pensarmos mais concretamente na linguagem C, o que precisamos para definir um array? O tipo de dados e o número de elementos que iremos ter! E no início da implementação de um programa, definir o número de elementos que o array poderá ter pode ser problemático. Ou porque não sabemos em definitivo quantos elementos vai ter o array ou porque depois poderemos querer adicionar ou remover elementos.
Mantendo sempre o nosso pensamento na linguagem C, temos uma forma de aumentar ou diminuir o número de elementos de um array usando a função realloc disponível na biblioteca stdlib.h, mas o que esta função faz na prática é realocar todos os elementos novamente, ou seja, se pensarmos no caso em que só queremos adicionar um elemento, e se o nosso array tiver vários elementos, realocar toda a memória novamente é um desperdício de recursos computacionais, recursos estes que poderíamos estar a utilizar noutra operação do nosso programa.
Para além do problema da realocação de memória ainda existe o facto de, na linguagem C, os elementos dos arrays serem alocados de forma sequencial, ou seja, se o array for grande só o conseguimos alocar havendo quantidade suficiente de memória contígua livre. Contudo, no caso das listas os elementos são alocados dinamicamente, não sendo preciso existir grandes quantidades de memória contígua.
[...]