Arrays armazenar elementos em locais de memória contíguos, resultando em endereços facilmente calculáveis para os elementos armazenados e isso permite um acesso mais rápido a um elemento em um índice específico. As listas vinculadas são menos rígidas em sua estrutura de armazenamento e os elementos normalmente não são armazenados em locais contíguos, portanto, precisam ser armazenados com tags adicionais que dêem uma referência ao elemento seguinte. Essa diferença no esquema de armazenamento de dados decide qual estrutura de dados seria mais adequada para uma determinada situação.

Esquema de armazenamento de dados de um array

Esquema de armazenamento de dados de uma lista ligada

As maiores diferenças estão listadas abaixo:

• Tamanho: Como os dados só podem ser armazenados em blocos contíguos de memória em um array, seu tamanho não pode ser alterado em tempo de execução devido ao risco de sobrescrever sobre outros dados. Entretanto, em uma lista ligada, cada nó aponta para o próximo de modo que os dados possam existir em endereços dispersos (não contíguos); isto permite um tamanho dinâmico que pode mudar no tempo de execução.
• Alocação de memória: Para arrays em tempo de compilação e em tempo de execução para listas ligadas.
• Eficiência da memória: Para o mesmo número de elementos, as listas ligadas usam mais memória como referência para o próximo nó também é armazenada junto com os dados. No entanto, a flexibilidade de tamanho nas listas vinculadas pode fazê-las usar menos memória em geral; isto é útil quando há incerteza sobre o tamanho ou há grandes variações no tamanho dos elementos de dados; memória equivalente ao limite superior do tamanho tem que ser alocada (mesmo que nem toda esteja sendo usada) enquanto se usam arrays, enquanto as listas vinculadas podem aumentar seus tamanhos passo a passo proporcionalmente à quantidade de dados.
• Tempo de execução: Qualquer elemento de um array pode ser acessado diretamente com seu índice; no entanto, no caso de uma lista ligada, todos os elementos anteriores devem ser atravessados para alcançar qualquer elemento. Além disso, uma melhor localização de cache em arrays (devido à alocação de memória contígua) pode melhorar significativamente o desempenho. Como resultado, algumas operações (como modificar um determinado elemento) são mais rápidas em arrays, enquanto outras (como inserir/eliminar um elemento nos dados) são mais rápidas em listas ligadas.

A seguir são os pontos a favor das Listas Ligadas.
(1) O tamanho das arrays é fixo: Por isso devemos saber com antecedência o limite superior do número de elementos. Também, geralmente, a memória alocada é igual ao limite superior independentemente do uso, e em usos práticos, o limite superior raramente é atingido.

(2) Inserir um novo elemento num conjunto de elementos é caro porque tem de ser criada uma sala para os novos elementos e para criar uma sala os elementos existentes têm de ser deslocados.

Por exemplo, suponha que nós mantemos uma lista ordenada de IDs em um id de array.

id = .

E se quisermos inserir um novo ID 1005, então para manter a ordem ordenada, temos que mover todos os elementos após 1000 (excluindo 1000).

Deleção também é cara com arrays até que algumas técnicas especiais sejam usadas. Por exemplo, para apagar 1010 no id, tudo após 1010 tem que ser movido.

Lista ligada fornece as duas seguintes vantagens sobre as matrizes
1) Tamanho dinâmico
2) Facilidade de inserção/eliminação

Lista ligada tem os seguintes inconvenientes:
1) Acesso aleatório não é permitido. Temos de aceder aos elementos sequencialmente a partir do primeiro nó. Portanto, não podemos fazer uma pesquisa binária com listas vinculadas.
2) É necessário espaço de memória extra para um ponteiro com cada elemento da lista.
3) Arrays têm melhor localização de cache que pode fazer uma grande diferença na performance.