Discussion :

[mido1951]

Bonjour,

je voulais savoir si j'utilise une liste chainée ou enregistrement ?
Pour moi je veux bien utiliser les enregistrements mais ils m'ont dis d'utiliser les listes chainées donc si c'est possible je peux votre avis sur ça.

Merci.

[ternel]

Si tu te poses la question, c'est qu'il n'y a pas de réponse universelle.
Il nous faut donc un contexte, pourrais-tu nous exposer le tien?

Au passage, qu'appelles-tu un enregistrement?

[mido1951]

Si tu te poses la question, c'est qu'il n'y a pas de réponse universelle.
Il nous faut donc un contexte, pourrais-tu nous exposer le tien?

Au passage, qu'appelles-tu un enregistrement?

Un enregistrelent est une structure de données. la declaration comme la declaration d'une liste chainée mais pas de pointeur.
en fait, moi je veux stocker dans un tableau des position et chaque position a ses proriétés (par exemple).
donc le TABLEAU sera composé de deux colonnes (index, position) et dans la colonne position j'ai plusieurs valeurs: [pos1,num1],[pos2,num2],...
donc pour une ligne de mon tableau j'ai index1, [pos1,num1],[pos2,num2],... donx ici je voulais savoir est pour [pos1,num1],[pos2,num2] est j'utilise une liste chainée ou une structure sans pointer sur l'élément suivant?
je voulais avoir des avis des experts.
Merci

[Médinoc]

Ben ça dépend de ce que tu en fais.

• Si tu fais de la lecture pure avec besoin de recherche rapide (recherche dichotomique etc.) tu utilises un tableau.
• Si tu fais un truc qui est modifié de nombreuses fois durant l'exécution du code, une liste chaînée sera plus appropriée.

[ternel]

Le tableau et la liste chainée sont deux techniques pour répondre à un besoin commun: disposer d'une séquence de choses.
Il y a plusieurs différences entre ces deux techniques, et l'une d'elle est fondamentale:
un tableau est de taille constante, une liste chainée est de taille variable.

Il y a deux variantes principales de chainage: le chainage externe et le chainage dit intrusif.
supposons que je veuille une séquence de points.

avec un chainage intrusif (le plus classiquement utilisé en C), on aurait quelque chose comme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
struct point {
    int x, y;
    struct point* suivant;
};

Avec un chainage externe, par contre, on aurait deux structure: une chaine, et un point

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
struct point {
    int x, y;
};
 
struct chainon_point {
    struct point *p;
    struct chainon_point *suivant;
};

L'intéret de seconde solution est de pouvoir placer le même point dans plusieurs chaines.

Dans ton cas, si tu sais combien tu auras d'éléments à lister, préfère le tableau. Si tu connais un maximum tu peux aussi tenter le tableau.
Si ta séquence n'est pas vraiment bornée, tu n'as d'autre choix que la liste chainée

[mido1951]

Le tableau et la liste chainée sont deux techniques pour répondre à un besoin commun: disposer d'une séquence de choses.
Il y a plusieurs différences entre ces deux techniques, et l'une d'elle est fondamentale:
un tableau est de taille constante, une liste chainée est de taille variable.

Il y a deux variantes principales de chainage: le chainage externe et le chainage dit intrusif.
supposons que je veuille une séquence de points.

avec un chainage intrusif (le plus classiquement utilisé en C), on aurait quelque chose comme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
struct point {
    int x, y;
    struct point* suivant;
};

Avec un chainage externe, par contre, on aurait deux structure: une chaine, et un point

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
struct point {
    int x, y;
};
 
struct chainon_point {
    struct point *p;
    struct chainon_point *suivant;
};

L'intéret de seconde solution est de pouvoir placer le même point dans plusieurs chaines.

Dans ton cas, si tu sais combien tu auras d'éléments à lister, préfère le tableau. Si tu connais un maximum tu peux aussi tenter le tableau.
Si ta séquence n'est pas vraiment bornée, tu n'as d'autre choix que la liste chainée

merci pour ta reponse.
pour moi je ne connais pas la longueur de mon tableau mais je connais sa plus longue taille mais je pense les listes chainées permettent de gangner en mémoire parceque si j'utilise les enregistrements et je fixe une taille MAX peut etre que je perds en mémoire puisque je ne vais pas remplir toutes les cases à MAX.
qu'est ce que vous pensez?

[Sve@r]

merci pour ta reponse.
pour moi je ne connais pas la longueur de mon tableau mais je connais sa plus longue taille mais je pense les listes chainées permettent de gangner en mémoire parceque si j'utilise les enregistrements et je fixe une taille MAX peut etre que je perds en mémoire puisque je ne vais pas remplir toutes les cases à MAX.
qu'est ce que vous pensez?

Bonjour

