I noticed a few months back, several posts on LinkedIn and Twitter where people are saying things like “what’s the point of a linked list?”, “do I need linked lists?” etc.

The answer, like in many cases, to these sorts of questions are “it depends”.

What is a linked list?

A singularly linked list is a container structure where you usually maintain a HEAD link and from that you have a pointer/reference to a NEXT link in the list, each link points to a NEXT link OR a NULL. The NULL simply indicates there are no more links.

Let’s create a really simple example of this in C#. This will act list a Queue, hence we’ll put to the end of the list and get from the front of the list, i.e. FIFO (First In First Out). It should be pretty obvious how it can be written in most other languages

class Link<T>
{
   public Link<T>(T data)
   {
      Data = data;
   }
  
   public T Data { get; }
   public Link<T> Next { get; set; }
}

class Queue<T>
{
   private Link<T> _head;
   private Link<T> _tail;
 
   public void Put(T data)
   {
      if(_head == null)
      {
         _head = _tail = new Link<T>(data);
      }
      else
      {
         _tail.Next = new Link<T>(data);
         _tail = _tail.Next;
      }
   }

   public T Get()
   {
      if(_head != null) 
      {
         var data = _head.Data;
         _head = _head.Next;
         return data;
      }
      return default(T);
   }
}

In the code above we’ve added a little optimization by including a TAIL link, which just allows us to add to the end of the linked list without having to iterate of the links each time, but otherwise it’s about as simple as it gets.

What are the problems with Linked Lists?

So immediately from the fairly trivial example we can see a few issues with this type of container. The most obvious is the lack of direct indexing, i.e. we cannot just peek or get the third item in a O(1) time complexity. Instead, we must go to the HEAD and iterate to the third item via the NEXT links. Ofcourse, an array would have far better performance than a Linked List in such situations.

With a linked list, we are (potentially) going to end up, with quite a bit of memory fragmentation as each link can be stored anywhere in memory. So, that’s another downside of using a linked list.

I suppose one might find the implementation complex compared to just creating an array, although once implemented and fully tested that’s probably not a concern. What might be more concerned with is that for each item in memory we have to store a link to the next item.

But let’s be honest the main issue people would have with a linked list is performance especially compared to an array.

So, what’s the point of a linked list when we could just use an array?

Way back, when I learned to use linked lists, I was using C++ on 8088 processors and we had very little memory available. Now, whilst each link in a linked list does have this overheard of a NEXT link, a link list can grow in a way that an array cannot.

Let’s assume we have an array of 1000 items and we want to add one more item. Then we need to create a new array buffer the size of the previous buffer + 1 and then copy all the items from the old to the new buffer then add our new item to the next extended buffer then free the original array buffer.

This means we have two arrays in memory, one with a size of 1000 items and another with 1001 items being held in memory whilst we do the copy. When memory is scarce or heavily fragmented, there’s the potential of an Out of Memory exception as an array would need a block of memory that’s contiguous and hence indexable. Along with the fact that this will end up being slow, creating a new array every time we add an item and copying.

The first thing the reader might say is – well instead of creating a new array with 1 extra item, meaning we have to create a new allocation for every item added, let’s instead create an array with more memory than we currently need, so we might then create an array with a delta (a value that says, when I create a new buffer it will always be old buffer length + delta) where delta might be a value such as 100. Now, we only need to allocate more memory every 100 times we add an item. In other words in our example, instead of creating a 1001 buffer we create a 1100 and simply track length as being 1001 but buffer size being 1100, hence we do not need to allocate more memory until the developer reaches the 1100 and wants to add an item.

This reduces memory allocation, but we still have the issues around maintaining two buffers in memory whilst we copy from one to another and, again, on systems with smaller amounts of memory such as microprocessors and still has the potential of Out of Memory exceptions due to this copy process and/or fragmentation.

Conclusion

So, in today’s modern desktop, laptops and even phones, we probably do not care about the extra issues around creating arrays and resizing them because we have plenty of memory and with some languages using garbage collection with heap defragmentation because we’ve memory to spare and the O(1) indexing is far more important to us, but if you’re using a microprocessor/microcontroller where memory is a premium linked lists still make a lot of sense. Ofcourse you will lose out on O(1) indexing but everything is a trade-off where memory is at a premium.