Problems with a regular list

One disadvantage of using a static array variable to store data is that its size cannot be easily adjusted according to the amount of data.

Furthermore, if you want to store a list of data items in a particular order, but they do not arrive in that order, then inserting a new item in the correct place would probably involve moving other items around; an expensive operation in terms of processing.  Removing items from the list would also involve some movement.

Linked list to the rescue

A linked list overcomes some of the problems associated with array variables.

A linked list is a dynamic data structure that consists of a linear collection of data items known as nodes.  Each node includes a pointer to the next node.  The order of the pointers represents the inherent sequence of data items.

A linked list allows for efficient insertion or deletion of elements from any position in the implied sequence.

Uses of linked lists

Linked lists have a range of applications including:

• Undo functionality
• Browser cache
• Polynomial addition
• Prioritised job queues

Linked lists are also often used to Implement other data structures like stacks, trees, queues and graphs.

Representing a linked list

A linked list can be represented for implementation purposes using two one dimensional array variables.  One array to store the data items in the order that they arrive, and one array to store the pointers which indicate the correct order of the data.  An extra pair of variables can also be used to track the start of the list and the next free position.