Operations on a simply linked list

Version 1.5 1997
Authors : Jean-Yves Daunay, David Passani Supervisors : Richard Bonnaire, Hélène Perrin
 

Representation

Colored disks with an arrow represents pointers. The blue rectangles are the various components of the linked list (elements). In these elements are two fields. In the first one is a character, the information contained in the element. The second field is a pointer to the next element.
The code shown in the window use a C structure for the element :
typedef struct element {char information; element * suivant;}
Index Animation

Description of the animation

A randomly generated linked list is shown. It contains either four, one or no element (empty list). It is possible to obtain another list by pushing the "RESET" button.
The user has to enter a character in the text input zone

Deleting an element

The first step is the localization of the character in the list. A yellow pointer is put at the head of the list. If the head pointer is NULL, the list is empty so it is not possible to delete anything. If not, the yellow pointer is placed on the first element and the red pointer receive the value of the "head" pointer.
If the yellow pointer points to an element containing the information to delete, the search is done. Otherwise the yellow and the red pointers are moved respectively to the next element.
Again, if the yellow pointer is on a element containing the character, the search is done and the red and yellow pointers are correctly set for the deleting step, otherwise the search goes on until the character is found or the end of the list is reached.
As soon as the yellow pointer points to the element containing the character the first step is ended..

Second step : deletion.
It can be divided in three steps :

Insertion process

Before clicking the ADD button, it is possible to choose the position at which the new element will be placed. The choice is done by clicking on one of the four checking boxes under the ADD button.
According to the number of elements in the list, various insertion position are permitted. For example, if the list is empty, the new element can only be inserted in the first position and so the other three checking boxes are de-activated etc.
There is two different case for inserting an element : Index Animation

Controls

Index Animation

Remarks

At any time it is possible to change from the stepwise mode to the continuous mode but it is not possible to interrupt the continuous mode.

In the list the characters are always in capital letters but it is not necessary to enter them in capital, the conversion will be automatic.

During the search for the element to delete, if it occurs in several elements of the list ( for example in the list P A P A), only the first occurrence will be deleted.

By clicking on a component of the application, an help message indicates the nature of the component. This is only possible in the continuous mode.

For graphical reasons, the linked list is restricted to four elements.

The "head" pointer is a global variable, always pointing to the first element of the list. It is updated according to the changes of the linked list. It is always necessary to know the head of the linked list, otherwise data will be lost.

In the insertion of a new element in the list, it is supposed that the chosen position is correct (if the list contains only one element it is impossible to ask for an insertion in the fourth position).
Index Animation

Conclusion

This application enables to visualize the main operations on a linked list. The number of elements has been restricted to four due to the graphic characteristics of the application but in "real size" linked list the number of elements is only limited by the amount of available memory. it is also possible to have more fields in the structure of an element.
For example it is possible to easily represent planes queuing before landing. The "plane" element would contain the flight identifier, the destination, the starting point, the remaining flight duration and planes before and behind it. With the parameter remaining flight duration it is possible to set up landing priorities and the to move the plane to the head or the end of the queue by insertion and deletion.
Index Animation 
bonnaire@ccr.jussieu.fr