Variedade e Lista vinculada são as duas formas de organizar os dados na memória. Antes de entender as diferenças entre os Variedade e a Lista vinculada , primeiro olhamos em uma matriz e uma lista vinculada .
comando all caps excel
O que é uma matriz?
Uma estrutura de dados que contém os elementos do mesmo tipo. Uma estrutura de dados é uma forma de organizar os dados; uma matriz é uma estrutura de dados porque organiza os dados sequencialmente. Um array é um grande pedaço de memória no qual a memória é dividida em pequenos blocos, e cada bloco é capaz de armazenar algum valor.
Suponha que criamos um array que consiste em 10 valores, então cada bloco armazenará o valor de um tipo inteiro. Se tentarmos armazenar o valor em um array de tipos diferentes, então não é um array correto e gerará um erro em tempo de compilação.
Declaração de matriz
Uma matriz pode ser declarada como:
data_type name of the array[no of elements]
Para declarar um array, primeiro precisamos especificar o tipo do array e depois o nome do array. Dentro dos colchetes, precisamos especificar o número de elementos que nosso array deve conter.
Vamos entender através de um exemplo.
int a[5];
No caso acima, declaramos um array de 5 elementos com ' a 'nome de um inteiro tipo de dados.
O que é lista vinculada?
Uma lista vinculada é a coleção de nós armazenados aleatoriamente. Cada nó consiste em dois campos, ou seja, dados e link . Aqui, os dados são o valor armazenado naquele nó específico e o link é o ponteiro que contém o endereço do próximo nó.
Diferenças entre array e lista vinculada
Não podemos dizer qual estrutura de dados é melhor, ou seja, array ou lista vinculada . Pode haver a possibilidade de que uma estrutura de dados seja melhor para um tipo de requisito, enquanto a outra estrutura de dados seja melhor para outro tipo de requisito. Existem vários fatores, como quais são as operações frequentes realizadas na estrutura de dados ou o tamanho dos dados, e outros fatores também com base nos quais a estrutura de dados é selecionada. Agora veremos algumas diferenças entre o array e a lista vinculada com base em alguns parâmetros.
1. Custo de acesso a um elemento
No caso de um array, independentemente do tamanho de um array, um array leva um tempo constante para acessar um elemento. Em um array, os elementos são armazenados de maneira contígua, portanto, se soubermos o endereço base do elemento, poderemos facilmente obter o endereço de qualquer elemento em um array. Precisamos realizar um cálculo simples para obter o endereço de qualquer elemento de um array. Então, acessar o elemento em um array é O(1) em termos de complexidade de tempo.
Na lista vinculada, os elementos não são armazenados de forma contígua. Consiste em vários blocos e cada bloco é representado como um nó. Cada nó possui dois campos, ou seja, um é para o campo de dados e outro armazena o endereço do próximo nó. Para encontrar qualquer nó na lista vinculada, primeiro precisamos determinar o primeiro nó conhecido como nó principal. Se tivermos que encontrar o segundo nó na lista, precisaremos percorrer a partir do primeiro nó e, na pior das hipóteses, para encontrar o último nó, estaremos percorrendo todos os nós. O caso médio para acessar o elemento é O(n).
como ler o arquivo csv em java
Concluímos que o custo de acesso a um elemento do array é menor que o da lista encadeada. Portanto, se tivermos algum requisito para acessar os elementos, então array é uma escolha melhor.
2. Custo de inserção de um elemento
Pode haver três cenários na inserção:
No caso de uma lista vinculada, para inserir um elemento no início da lista vinculada, criaremos um novo nó, e o endereço do primeiro nó será adicionado ao novo nó. Desta forma, o novo nó torna-se o primeiro nó. Portanto, a complexidade do tempo não é proporcional ao tamanho da lista. A complexidade do tempo seria constante, ou seja, O(1).
Se o array não estiver cheio, podemos adicionar diretamente o novo elemento por meio do índice. Neste caso, a complexidade do tempo seria constante, ou seja, O(1). Se o array estiver cheio, primeiro precisamos copiá-lo para outro array e adicionar um novo elemento. Neste caso, a complexidade de tempo seria O(n).
Para inserir um elemento no final da lista vinculada, temos que percorrer toda a lista. Se a lista vinculada consistir em n elementos, então a complexidade de tempo seria O(n).
Suponha que queremos inserir o elemento no iºposição da matriz; precisamos deslocar os n/2 elementos para a direita. Portanto, a complexidade do tempo é proporcional ao número de elementos. A complexidade do tempo seria O(n) para o caso médio.
modelos de aprendizado de máquina
No caso de lista vinculada, temos que ir até aquela posição onde devemos inserir o novo elemento. Mesmo assim, não precisamos realizar nenhum tipo de deslocamento, mas temos que percorrer até a posição n/2. O tempo gasto é proporcional ao número n de elementos, e a complexidade de tempo para o caso médio seria O(n).
A lista vinculada resultante é:
A implementação de um array é fácil em comparação com a lista vinculada. Ao criar um programa usando uma lista vinculada, o programa está mais sujeito a erros como falha de segmentação ou vazamento de memória. Portanto, é preciso tomar muito cuidado ao criar um programa na lista vinculada.
A lista vinculada tem tamanho dinâmico, enquanto a matriz é estática. Aqui, estático não significa que não podemos decidir o tamanho em tempo de execução, mas não podemos alterá-lo depois que o tamanho for decidido.
3. Requisitos de memória
Como os elementos de um array são armazenados em um bloco contíguo de memória, o array tem tamanho fixo. Suponha que temos um array de tamanho 7, e o array consiste em 4 elementos, então o resto do espaço não é utilizado. A memória ocupada pelos 7 elementos:
Espaço de memória = 7*4 = 28 bytes
Onde 7 é o número de elementos em uma matriz e 4 é o número de bytes de um tipo inteiro.
No caso de lista vinculada, não há memória não utilizada, mas a memória extra é ocupada pelas variáveis de ponteiro. Se os dados forem do tipo inteiro, então a memória total ocupada por um nó é de 8 bytes, ou seja, 4 bytes para dados e 4 bytes para variável de ponteiro. Se a lista vinculada consistir em 4 elementos, então o espaço de memória ocupado pela lista vinculada seria:
driver da web
Espaço de memória = 8*4 = 32 bytes
A lista vinculada seria uma escolha melhor se a parte dos dados fosse maior. Suponha que os dados tenham 16 bytes. O espaço de memória ocupado pelo array seria 16*7=112 bytes enquanto a lista vinculada ocupa 20*4=80, aqui especificamos 20 bytes como 16 bytes para o tamanho dos dados mais 4 bytes para a variável do ponteiro. Se escolhermos um tamanho maior de dados, a lista vinculada consumirá menos memória; caso contrário, depende dos fatores que estamos adotando para determinar o tamanho.
Vejamos as diferenças entre o array e a lista vinculada em formato tabular.
| Variedade | Lista vinculada |
|---|---|
| Uma matriz é uma coleção de elementos de um tipo de dados semelhante. | Uma lista vinculada é uma coleção de objetos conhecida como nó, onde o nó consiste em duas partes, ou seja, dados e endereço. |
| Os elementos da matriz são armazenados em um local de memória contíguo. | Os elementos da lista vinculada podem ser armazenados em qualquer lugar da memória ou armazenados aleatoriamente. |
| Array funciona com uma memória estática. Aqui, memória estática significa que o tamanho da memória é fixo e não pode ser alterado em tempo de execução. | A lista vinculada funciona com memória dinâmica. Aqui, memória dinâmica significa que o tamanho da memória pode ser alterado em tempo de execução de acordo com nossos requisitos. |
| Os elementos da matriz são independentes uns dos outros. | Os elementos da lista vinculada dependem uns dos outros. Como cada nó contém o endereço do próximo nó, para acessar o próximo nó, precisamos acessar o nó anterior. |
| Array leva mais tempo ao executar qualquer operação como inserção, exclusão, etc. | A lista vinculada leva menos tempo ao executar qualquer operação como inserção, exclusão, etc. |
| Acessar qualquer elemento de um array é mais rápido, pois o elemento de um array pode ser acessado diretamente por meio do índice. | O acesso a um elemento em uma lista vinculada é mais lento, pois começa a percorrer a partir do primeiro elemento da lista vinculada. |
| No caso de um array, a memória é alocada em tempo de compilação. | No caso de uma lista vinculada, a memória é alocada em tempo de execução. |
| A utilização da memória é ineficiente no array. Por exemplo, se o tamanho do array for 6 e o array consistir apenas em 3 elementos, o restante do espaço não será utilizado. | A utilização da memória é eficiente no caso de uma lista vinculada, pois a memória pode ser alocada ou desalocada em tempo de execução de acordo com nossa necessidade. |