Diferença entre Lista de Array e Lista Ligada Diferença entre
Como os dados são armazenados?
A lista de matrizes e a lista vinculada são termos comuns quando se trata de armazenamento e recuperação de dados. Embora existam muitos dispositivos de armazenamento, em última análise, eles dependem do mecanismo de armazenamento. Estes dois mecanismos de armazenamento colocam seus dados nos dispositivos de armazenamento e os recuperam quando necessário. Vamos dar uma olhada em como eles armazenam dados em sua memória. A lista Array usa um armazenamento seqüencial, e as peças de dados são armazenadas uma após a outra. Esta é talvez uma forma mais simples de armazenamento - evita confusão. Sim, podemos recuperar o próximo item ou dados da próxima localização de memória da lista de matrizes; No entanto, ele é armazenado com a ajuda de ponteiros na lista vinculada. Aqui precisamos de dois locais de memória para armazenamento - um para os dados, o outro para o ponteiro. Um ponteiro aborda a localização da memória dos próximos dados. Podemos entender facilmente que a Lista vinculada nunca armazena dados sequencialmente; Em vez disso, ele usa um mecanismo de armazenamento aleatório. Os ponteiros são os elementos-chave na localização dos locais de dados na memória.
Array dinâmico e lista vinculada
Já discutimos como os dois mecanismos de armazenamento colocam dados e podemos dar um termo "matriz dinâmica" para o esquema de armazenamento interno da lista de matrizes. Basta colocar as peças de dados uma após a outra - portanto, o nome - enquanto a lista Ligada usa uma lista interna com a ajuda de ponteiros para rastrear o próximo item. Portanto, ele usa uma lista interna vinculada, como uma lista individual ou duplamente vinculada para nos mostrar os próximos dados.
Uso de memória
Como a lista Array armazena apenas os dados reais, precisamos apenas de espaço para os dados que armazenamos. Por outro lado, na lista vinculada, usamos ponteiros também. Portanto, dois locais de memória são necessários, e podemos dizer que a lista vinculada consome mais memória que a lista de matrizes. Um lado vantajoso da lista Ligada é que ele nunca exige locais de memória contínua para armazenar nossos dados, em oposição à lista de Array. Os ponteiros são capazes de manter a posição da próxima localização de dados, e podemos até usar slots de memória menores que não são contínuos. Quando se trata de uso de memória, os ponteiros desempenham o papel principal na lista vinculada, assim como a eficácia deles.
Tamanho da lista de matriz inicial e lista vinculada
Com a lista Array, mesmo uma lista vazia requer um tamanho de 10, mas com uma lista Linked, não precisamos de um espaço tão grande. Podemos criar uma lista Vinculada vazia com um tamanho de 0. Mais tarde, podemos aumentar o tamanho, conforme necessário.
Recuperação de dados
A recuperação de dados é mais simples na lista Array como ele armazena seqüencialmente. Tudo o que faz é identificar a primeira localização de dados; A partir daí, o próximo local é acessado sequencialmente para recuperar o resto.Calcula como a primeira posição de dados + 'n', onde 'n' é a ordem dos dados na lista Array. A lista Ligada refere o ponteiro inicial para encontrar o primeiro local de dados e, a partir daí, ele se refere ao ponteiro associado a cada dado para encontrar a próxima localização de dados. O processo de recuperação depende principalmente dos ponteiros aqui, e eles efetivamente nos mostram o próximo local de dados.
Fim dos dados
A lista Array usa um valor nulo para marcar o fim dos dados, enquanto a lista vinculada usa um ponteiro nulo para este propósito. Assim que o sistema reconhecer dados nulos, a lista Array interrompe a próxima recuperação de dados. De forma semelhante, o ponteiro nulo impede o sistema de continuar a próxima recuperação de dados.
Reverse Traversal
A lista Linked nos permite percorrer as direções inversas com a ajuda de descendingiterator (). No entanto, não temos essa facilidade em uma lista de Array - a travessia reversa torna-se um problema aqui.
Sintaxe
Vejamos a sintaxe Java de ambos os mecanismos de armazenamento.
Criação da lista de matrizes:
List arraylistsample = new ArrayList ();
Adicionando objetos à Lista de Array:
Arraylistsample. adicionar ("nome1");
Arraylistsample. adicionar ("nome2");
É assim que aparecerá a lista resultante da matriz - [name1, name2].
Criação da lista vinculada:
Lista linkedlistsample = new linkedList ();
Adicionando objetos à Lista vinculada:
Linkedlistsample. adicionar ("nome3");
Linkedlistsample. adicionar ("nome4");
É assim que a lista vinculada resultante será semelhante a - [name3, name4].
Qual é melhor para a operação Get ou Search?
A lista Array leva O (1) tempo para executar qualquer busca de dados, enquanto a lista Ligada leva u (n) para a pesquisa de dados n th . Portanto, uma lista Array sempre usa um tempo constante para qualquer busca de dados, mas na lista Linked, o tempo depende da posição dos dados. Portanto, as listas de matrizes são sempre uma escolha melhor para as operações Get ou Search.
Qual é melhor para a operação de inserção ou adição?
Tanto a lista Array como a Lista vinculada levam o tempo O (1) para a adição de dados. Mas se a matriz estiver cheia, a lista Array leva uma quantidade considerável de tempo para redimensioná-la e copiar os itens para o novo. Nesse caso, a lista vinculada é a melhor escolha.
Qual é melhor para a operação de remoção?
A operação de remoção leva quase a mesma quantidade de tempo na lista Array e na Lista vinculada. Na lista Array, esta operação exclui os dados e, em seguida, muda a posição dos dados para formar a matriz mais nova - é preciso tempo de O (n). Na lista Ligada, esta operação atravessa os dados específicos e muda as posições do ponteiro para formar a lista mais recente. O tempo para o percurso e a remoção também é O (n).
Qual é mais rápido?
Sabemos que uma lista Array usa uma matriz interna para armazenar os dados reais. Portanto, se algum dado é excluído, todos os dados futuros precisam de uma mudança de memória.Obviamente, isso exige uma quantidade considerável de tempo e retarda as coisas. Essa mudança de memória não é necessária na lista vinculada, pois tudo o que faz é mudar a localização do ponteiro. Portanto, uma lista vinculada é mais rápida do que uma lista de Array em qualquer tipo de armazenamento de dados. No entanto, isso é puramente dependente do tipo de operação, i. e. Para a operação Get ou Search, a lista Linked tem muito mais tempo do que uma lista Array. Quando observamos o desempenho geral, podemos dizer que a lista vinculada é mais rápida.
Quando usar uma lista de matrizes e uma lista vinculada?
Uma lista de matrizes é mais adequada para requisitos de dados menores, onde a memória contínua está disponível. Mas quando lidamos com enormes quantidades de dados, a disponibilidade de memória contínua implementa os mecanismos de armazenamento de dados, seja pequeno ou enorme. Em seguida, decida qual deles escolher - a lista Array ou a lista Linked. Você pode prosseguir com uma lista de matrizes quando você precisa apenas de armazenamento e recuperação de dados. Mas uma lista pode ajudá-lo além disso, manipulando dados. Depois de decidir a frequência com que é necessária a manipulação de dados, é importante verificar qual o tipo de recuperação de dados que você geralmente executa. Quando é apenas obter ou pesquisar, a lista de matriz é a melhor escolha; para outras operações como Inserção ou Exclusão, vá em frente com a lista Ligada.
Vejamos as diferenças em forma de tabela.
