Arrays 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 individualmente, também é uma estrutura de dados que pode ser usada para armazenar uma coleção de elementos. É composto por uma sequência de nós e cada nó tem uma referência ao próximo nó na sequência.
Mostrado na figura 1, é um pedaço de código normalmente usado para declarar e atribuir valores a um array. 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 o array inteiro é alocado como um único bloco de memória e cada elemento recebe seu próprio espaço na matriz. Uma vez que uma matriz é definida, seu tamanho é fixo. Então, se você não tiver certeza sobre o tamanho do array em tempo de compilação, você teria que definir um array grande o suficiente para estar no lado seguro. Mas, na maioria das vezes, usaremos um número menor 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 grande o suficiente, o programa irá travar.
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 encadeada é armazenado como o cabeçalho da lista encadeada.
| dados | próximo |
Figura 3: Elemento de uma lista encadeada
A Figura 4 mostra uma lista encadeada 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 encadeadas sejam semelhantes no sentido de que ambos são usados para armazenar coleção de elementos, eles incorrem em diferenças devido às estratégias que usam para alocar memória aos seus elementos. 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 forma como você acessa diretamente os elementos em uma matriz usando seus índices.
