différence entre tableau et liste

Question

quelle est la différence entre array et list?

Answer 1

Dans C, un tableau est une zone de stockage contiguë de taille fixe contenant plusieurs objets, l'un après l'autre. Ce tableau est un "objet" dans le sens que C donne au mot - fondamentalement juste un peu de mémoire qui représente quelque chose. Un objet pourrait simplement être un int.

Vous pouvez distinguer légèrement entre le tableau les objets et le tableau les types. Souvent, les gens utilisent le tableau objets qui sont alloués avec malloc, et utilisés via un pointeur sur le premier élément. Mais C a aussi des types spécifiques pour les tableaux de différentes tailles, et aussi pour les tableaux de longueur variable, dont la taille est définie lors de leur création. Les VLA ont un nom légèrement trompeur: la taille est seulement "variable" dans le sens où elle n'est pas fixée au moment de la compilation. Il ne peut pas changer pendant la durée de vie de l'objet. Donc, quand je dis qu'un tableau est de taille fixe, je veux dire que la taille ne peut pas changer une fois que le tableau est créé, et cela inclut les VLA.Il y a realloc, qui retourne logiquement un pointeur vers un nouveau tableau qui remplace l'ancien, mais peut parfois renvoyer la même adresse passée, après avoir changé la taille du tableau en place. realloc fonctionne sur les allocations de mémoire, pas sur les tableaux en général.

C'est ce qu'est un tableau. Le langage de programmation C ne définit rien appelé une liste. Impossible de vraiment comparer quelque chose qui est bien défini, avec quelque chose qui n'est pas défini ;-) Habituellement, "liste" signifierait linked list, mais dans certains contextes ou dans d'autres langues, cela signifie d'autres choses. D'ailleurs, dans d'autres langages "array" pourrait signifier autre chose, bien que je ne puisse pas immédiatement penser à un langage où cela signifie quelque chose de très différent d'un tableau C.

Si votre question n'a vraiment rien à voir avec C, et est une langue agnostique des structures de données question, « Quelle est la différence entre un tableau et une liste chaînée », alors il est un double de celle-ci:

Array versus linked-list

Answer 2

Bien qu'il n'y ait rien comme unlistdansCen soi mais vous pouvez vous parler d'un mise en œuvre des listes chaînées.

Array: Accès aléatoire, taille prédéfinie.
Liste liée: Accès séquentiel, taille à l'exécution.

D'autres langues comme, disons Python, peuvent avoir à la fois list s et array s intégré et leur signification peut différer.

commentaires utiles ci-dessous:

Vous pouvez ajouter des listes de tableau. Les listes qui, en interne, sont un tableau qui est doublé lorsque nécessaire et réduit de moitié lorsque seulement 1/4 complet. Cela donne O (1) pour ajouter, supprimer, obtenir (index) amorti. - lasseespeholt

Python's list n'est pas une liste liée. Et la distinction entre Python list et array est list peut stocker n'importe quoi tandis que tableau peut seulement stocker les types primitifs (int, float, etc.). - KennyTM

Answer 3

Il n'existe pas de liste standard dans C. Il existe une telle chose en C++, où il est implémenté comme double-linked list.

Les principales différences sont que les tableaux ont accès aléatoire - vous pouvez accéder à tous les membres du réseau en temps O(1) (à savoir si a était un tableau, a[4]) et ont une taille prédéfinie au moment de la compilation. Les listes chaînées ont un accès séquentiel - pour accéder à un élément, vous devez parcourir la liste jusqu'à ce que vous arriviez à l'élément souhaité (ie si b était une liste chaînée, pour arriver au 5ème élément de b, vous devez parcourir les éléments 0, 1, 2, 3 et 4), et la taille peut être augmentée et rétrécie dynamiquement.

Answer 4

Une caractéristique souvent sous apprécié des structures de données liées est que vous pouvez les utiliser dans des situations où la mémoire est très fragmenté car il n'y avait aucune garantie de mémoire contiguë entre les éléments. Par exemple, vous pourriez avoir 100 Mo d'espace libre, mais seulement dire un maximum de mémoire libre de 10 Mo de longueur. Dans ce cas, vous pouvez seulement créer un tableau de taille 10Mo mais peut-être une liste chaînée potentiellement plus grande puisque vous seriez capable d'utiliser chaque mémoire libre suffisamment grande pour contenir un seul nœud.

Answer 5

1. Pour tableau, il a une taille fixe comme nous écrivons, new int [100] mais la liste n'a pas une taille fixe ... il peut aller et

2. insertion et la suppression est plus facile dans la liste que dans le tableau Raison: nous pouvons simplement utiliser pour changer les pointeurs pour insérer et supprimer pour la liste chaînée, mais pour l'insertion de tableau et de suppression a besoin shiftRight et shiftLeft

3. liste chaînée utilise un nœud de tête factice pour éviter les cas particuliers de insertion dans une liste vide ou suppression du dernier nœud d'une liste de taille d'unité; et, il utilise des liens doubles pour permettre l'itération dans les deux sens. Le coût du cours est l'espace supplémentaire nécessaire pour maintenir le nœud factice (coût minimal), et le lien précédent supplémentaire en plus du lien suivant habituel pour chaque nœud (coût beaucoup plus important). Dans le tableau, nous pouvons ajouter à l'aide de son accès aléatoire

4. Dans la liste Liée, la référence au nœud de queue est simplement header.prev, ce qui nous donne la possibilité d'ajouter à la liste en temps constant (sans avoir à itérer pour trouver la référence de queue, ou avoir à maintenir une référence de queue séparée). Mais dans le tableau, nous devons redimensionner le tableau avant de l'insérer.

5. Array a la flexibilité d'obtenir un accès aléatoire contrairement à Linked List.

liste liée a des problèmes tels que,

Il consomme le stockage de la mémoire supplémentaire pour le pointeur que nous utilisons!

complexité du temps de O (n) au lieu de O (1) comme dans le tableau

déplacement inverse est difficile pour une liste chaînée et si nous utilisons la liste doublement chaînée, un autre pointeur signifie plus de stockage de mémoire supplémentaire

Restriction de tas également! La mémoire est allouée uniquement s'il y a de l'espace disponible dans le tas. Si la mémoire est insuffisante, la mémoire ne sera pas créée.

tableau a des problèmes tels que,

une chance de perte de mémoire ou de pénurie.

Espérons que cela aide! :)

Answer 6

Le tableau a uniquement des types de données similaires (c'est-à-dire), ils sont de nature homogène. nous ne pouvons avoir qu'un tableau de chaînes, d'entiers, etc. la taille du tableau est également prédéfinie. mais dans le cas de la liste nous pouvons avoir n'importe quel type d'éléments. que ce soit un entier de chaîne ou une combinaison des deux. Les éléments null ou dupliqués sont également autorisés dans la liste. exemple de liste comprennent arraylist, linkedlist.here dans la liste la taille peut augmenter ou diminuer à tout moment.