Linked Lists: What They Are and How They Compare to Arrays

Singly linked lists contain a series of nodes. Each node has a value, as well as information on the location of the next node. The first node in a linked list is called the "head", and the last node is called the "tail".

At first glance, it may seem like linked lists are just more complicated versions of arrays--why would you want to point to another element, when your elements could simply just be sequential? To understand the value of linked lists, it's important to first discuss how memory is stored in a computer.

A computer's memory (a.k.a. Random Access Memory, or RAM), contains billions of numbered addresses. At various points, your computer could look up the information stored at address number 1002, for example, or address number 620,059. The information stored at each address is called a "byte".

Arrays store information sequentially in memory. Let's say you have an array, ["a", "b", "c", "d"]. It may be stored in memory like the following, located at the addresses at 500, 501, 502, and 503.

In some cases, this works well. If your array will never get longer than this, then there are advantages to this approach. For example, if you're told to find the element at the second index this array, you could quickly do something like array[2]. Things get tricky, however, if you want to add an element to this array.

Let's say you want to append "e" to the array. If the memory at address 504 is available, then you'd have no problem. However, if there's already something in 504, the whole array would have to move, element by element, to elsewhere in the memory where there would be enough space for a five-element array. This takes times, and in Big O notation it can take up to linear time (O(n)) to append to an array (though it's important to note it can be constant, if there is space in memory).

Now, let's contrast that with linked lists. The nodes in a linked list don't have to be anywhere near each other, or even in sequential order.

To append an item to a linked list, all you have to do is create a new node (which has a value and a pointer to the next node), and have the previous tail point to the new node. The new node now becomes the tail.

The run time for appending to a linked list is constant (O(1)), which means it's faster than arrays.

Prepending is also faster for linked lists than arrays. To prepend to a linked list, you simply create a new node, and have it point to the node that was previously the head. Now, it becomes the new head.

To prepend to an array, even if there is space in memory, you always need to move every item in the array one index over. The Big O for linked list prepending is always constant (O(1)), whereas the Big O for array prepending is always linear (O(n)).

As alluded to earlier, the downside of linked lists comes in the form of lookup. If you were told to find the 20th node in a linked list, you would have to go through all 19 elements before it in order to find it. Lookups with linked lists are therefore always slower than they are for arrays.

If you are working with a dataset of any size, appending and prepending is much faster when using linked lists. If quick lookup is something you'll need, arrays may be a better bet.

Comments

[Duy K. Bui]

I was just browsing through your posts and saw this and the reversing array ones and thought to myself reversing a linked list would make an interesting recursion example.

Usually when seasoned devs introduce recursion to a newcomer dev, we use an example something like

function recurseMe(prettyPlease) {
  do something
  return early if one of the final conditions reached
  return recurseMe(prettyPrettyPlease)
}

In this case though, it will be a bit different, as in

function reverseLink(node) {
  if (!node.next) return node; // old tail reached, return as new head
  reverseLink(node.next); // recurse first
  node.next.next = node; // then reverse link
}
// then to actually reverse a list
const newTail = oldHead;
const newHead = reverseLink(oldHead);