Nous avons vu qu'il est très simple de créer les structures de données qui sont semblables organisé à la manière que la mémoire d'ordinateur est organisée. Par exemple, la liste de l'employé de la compagnie d'ABC est une structure de données linéaire. Puisque la mémoire d'ordinateur est également linéaire, il est très facile de voir comment nous pouvons représenter cette liste avec de la mémoire d'ordinateur. Toute structure de données qui organise les éléments d'informations un après que l'autre soit connu pendant que structure de données linéaire. Jusqu'ici nous avons vu deux exemples des structures de données linéaires : la structure de données de corde et la compagnie d'ABC énumèrent.

Vous avez pu avoir noté que ces deux exemples des structures de données linéaires ressemblent entre eux. C'est parce qu'elles toutes les deux sont des genres vraiment différents de listes. Généralement toutes les structures de données linéaires ressemblent à la liste. Cependant, ceci ne signifie pas que toutes structures de données linéaires sont exactement identiques. Supposer que je veux concevoir une liste pour stocker les noms des employés d'ABC dans l'ordinateur. Une conception possible est d'organiser les noms semblables à l'image d'exemple ci-dessus. Une autre conception possible est d'employer les indicateurs que nous avons appris environ dans la dernière leçon. Tandis que ces deux conceptions fournissent la même fonctionnalité la manière elles sont mises en application dans l'ordinateur est beaucoup différente. Ceci signifie qu'il y a une vue abstraite d'une liste qui est distincte de n'importe quelle exécution particulière d'ordinateur

Vous avez pu avoir également noté que l'image des employés d'ABC n'est pas aussi exactement identique que la liste originale. Quand nous faisons une liste des noms, nous tendons à organiser cette liste en colonne plutôt qu'une rangée. Dans ce cas-ci, la représentation conceptuelle ou logique d'une liste est la colonne des noms. Cependant, la représentation physique de la liste dans la mémoire d'ordinateur est la rangée des cordes. Pour la plupart des structures de données, la manière dont nous pensons à elles est loin différent de la manière elles sont mises en application dans l'ordinateur. En d'autres termes, la représentation physique est beaucoup différente de celle de la représentation logique, particulièrement en structures de données qui emploient des indicateurs.

La structure de données linéaire la plus commune utilisée est la liste. À ce jour vous êtes déjà joli au courant de l'idée d'une liste et au moins d'un one-way de représenter une liste dans l'ordinateur. Maintenant nous allons regarder un genre particulier de liste : une liste commandée. Les listes commandées sont très semblables à la liste alphabétique de noms des employés pour la compagnie d'ABC. Ces listes maintiennent des articles dans un ordre spécifique tel que l'ordre alphabétique ou numérique. Toutes les fois qu'un article est ajouté à la liste, il est placé dans la position assortie correcte de sorte que la liste entière soit toujours assortie.

Avant que nous considérions comment mettre en application une telle liste, nous devons considérer la vue abstraite d'une liste commandée. Puisque l'idée d'une vue abstraite d'une liste peut être peu une embrouillante, pensons à un exemple plus familier. Considérer la vue abstraite d'une télévision. Indépendamment de qui fait une télévision, nous tous nous attendons à certaines choses de base comme la capacité de changer des canaux et d'ajuster le volume. Tant que ces opérations sont disponibles et la TV montre les expositions que nous voulons regarder, nous vraiment ne nous inquiétons pas de qui a fait la TV ou de la façon dont ils a choisi de la construire. Les circuits à l'intérieur de l'ensemble de TV peuvent être très différents d'une marque même chose à la prochaine, mais de fonctionnalité des restes. De même, quand nous considérons la vue abstraite d'une liste commandée, nous ne nous inquiétons pas des détails de l'exécution. Nous sommes seulement concernés par ce que la liste fait, pas comment elle le fait.

Supposer que nous voulons une liste qui peut tenir le groupe suivant de nombres assortis : [2 4 6 7]. Quelles sont quelques choses que nous pourrions vouloir pour faire avec notre liste ? Bien, puisque notre liste est en règle, nous aurons besoin d'une certaine manière d'ajouter des nombres à la liste dans l'endroit approprié, et nous aurons besoin d'une certaine manière de supprimer des nombres que nous ne voulons pas de la liste. Pour représenter ces opérations, nous emploierons la notation suivante :

Chaque opération a le nom et la liste de paramètres les besoins d'opération. La liste de paramètre pour l'opération d'AddListItem inclut une liste et un article. L'opération de RemoveListItem est très semblable excepté ce temps où nous indiquerons l'article nous voulons enlever. Ces opérations font partie de la vue abstraite d'une liste commandée. Sont elles ce que nous comptons de n'importe quelle liste commandée indépendamment de la façon dont elle est mise en application dans la mémoire d'ordinateur.

Une approche à créer une liste est simplement de réserver un bloc de cellules de mémoire adjacentes assez à grand pour tenir la liste entière. Un tel bloc de mémoire s'appelle en tant que rangée. Naturellement, puisque nous voulons ajouter des articles à notre liste, nous devons réserver plus que juste quatre cellules de mémoire. Pour maintenant, nous rendrons notre rangée assez grande pour tenir pas moins de six nombres.

Une deuxième approche à créer une liste est de lier des groupes de cellules de mémoire employant ensemble les indicateurs. Chaque groupe de cellules de mémoire s'appelle comme noeud. Avec cette exécution chaque noeud contient la donnée élémentaire et l'indicateur au prochain article dans la liste. Vous pouvez décrire cette structure pendant qu'une chaîne des noeuds liait ensemble par les indicateurs. Tant que nous savons où la chaîne commence, nous pouvons suivre les liens pour atteindre n'importe quel article dans la liste. Souvent cette structure s'appelle comme une liste liée.

Noter que la dernière cellule de mémoire dans notre chaîne contient le symbole appelé « nul ». Ce symbole est une valeur spéciale qui nous indique que nous avons atteint la fin de notre liste. Vous pouvez penser que ce symbole comme indicateur ce se dirige à rien. Puisque nous employons les indicateurs pour mettre en application notre liste, les opérations AddListItem et le RemoveListItem de liste fonctionneront différemment qu'elles ont fait pour les listes séquentielles.