Linked lists

By Martin McBride, 2018-05-05
Tags: list linked list
Categories: data structures

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

Sign up to the Creative Coding Newletter

Join my newsletter to receive occasional emails when new content is added, using the form below:

Popular tags

555 timer abstract data type abstraction addition algorithm and gate array ascii ascii85 base32 base64 battery binary binary encoding binary search bit block cipher block padding byte canvas colour coming soon computer music condition cryptographic attacks cryptography decomposition decryption deduplication dictionary attack encryption file server flash memory hard drive hashing hexadecimal hmac html image insertion sort ip address key derivation lamp linear search list mac mac address mesh network message authentication code music nand gate network storage none nor gate not gate op-amp or gate pixel private key python quantisation queue raid ram relational operator resources rgb rom search sort sound synthesis ssd star network supercollider svg switch symmetric encryption truth table turtle graphics yenc