Linked lists

An linked list is a data structure that implements a list. The elements are linked together by memory pointers. Unlike an array list, the elements of the list do not have to be stored in any particular order in memory.

An example linked list

In a linked list, each element of the list is stored in a cell, made up of two values:

• The element's value.
• The address if the next cell in the list.

Starting from the first cell in the list, you can read all the elements by moving from one cell to the next using the memory pointers. Here is the list:

[8, 7, 6, 5, 4]

The last cell in the list contains an null pointer (usually with a value 0) to show that there are no more elements. Notice that because each cell holds a pointer to the next, the cells can be stored anywhere in memory, there is no need for them to be stored next to each other like an array.

Adding an element

Suppose we wanted to add an element, value 3, at index 3, to make the list look like this:

[8, 7, 6, 3, 5, 4]

All the list needs to do is create a new cell with value 3. This can be created anywhere in memory.

The link between cells 3 and 4 is then broken. Cell 3 is altered to point at the new cell. The new cell points at the previous cell 4.

The list now contains 6 elements, in the correct order. The great thing is, there was no need to copy any elements. Al that needed to be done was to modify two memory pointers.

Removing an element

Going back to our original list, suppose we wanted to remove element 1 (value 7) to make the list look like this:

[8, 6, 5, 4]

All the list needs to do is change cell 0, so that instead of pointing to cell 1 it points to cell 2:

Now the list has 4 elements, in the correct order.

The cell containing value 7 is now no longer used. Its memory can be reclaimed to be used again.

Finding an element by index

A weak point of linked lists is that you cannot quickly find an element by index. Suppose you wanted to find the value at index 3. You would need to:

• Start at cell 0, the beginning of the list.
• Follow cell 0's pointer, to cell 1.
• Follow cell 1's pointer, to cell 2.
• Follow cell 2's pointer, to cell 3.
• Read the value of cell 3.

If there were thousands or millions of elements, this could take a while.

Benefits of a linked list

With a linked list, adding and removing elements is very fast. Looping through the elements in order is also very fast.

Finding an element by index can be slow.

See also

• Abstract data types
• Arrays
• Lists
• Array lists
• Static vs dynamic data structures
• Queues
• List based queues
• Circular queues