Array vs Linked List – Diferença entre Array e Linked List

Ever perguntou, Como os dados são armazenados dentro da memória do computador? Você não pode simplesmente jogar dados na memória sem fazer a estrutura apropriada para os dados.

Para fornecer uma estrutura organizada para que os dados sejam armazenados dentro da memória do computador para que nós possamos usar e gerenciar os dados armazenados da maneira mais eficiente possível, nós usamos Estruturas de Dados.

Todas as linguagens de programação fornecem estruturas de dados fundamentais como int, char, float etc. para armazenar os valores do tipo primitivo. Mas com o uso de tipos de dados definidos pelo usuário, podemos criar estruturas de dados conforme necessário. É como criar nossa casa com tijolos, nós podemos fazer qualquer tipo de estrutura que quisermos.

Aqui neste artigo veremos dois tipos de dados definidos pelo usuário mais comumente usados: Arrays e Linked List, Diferença entre Array e Linked List e sua implementação.

Array

O tipo mais simples de estrutura de dados é Array que é usado para armazenar um conjunto de dados similares em blocos contínuos de memória sob um cabeçalho ou nome de variável comum. Com sua simplicidade vem algumas barreiras como a necessidade de bloco contínuo de memória e se a memória livre não estiver disponível em bloco contíguo, torna-se ineficiente usar arrays.

Array Representation>

Array Representation (Source)

Arrays indexing starts with 0, and every element of the array can be accessed using its index. A operação em array é muito rápida, pois qualquer elemento pode ser acessado diretamente usando a indexação de array. O nome do array é o endereço base do array e todos os outros elementos podem ser acessados usando o endereço base porque a memória alocada ao array é consecutiva.

Linked List

Por outro lado, uma estrutura de dados simples mas muito útil que não precisa de blocos contíguos de memória é Linked List. Eles são usados em situações em que há necessidade de alocar memória dinamicamente que é durante o tempo de execução de um programa. Pode ser visualizado como um comboio onde temos uma locomotiva (cabeça) e todas as carruagens (nós) estão ligadas à locomotiva do comboio quer directa ou indirectamente através de outras carruagens.

Linked list Representação

Linked list Representação (fonte)

Linked list é um tipo de dados definido pelo utilizador onde todos os nós da lista estão ligados através de ponteiros. Para acessar qualquer nó da lista, devemos atravessar a lista linearmente, ao contrário do array onde podemos acessar diretamente os elementos.

Array vs Linked List – Diferença entre Array e Linked List

Parametros Array Linked List
Definição É uma coleção de elementos com o mesmo tipo de dados com um nome comum. É uma coleção ordenada de elementos que estão ligados por links ou ponteiros.
Tamanho Fixado, uma vez declarado não pode ser alterado. Variável, pode ser alterado durante o tempo de execução.
Alocação da memória Requerir blocos contíguos de memória. Memória aleatória pode ser alocada.
Acesso Acesso direto ou aleatório, ou seja Especificar o índice ou subscrito do array. Acesso sequencial, ou seja, Travessa a partir do primeiro nó da lista pelo ponteiro.
Inserção e Eliminação Relativamente lento, como para inserir ou eliminar qualquer elemento, outros elementos precisam ser deslocados para ocupar o espaço vazio ou fazer espaço. Mais rápido, mais fácil e eficiente como apenas ligando ou desligando o nó é necessário.
Pesquisa Pesquisa binária e linear Pesquisa linear
Espaço extra Espaço extra não é necessário. Para ligar nós de lista, são usados ponteiros que requerem espaço extra.
Utilização de memória Ineficiente Eficiente
Tipos Pode ser unidimensional, bidimensional ou multidimensional. Pode ser unidimensional, bidimensional ou circular lista ligada.

Realização em C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#incluir<iostream>
usando o namespace std;
int main()
{
int arr; // declarar um array inteiro de tamanho 5
arr=5; // atribuir valores aos elementos do array
arr=4; // notar que a indexação de array começa em 0 e termina em size-1
arr=3;
arr=2;
arr=1;
for(int i=0;i<5;i+++)
cout<<arr<<” “; // imprimir elementos de array
return 0;
}

Saída

5 4 3 2 1

Linked List Implementation in C+++

>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#incluir<iostream>
usando o namespace std;
/* Criando estrutura definida pelo usuário para armazenar dados na lista ligada */
Nó estruturador
{
int data;
structure Node *next; // ponteiro para ligar nós da lista
};
struct Node* head = NULL; // Inicialmente não há nenhum elemento na lista, então a cabeça não aponta para lugar nenhum
/* função para inserir e ligar nós à lista */
void insert(int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // alocando memória dinamicamente
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
/* função para exibir dados da lista */
display()
{
Nó estruturante* ptr;
ptr = cabeça;
while (ptr != NULL)
{
cout<< ptr->dados <<” “;
ptr = ptr->próximo;
}
}
int main()
{
insert(5); // inserindo dados na lista
insert(1);
insert(4);
insert(6);
insert(7);
cout<<“A lista ligada é: “;
display();
return 0;
}

>561515>

A lista ligada é: 7 6 4 1 5

Video Tutorial

Leave a Reply

Deixe uma resposta

O seu endereço de email não será publicado.