List

In , one list is one structure of data allowing to gather data so as to be able to reach it freely (contrary to files and with piles, whose access is done respectively in mode FIFO and LIFO). One uses to this end an index which one can place on a particular element of the list.

The principle of the list is that each element to be stored has pointers towards the elements which are logically adjacent for him in the list. So the use of a list is recommended when insertions/removals of elements in any point are relatively more frequent than the simple accesses, for reasons of speed of treatment. Indeed, an insertion or suppression is done in time constant bus requires to the maximum only two accesses in writing. On the other hand, the access to an element by chance positioned request the course of each element which separates the index from the element chosen, it is thus preferable to reach the elements sequentially.

There are several types of lists, characterized mainly by two attributes:

1. chaining
   • list simply chained: the access is done forwards only
   • list doubly chained: the access can be done indifferently forwards or backwards
2. looping
   • list not circular: the last element does not have a reference towards the first element of the list
   • list circular: the last element has a reference towards the first element (if the list is doubly chained, the first element has also a reference towards the last)

A list also has a static reference towards the first element (the chief candidate) which makes it possible to find all the others.

Primitives

One defines a certain number of primitives, which are related to test, access in reading or writing whose list allows an effective execution.

There is not standardization for the primitives of handling of list. Their names are thus indicated in an abstract way. Here the list of most usually used:

• "Placement on the first element": place the index on the first element of the list.
• "Placement on the last element": place the index on the last element of the list.
• "Placement on the following element": place the index on the element which follows the current element if it is possible.
• "Placement on the preceding element": place the index on the element which precedes the current element if it is possible.
• "is List empties? » : Turn over true if the list is empty, false if not.
• "is the element running the first? » : Turn over true if the current element is the first element of the list, forgery if not.
• "is the element running the last? » : Turn over true if the current element is the last element of the list, forgery if not.
• "a Number of element": return the number of elements in the list.
• "To add in tail": add an element after the last element of the list (effective only for one doubly chained list).
• "To add at the head": add an element before the first element of the list.
• "Insertion": insert an element before the current element.
• "Replacement": Replace the current element.
• "Suppression": Remove the current element.

Implementation

In imperative languages like C, the implementation of the lists uses one of the following methods:

• Implementation by contiguity: The elements are in the order in a structure of data moreover low level, like one table, for example.
• Implementation by chaining: The elements contain information (pointers, into C), making it possible to find the following element (simple chaining) or the elements precedent and following (double chaining).

Example of implementation in the PASCAL language (list of entireties):

liste=^jonction type;
     jonction=record
        contents:longint;
        according to:list
     end;

See too

• on Wikipédia.