Array vs Linked List – Differenza tra Array e Linked List

Vi siete mai chiesti, come vengono memorizzati i dati nella memoria del computer? Non puoi semplicemente gettare i dati nella memoria senza creare una struttura adeguata per i dati.

Per fornire una struttura organizzata per i dati da memorizzare all’interno della memoria del computer in modo da poter utilizzare e gestire i dati memorizzati nel modo più efficiente possibile, usiamo le strutture di dati.

Tutti i linguaggi di programmazione forniscono strutture di dati fondamentali come int, char, float ecc per memorizzare i valori di tipo primitivo. Ma con l’uso di tipi di dati definiti dall’utente possiamo creare strutture di dati come richiesto. È come creare la nostra casa con i mattoni, possiamo fare qualsiasi tipo di struttura che vogliamo.

Qui in questo articolo vedremo due tipi di dati definiti dall’utente più comunemente usati: Array e Linked List, la differenza tra Array e Linked List e la loro implementazione.

Array

Il tipo più semplice di struttura dati è Array che è usato per memorizzare set di dati simili in blocchi continui di memoria sotto un titolo comune o nome di variabile. Con la sua semplicità ci sono alcune barriere come la necessità di un blocco continuo di memoria e se la memoria libera non è disponibile in blocchi contigui, diventa inefficiente usare gli array.

Rappresentazione degli array

Rappresentazione degli array (Fonte)

L’indicizzazione degli array inizia con 0, e ogni elemento dell’array può essere raggiunto usando il suo indice. L’operazione sulla matrice è molto veloce, poiché ogni elemento è accessibile direttamente usando l’indicizzazione della matrice. Il nome dell’array è l’indirizzo base dell’array e tutti gli altri elementi possono essere raggiunti usando l’indirizzo base perché la memoria allocata all’array è consecutiva.

Linked List

D’altra parte, una struttura dati semplice ma molto utile che non ha bisogno di blocchi contigui di memoria è Linked List. Sono usate in situazioni in cui c’è bisogno di allocare la memoria dinamicamente, cioè durante l’esecuzione di un programma. Può essere visualizzato come un treno dove abbiamo un motore (testa) e tutti i vagoni (nodi) sono collegati al motore del treno direttamente o indirettamente attraverso altri vagoni.

Rappresentazione della lista collegata

Rappresentazione della lista collegata (fonte)

La lista collegata è un tipo di dati definito dall’utente dove tutti i nodi della lista sono collegati usando puntatori. Per accedere a qualsiasi nodo della lista, dobbiamo attraversare la lista linearmente a differenza dell’array dove possiamo accedere direttamente agli elementi.

Array vs Linked List – Differenza tra Array e Linked List

Parametri Array Linked List
Definizione È una collezione di elementi che hanno lo stesso tipo di dati con un nome comune. E’ un insieme ordinato di elementi che sono collegati da collegamenti o puntatori.
Dimensione Fissa, una volta dichiarata non può essere cambiata. Variabile, può essere cambiata durante l’esecuzione.
Allocazione della memoria Richiede blocchi di memoria contigui. La memoria casuale può essere allocata.
Accesso Diretto o accesso casuale, cioè, Specificare l’indice o il pedice dell’array. Accesso sequenziale, cioè, Attraversare partendo dal primo nodo della lista tramite il puntatore.
Inserimento e cancellazione Relativamente lento, poiché per inserire o cancellare qualsiasi elemento, altri elementi devono essere spostati per occupare lo spazio vuoto o fare spazio. Più veloce, facile ed efficiente, poiché è richiesto solo di collegare o scollegare il nodo.
Ricerca Ricerca binaria e ricerca lineare Ricerca lineare
Spazio extra Non è richiesto spazio extra. Per collegare i nodi della lista, si usano i puntatori che richiedono spazio extra.
Utilizzo della memoria Inefficiente Efficiente
Tipi Può essere monodimensionale, bidimensionale o multidimensionale. Può essere una lista collegata singolarmente, doppiamente o circolare.

Esecuzione delle matrici in C++

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

#include<iostream>
using namespace std;
int main()
{
int arr; // dichiarazione di un array intero di dimensione 5
arr=5; // assegnazione di valori agli elementi dell’array
arr=4; // notate che l’indicizzazione dell’array inizia da 0 e finisce a size-1
arr=3;
arr=2;
arr=1;
for(int i=0;i<5;i++)
cout<<arr<<” “; // stampa gli elementi dell’array
return 0;
}

Output

5 4 3 2 1

Implementazione di liste collegate 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

#include<iostream>
using namespace std;
/* Creazione di una struttura definita dall’utente per memorizzare i dati nella lista collegata */
struct Node
{
int data;
struct Node *next; // puntatore ai nodi collegati della lista
};
struct Node* head = NULL; // Inizialmente non ci sono elementi nella lista, quindi head non punta da nessuna parte
/* funzione per inserire e collegare i nodi nella lista */
void insert(int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // alloca la memoria dinamicamente
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
/* funzione per visualizzare i dati della lista */
void display()
{
struct Node* ptr;
ptr = head;
while (ptr != NULL)
{
cout<< ptr->data <<” “;
ptr = ptr->next;
}
}
int main()
{
insert(5); // inserire dati nella lista
insert(1);
insert(4);
insert(6);
insert(7);
cout<<“La lista collegata è: “;
display();
return 0;
}

Output

La lista collegata è: 7 6 4 1 5

Video Tutorial

Leave a Reply

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.