Diferença entre matrizes e listas vinculadas

Matrizes vs Listas Vinculadas

Matrizes são a estrutura de dados mais usada para armazenar a coleção de elementos. A maioria das linguagens de programação fornece métodos para declarar facilmente matrizes e acessar elementos nas matrizes. A lista vinculada, mais precisamente a lista vinculada individualmente, também é uma estrutura de dados que pode ser usada para armazenar a coleção de elementos. É composto de 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 uma matriz. A Figura 2 mostra como uma matriz ficaria na memória.

O código acima define uma matriz que pode armazenar 5 números inteiros e eles são acessados ​​usando os índices de 0 a 4. Uma propriedade importante de uma matriz é que toda a matriz é alocada como um único bloco de memória e cada elemento obtém seu próprio espaço na matriz. Depois que uma matriz é definida, seu tamanho é fixo. Portanto, se você não tiver certeza do tamanho da matriz em tempo de compilação, terá que definir uma matriz grande o suficiente para estar no lado seguro. Mas, na maioria das vezes, vamos realmente usar menos número de elementos do que alocamos. Portanto, uma quantidade considerável de memória é realmente desperdiçada. Por outro lado, se a “matriz grande o suficiente” não for realmente grande o suficiente, o programa falhará.

Uma lista vinculada aloca memória para seus elementos separadamente em seu próprio bloco de memória e a estrutura geral é obtida ao vincular esses elementos como links em uma cadeia. Cada elemento em uma lista vinculada tem dois campos, como mostrado na Figura 3. O campo de dados mantém os dados reais armazenados e o próximo campo manté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, uma referência ao próximo elemento. O último elemento mantém um valor nulo em seu próximo campo. Qualquer elemento da lista pode ser acessado iniciando no cabeçalho e seguindo o próximo ponteiro até encontrar o elemento necessário.

Embora as matrizes e as listas vinculadas sejam semelhantes no sentido de que ambas são usadas para armazenar a coleção de elementos, elas incorrem em diferenças devido às estratégias usadas para alocar memória a seus elementos. Matrizes alocam memória para todos os seus elementos como um único bloco e o tamanho da matriz deve ser determinado em tempo de execução. Isso tornaria as matrizes ineficientes em situações em que você não sabe o tamanho da matriz em tempo de compilação. Como uma lista vinculada aloca memória para seus elementos separadamente, 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 diretos, em comparação com a maneira como você acessa diretamente os elementos em uma matriz usando seus índices.