What are Linked Lists?

Arrays are a common method of storing lists of data items, where each item is stored in sequence one item directly after another. The problem with storing data in arrays is that it is difficult to insert or remove items.

Say you create an array of characters like this:

[A,B,C,E,F,G,H,I,J]

Now you want to insert D between C and E. How would this be solved? The solution is very inefficient. What would usually be done is:

• Make a new array one element larger
• Copy the items A - C.
• Append D.
• Append a copy of items E - J
• Delete the original array

Some programming languages give the appearance of allowing items to be arbitrarily inserted into an array, but they are actually doing some variation on the above procedure under the hood. The larger the array, the more time consuming this process is. If the array contains many millions of large items, it may take a very noticable amount of time for the array to be copied. If a large number of updates are needed to the array, the situation gets even worse with a huge number of copies of an already large array being required.

A more efficient solution is to use a linked list. The way this works is each data item is stored together with a pointer to the next item in the list (and sometimes the previous one). A pointer is the location of a data item in memory.

Below we have the data item “A” at memory location 0. Immediately after that we have a pointer which explains where we should look next. It says to look in memory location 2. So we jump here and read the the next item in the list which is “B”. Immediately after that we find the pointer to the next item in the list which tells us to look in memory location 4. We move to this location and we read “C” and so on.

A special value is used to indicate when the end of the list is reached. Here we use -1 to mean the end of the list and there are no more pointers, which is at location 17 after the final data item “J”. We can safely use a negative number to represent this special condition because memory locations can only be positive numbers.

The benefit of this system is that we can make insertions into the list without having to copy the entire list.

To insert the missing “D” item, we simply add it to the end and then update the pointer of the preceding “C” item to point to it. So we change the pointer after C to refer to memory location 18. Immediately after the D item, we add a pointer to jump back to the next item in the list, which is “E”.

We can also easily delete items with linked lists. Here we remove the item “G” by simply updating the pointer at “F” to point to “H” instead:

But what if we want to insert before the first item in the list? The way this can be achieved is by storing an extra pointer to where the list itself starts called the “head” pointer.

When we access the list, we refer to the head pointer to find out where the start is. If we need to insert an item right at the beginning of the list, we can just update the head pointer. Here we insert the new item “Z” before “A”.

When using an array, it is easy to navigate in two directions. For example if we want to find the next item in the array we add one to the current array index and to get to the previous item we simply subtract one from the array index. However, using the linked list strategy it’s difficult to go backwards because we only have a pointer to the next item. To solve this we simply add an additional pointer that points to previous item in the array. Now we can navigate the list in two directions.

A disadvantage of the linked list versus an array is that it uses more memory to store all of the pointers. An array is more advantageous if we do not need to add or remove items.