Matrizes vs listas vinculadas
Arrays são a estrutura de dados mais comumente usada para armazenar coleção de elementos. A maioria das linguagens de programação fornece métodos para declarar arrays facilmente e acessar elementos nos arrays. A lista vinculada, mais precisamente a lista vinculada de forma simples, também é uma estrutura de dados que pode ser usada para armazenar a coleção de elementos. É composto por uma sequência de nós e cada nó tem uma referência ao próximo nó da sequência.
Mostrado na figura 1, está um trecho de código normalmente usado para declarar e atribuir valores a uma matriz. A Figura 2 mostra como um array ficaria na memória.
O código acima define um array que pode armazenar 5 inteiros e eles são acessados usando índices de 0 a 4. Uma propriedade importante de um array é que todo o array é alocado como um único bloco de memória e cada elemento obtém seu próprio espaço no array. Depois que um array é definido, seu tamanho é fixo. Portanto, se você não tiver certeza sobre o tamanho do array em tempo de compilação, terá que definir um array grande o suficiente para estar no lado seguro. Mas, na maioria das vezes, usaremos menos número de elementos do que alocamos. Portanto, uma quantidade considerável de memória é realmente desperdiçada. Por outro lado, se o “array grande o suficiente” não for realmente grande o suficiente, o programa travaria.
Uma lista encadeada aloca memória para seus elementos separadamente em seu próprio bloco de memória e a estrutura geral é obtida ligando esses elementos como elos em uma cadeia. Cada elemento em uma lista vinculada possui dois campos, conforme mostrado na Figura 3. O campo de dados contém os dados reais armazenados e o próximo campo contém a referência ao próximo elemento na cadeia. O primeiro elemento da lista vinculada é armazenado como o cabeçalho da lista vinculada.
Figura 3: Elemento de uma lista vinculada
A Figura 4 mostra uma lista vinculada com três elementos. Cada elemento armazena seus dados e todos os elementos, exceto o último, armazenam uma referência ao próximo elemento. O último elemento contém um valor nulo em seu próximo campo. Qualquer elemento da lista pode ser acessado começando no cabeçalho e seguindo o próximo ponteiro até encontrar o elemento necessário.
Mesmo que os arrays e as listas vinculadas sejam semelhantes no sentido de que ambos são usados para armazenar coleções de elementos, eles incorrem em diferenças devido às estratégias que usam para alocar memória aos seus elementos. Os arrays alocam memória para todos os seus elementos como um único bloco e o tamanho do array deve ser determinado em tempo de execução. Isso tornaria os arrays ineficientes em situações em que você não sabe o tamanho do array em tempo de compilação. Como uma lista encadeada aloca memória para seus elementos separadamente, ela seria muito eficiente em situações nas quais você não sabe o tamanho da lista em tempo de compilação. A declaração e o acesso a elementos em uma lista vinculada não seriam simples em comparação com a maneira como você acessa diretamente os elementos em uma matriz usando seus índices.
