4. List

The basic List is a data structure having a number of items stored in the order that they were originally added. The 'List' can be allocated a fixed length - in which case it is a 'static data structure' on the other hand, if the list is allowed to grow or shrink then it is a 'dynamic data structure'.

An example of a simple list is the 'array' which can hold a number of data items or 'elements' as they are sometimes called. If the array is defined at compile time, then it is a 'static array'. If the array is allowed to vary in length then that is an example of a dynamic list.

A 'linked list' is one where each data item points to its neighbours.

A linked list is excellent as a general storage structure because it is simple to insert and delete items and to find the first and last item.

The Linked List

Although the standard list will add items in the order they were provided, a slightly more complicated list can be maintained such as an alphabetically ordered list. In this case, when an item is added, the list is scanned to find the correct location for the item before it is inserted.

For example a LIST might look like this

A list example
horse
cat
dog
mouse
zebra

Typical operations that can be carried out on a list are:

ADD (or INSERT)	Adds an item to the list
DELETE (or REMOVE)	Removes an item from the list
FIRST	Identifies the first item in the list
NEXT	Identifies the next item in the list
LAST	Identifies the end of the list
LOCATE	Identifies the location of a specific item within the list

Each of these operations have to be written as a 'function' or 'method' that act upon the list.

Challenge see if you can find out one extra fact on this topic that we haven't already told you

Click on this link: The Linked List