Tableau vs liste chaînée – Différence entre tableau et liste chaînée

Vous vous êtes déjà demandé, Comment les données sont stockées à l’intérieur de la mémoire de l’ordinateur ? Vous ne pouvez pas simplement jeter des données dans la mémoire sans faire une structure appropriée pour les données.

Pour fournir une structure organisée pour que les données soient stockées à l’intérieur de la mémoire de l’ordinateur afin que nous puissions utiliser et gérer les données stockées de la manière la plus efficace possible, nous utilisons les structures de données.

Tous les langages de programmation fournissent des structures de données fondamentales comme int, char, float etc. pour stocker les valeurs de type primitif. Mais avec l’utilisation de types de données définis par l’utilisateur, nous pouvons créer une structure de données selon les besoins. C’est comme créer notre maison avec des briques, nous pouvons faire n’importe quel type de structure que nous voulons.

Ici, dans cet article, nous allons voir deux types de données définis par l’utilisateur les plus couramment utilisés : Arrays et Linked List, la différence entre Array et Linked List et leur implémentation.

Array

Le type le plus simple de structure de données est Array qui est utilisé pour stocker un ensemble de données similaires dans des blocs continus de mémoire sous un titre commun ou un nom de variable. Avec sa simplicité vient quelques barrières comme il a besoin d’un bloc continu de mémoire et si la mémoire libre n’est pas disponible dans un bloc contigu, il devient inefficace d’utiliser les tableaux.

Représentation des tableaux

Représentation des tableaux (Source)

L’indexation des tableaux commence avec 0, et chaque élément du tableau peut être accédé en utilisant son index. L’opération sur le tableau est très rapide car tout élément peut être accédé directement en utilisant l’indexation du tableau. Le nom du tableau est l’adresse de base du tableau et tous les autres éléments peuvent être accédés en utilisant l’adresse de base car la mémoire allouée au tableau est consécutive.

Liste liée

D’autre part, une structure de données simple mais très utile qui n’a pas besoin de blocs contigus de mémoire est la liste liée. Elles sont utilisées dans les situations où il y a besoin d’allouer de la mémoire dynamiquement c’est-à-dire pendant l’exécution d’un programme. Elle peut être visualisée comme un train où nous avons un Moteur (Tête) et tous les wagons (nœuds) sont liés au moteur du train soit directement soit indirectement par d’autres wagons.

Représentation de la liste chaînée

Représentation de la liste chaînée (Source)

La liste chaînée est un type de données défini par l’utilisateur où tous les nœuds de la liste sont liés en utilisant des pointeurs. Pour accéder à n’importe quel nœud de la liste, nous devons parcourir la liste linéairement contrairement au tableau où nous pouvons accéder directement aux éléments.

Tableau vs liste chaînée – Différence entre tableau et liste chaînée

Paramètres Tableau Liste chaînée
Définition C’est une collection d’éléments ayant le même type de données avec un nom commun. C’est une collection ordonnée d’éléments qui sont reliés par des liens ou des pointeurs.
Taille Fixe, une fois déclarée ne peut être modifiée. Variable, peut être modifiée pendant l’exécution.
Allocation de mémoire Requiert des blocs de mémoire contigus. Une mémoire aléatoire peut être allouée.
Accès Accès direct ou aléatoire, c’est-à-dire , Spécifier l’index ou l’indice du tableau. Accès séquentiel, c’est-à-dire, Traverse à partir du premier nœud de la liste par le pointeur.
Insertion et suppression Relativement lent, car pour insérer ou supprimer un élément, d’autres éléments doivent être déplacés pour occuper l’espace vide ou faire de la place. Plus rapide, plus facile et efficace car il suffit de lier ou de délier un nœud.
Recherche Recherche binaire et recherche linéaire Recherche linéaire
Espace supplémentaire L’espace supplémentaire n’est pas nécessaire. Pour lier les nœuds de la liste, on utilise des pointeurs qui nécessitent un espace supplémentaire.
Utilisation de la mémoire Inefficace Efficace
Types Il peut être à une dimension, à deux dimensions ou multidimensionnel. Il peut s’agir d’une liste à liaison simple, double ou circulaire.

Mise en œuvre des tableaux en 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 ; // déclaration d’un tableau d’entiers de taille 5
arr=5 ; // affectation de valeurs aux éléments du tableau
arr=4 ; // remarquer que l’indexation du tableau commence à 0 et se termine à la taille 1
arr=3 ;
arr=2 ;
arr=1 ;
for(int i=0;i<5;i++)
cout<<arr<< »  » ; // impression des éléments du tableau
return 0 ;
}

Sortie

5 4 3 2 1

Implémentation de listes liées en 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 ;
/* Création d’une structure définie par l’utilisateur pour stocker des données dans une liste chaînée */
struct Node
{
int data ;
struct Node *next ; // pointeur vers les nœuds de liaison de la liste
} ;
struct Node* head = NULL ; // Initialement, il n’y a pas d’élément dans la liste, donc head ne pointe nulle part
/* fonction pour insérer et lier les nœuds de la liste */
void insert(int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)) ; // allocation dynamique de la mémoire
new_node->data = new_data ;
new_node->next = head ;
head = new_node ;
}
/* fonction permettant d’afficher les données de la liste */
void display()
{
struct Node* ptr ;
ptr = head ;
while (ptr != NULL)
{
cout<< ptr->data << »  » ;
ptr = ptr->next ;
}
}
int main()
{
insert(5) ; // insertion de données dans la liste
insert(1) ;
insert(4) ;
insert(6) ;
insert(7) ;
cout<< « La liste chaînée est :  » ;
display() ;
return 0 ;
}

Sortie

La liste chaînée est : 7 6 4 1 5

Tutoriel vidéo

.

Leave a Reply

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.