Neste artigo vamos conhecer as duas estruturas de dados mais básicas: arrays e listas. Abordarei suas características e diferenças.
Introdução
Antes uma breve analogia sobre como funciona a memória de um computador. Imagine a memória como um conjunto de gavetas na qual cada gaveta possui um endereço. Para armazenar algo em uma dessas gavetas solicitamos ao computador um espaço e, portanto, ele irá fornecer um endereço onde você pode armazenar o item.
Arrays e listas encadeadas são duas formas de armazenar múltiplos itens na memória. Não existe apenas uma maneira correta de armazenar itens, cada estrutura tem seus prós e contras. Por fim, vamos conhecê-las.
Arrays
Para armazenar itens na memória, por exemplo, a temperatura média de cada mês do ano, podemos usar um array. Usar um array significa que todas as temperaturas estão armazenadas de forma contínua, ou seja, uma ao lado da outra na memória.
Mas repare que assim como na figura acima não podemos adicionar mais um item, pois o próximo slot de memória, isto é, a gaveta, está ocupada por coisas de outro programa.
Para armazenar novas temperaturas será preciso mover todas elas para um lugar onde todas coubessem. Dessa forma, será preciso pedir ao computador uma nova área de memória e mover todas as temperaturas para lá.
Mas toda vez que formos armazenar uma nova temperatura de novo ficamos sem espaço e será preciso mover todas novamente.
Adicionar novos itens em um array é muito lento. Mesmo que reservamos espaço extra por precaução, isso traz desvantagens como desperdiçar memória caso não seja usado os espaços extras e caso seja necessário adicionar mais itens será preciso mover eles de qualquer maneira.
É a partir desse problema que surgem as listas encadeadas.
Listas encadeadas
Listas encadeadas ou listas ligadas, também armazenam múltiplos itens, mas não de forma contínua como os arrays. Os itens armazenados podem estar em qualquer lugar da memória, ou seja, não vão estar um ao lado do outro.
Mesmo que cada item esteja em qualquer lugar da memória, ainda assim formam uma coleção de itens, uma lista, pois cada um deles armazena o endereço do próximo item da lista. O item é constituído de um nó que armazena o item propriamente dito e uma referência, também conhecida como ponteiro, para o próximo item.
As listas encadeadas são uma estrutura de dados dinâmica, isso significa que adicionar um item nelas é mais fácil, porque basta armazenar em qualquer lugar da memória e armazena uma referência (ponteiro) para o endereço do item anterior. Temos um monte de endereços aleatórios na memória ligados.
E com isso resolvemos o problema de ter de mover os itens, pois com as listas encadeadas isso não será preciso. Listas encadeadas são melhores para inserir itens do que arrays.
Mas, quando se trata de acessar itens aleatórios, as listas encadeadas são péssimas. Isso porque não é possível pular de um item para outro, pois não conhecemos seu endereço. É preciso ler um item de cada vez, ou seja, você precisa ir de um item 1 para pegar o endereço do item 2 e do item 2 para pegar o endereço do item 3 e assim por diante até encontrar o item desejado.
Esse comportamento é diferente nos arrays. Conhecemos o endereço de cada item, logo podemos calcular instantaneamente a posição de um elemento na memória. Por exemplo, imagine um array com sete elementos e sabemos que o endereço do primeiro item está no índice 0. Podemos deduzir que o endereço do item 5 estará no índice 4.
Os elementos de um array são numerados. Essa numeração começa por 0 e não no 1, são os chamados índices. Leia nosso artigo sobre como aplicar arrays e listas na prática para conhecer melhor essa terminologia.
Conclusão
Podemos observar vantagens e desvantagens no uso de cada estrutura. Consequentemente, o tempo de execução para operações simples em cada uma delas será diferente. Veremos o desempenho e operações como inserções e deleções nessas estruturas no artigo arrays e listas encadeadas na prática. Iremos pôr a mão na massa com aplicações simples em código, confere lá!