Encore une fois ça dépend du contexte. Si MAX est de l'ordre de 100, ou 1000, ou 10000, ou même 100000 ça n'a pas d'importance (encore que ça dépende aussi de la taille de ta structure). Si MAX est de l'ordre du million ou milliard, ça peut jouer. Mais même si MAX était à 1 milliard mais que tu stockes effectivement 999 999 999 éléments ben alors ça ne jouerait plus (parce qu'avec un tableau ou une liste chainée ça reste 999 999 999 et que perdre "1" avec un tableau ne compte pas).

Ceci dit, leternel a écrit qu'un tableau était de taille constante mais il a oublié de préciser qu'il pouvait être aussi alloué dynamiquement (malloc) puis agrandi par la suite (realloc). Tu peux alors très bien définir un MAX à 1000 et allouer donc 1000 éléments d'un coup, puis dès que tu arrives au 1001° élément tu réalloues 1000 de plus. Et etc.
Ca peut se faire très facilement dans un algo de ce type

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#define MAX         (1000)
typedef struct {
	struct s_ton_element *tab;
	struct s_ton_element *tmp;
	size_t nb;
	size_t max;
} t_alloc;
 
t_alloc data;
data.tab=NULL;
data.tmp=NULL;
data.nb=0;
data.max=0;
 
while (je lis un élément à stocker)
{
	// Si on a atteint le max éléments stockés (ce qui arrivera aussi la première fois vu que nb et max sont égaux à 0)
	if (data.nb == data.max)
	{
		// On réalloue MAX de plus - Dans le cas où le pointeur à réallouer est NULL, realloc se comporte comme malloc
		data.max+=MAX;
		data.tmp=realloc(data.tab, data.max * sizeof(struct s_ton_element));
 
		// Vérification allocation échouée
		if (data.tmp == NULL)
		{
			// Dans ce cas, on ne peut plus rien faire - On nettoie donc ce qui avait été éventuellement alloué précédemment et on quitte
			free(data.tab);
			return valeur_specifique_indiquant_echec;
		}
 
		// L'allocation/réallocation a réussie, on la recopie dans la bonne zone
		data.tab=data.tmp;
	}
 
	// Quoi qu'il arrive, ici on a forcément la place de stocker notre élément
	data.tab[data.nb]=element_a_stocker;
 
	// On a stocké un élément de plus
	data.nb++;  // on peut regrouper les deux lignes en data.tab[data.nb++]=element_a_stocker;
}

Tu peux le dérouler dans tous les sens, tu auras toujours la place pour stocker tout ce que tu lis. Et sur un ordi avec beaucoup de mémoire tu peux tailler MAX en très large, mais si tu es restreint tu le tailles à 1.

Bien entendu ça a un inconvénient (toute solution possède toujours des avantages et des inconvénients) c'est que contrairement à la liste (où l'allocation est facile car tu alloues à chaque fois un élément qui sera alloué n'importe où il y a de la place pour un élément), le malloc/realloc doit toujours allouer la zone demandée en un seul bloc contigû (pour qu'on puisse l'utiliser comme un tableau) et que s'il n'a plus de place là où il se trouve pour répondre à la demande, il devra déplacer tout ce qui a déjà été alloué dans une zone plus large. Ce qui peut alors prendre du temps.

[koala01]

Salut,

En fait, la seule vraie différence entre un tableau et une liste chainée, c'est surtout la complexité algorithmique des différentes opération(Comprends par là : le "temps" qui sera nécessaire pour effectuer une opération donnée à une position donnée).

Ainsi, un tableau permet l'accès à n'importe quel élément qu'il contient en "temps constant" (on parle d'une complexité en O(1) ): que tu veuilles accéder au premier élément du tableau ou à son 999 999 999eme, le temps d'accès sera toujours le même, alors que l'accès à un élément donné d'une liste chainée sera en "temps proportionnel" (on parle d'une complexité en O(n) ) : il dépendra du nombre d'éléments par lesquels il faut passer pour "rejoindre" l'élément qui t'intéresse au départ d'un élément dont du dispose.

Tu l'auras compris : tu mettra énormément de temps à atteindre le 999 999 999eme élément d'une liste si tu pars du premier élément, alors que, dans les memes circonstances, tu atteindrait le deuxième élément de la liste "très rapidement"

Par contre, l'insertion d'un élément dans un tableau se fera avec une complexité en O(n), car il s'agira de "décaler" tous les éléments qui suivront celui que l'on essaye d'insérer pour lui laisser la place.

A l'inverse, l'insertion d'un élément dans un tableau se fera avec une complexité en O(1) car il "suffit" de modifier les liaisons qui existent entre l'élément ajouté, celui qui le précède et celui qui le suit.

Enfin la recherche peut éventuellement être dichotomique et se faire avec une complexité en O(log(n)) pour un tableau (s'il a été trié au préalable), alors que la recherche dans une liste triée se fera avec une complexité en O(n) (proportionnelle) car, même si elle est triée, il faudra toujours parcourir tous les éléments qui se trouvent entre le premier élément de la liste et... celui que l'on recherche.

Par contre, s'il y a une chose qui se fera de la même manière pour les tableaux et pour les listes chainées, c'est bien le fait de parcourir tous les éléments afin de leur appliquer un traitement donné : le parcours complet prend forcément un temps proportionnel au nombre d'éléments devant être traité

(NOTA : j'ai volontairement décidé de ne pas prendre les problèmes au cache en compte dans mes explications... Cela n'aurait rien apporté, à part un peu de confusion en plus )

Dés lors, si tu veux choisir entre un tableau et une liste chainée, il faut impérativement te poser une question primordiale : quelle utilisation compte tu faire de toutes les données que tu mettras dedans

Si tu passes "le plus clair de ton temps" à ajouter et à supprimer des éléments, tu as sans doute intérêt à utiliser une liste chainée.
Si tu passes le plus clair de ton temps à rechercher un élément particulier, un tableau trié sera sans doute intéressant (à moins de se tourner vers un arbre binaire, qui présente les mêmes avantages au niveau de la recherche, mais force les données à être triées, alors que c'est quelque chose qui doit être fait "manuellement" avec un tableau)

Si tu passes ton temps à parcourir tous les éléments, du premier au dernier, il n'y a -- du point de vue de la complexité -- aucune différence, mais c'est à ce moment là qu'interviendront ce que l'on appelle les "problèmes de cache" :

La nature même d'un ordinateur fait que l'on peut avoir de la mémoire pour laquelle l'accès aux données est très rapide ou bien que l'on peut avoir de très grandes quantités de mémoire, mais on ne peut pas avoir dans le même temps de très grandes quantités de mémoire auxquelles nous pourrions accéder très rapidement.

C'est la raison pour laquelle les processeurs actuels disposent de ce que l'on appelle de la "mémoire cache" : c'est une petite quantité de mémoire très rapide dans laquelle le processeur va régulièrement copier les données données dont il a besoin et qui se trouve dans la RAM (une grande quantité de mémoire, mais lente) ainsi que les données qui se trouvent "juste à coté"; dans l'espoir que, s'il a besoin d'une autre donnée par la suite, elle se situe "juste à coté" de la donnée à laquelle il vient d'accéder et qu'elle puisse donc être déjà dans la mémoire cache.

"Quand tout va bien", on va sans doute perdre un peu de temps à copier les données de la mémoire RAM vers le cache, mais, à coté de cela, l'accès à ces données sera beaucoup plus rapide, si bien que, avec un "peu de chance", le temps total passé à charger les donnée dans le cache et à accéder à toutes les données sera quand même encore moins important que celui que nous aurions passé à essayer d'accéder à toutes ces données au départ de la RAM.

Les problèmes commencent à apparaitre quand "tout ne va pas bien" et quand, après avoir accédé à une donnée (mettons : A), on veut accéder à une autre donnée (mettons : B) et que cette autre donnée n'est pas "suffisamment proche de A" que pour se retrouver elle aussi dans la mémoire cache.

Car, à ce moment là, le processeur vas rechercher la donné B dans la RAM et... charger les données qui sont proche de cette données dans le cache. Si cela n'arrive qu'une fois, ce n'est pas grave, mais, s'il faut recharger le cache à chaque fois que l'on veut accéder "à une autre donnée", on finit par perdre énormément alors que le processus était sensé nous en faire gagner, et ca, c'est pas cool

On appelle ce genre de phénomène un cache miss (une erreur de cache).

Mais bon, tu te demandes sans doute pourquoi je viens d'expliquer cela... La raison est simple : il se fait que les tableaux garantissent le fait que les données seront contigües ne mémoire et donc que "plusieurs données" seront forcément chargées en cache en même temps, si bien que, tant que l'on passe "d'une donnée à la suivante", nous pourrons profiter efficacement de la mise en cache, et donc, gagner énormément de temps.

A l'inverse, les autres possibilités (toutes celles qui ont recours à l'allocation dynamique pour les différents éléments, dont la liste chainée) présentent l'énorme inconvénient de permettre au système d'exploitation d'allouer la mémoire requise "où bon lui semble", et il est donc "relativement rare" que deux éléments se trouvent, effectivement, l'un à coté de l'autre en mémoire. Avec comme conséquence logique : il n'est pas rare d'observer des cache miss lorsqu'on utilise la liste chainée.

Et donc, il faut savoir que, si tu passes "le plus clair de ton temps" à parcourir tous les éléments du premier au dernier, il est plus que probable (mais attention, il faudra faire des tests pour le confirmer !) que tu auras sans doute au final de meilleures performances avec un tableau qu'avec une liste chainée.

Enfin bref : tout cela m'amène à une conclusion toute simple: Il n'y a jamais de "réponse ultime" car tes choix auront un impact majeur sur tout ce que tu feras par la suite. C'est donc à toi d'essayer de définir le plus rapidement possible quels seront tes besoins réels. Cette interventions devrait alors t'aider à faire le "moins mauvais choix" (à défaut de te permettre de faire le meilleur)