Linked lists and scavenger hunts

This post is the fourth of a series adapted from my conference talk, Fun, Friendly Computer Science.

Growing up, my mom always made Easter egg scavenger hunts for me. She would write out clues and riddles that would lead me to the next clue and the next clue until the final clue led me to my Easter basket. One year, that basket contained a long-haired guinea pig who I fell in love with and named Matt (I’ve always had a thing for people names for pets apparently 🤷‍♀️). When you are following a scavenger hunt, you start with the first clue and must follow each clue sequentially one at a time. Because you have no way of knowing where the nth clue is when you start, you must follow the hunt from clue to clue to clue.

A scavenger hunt is a physical representation of a linked list. A linked list is a data structure characterized by sequential data access and no random access. This is unlike arrays. In arrays, because all of the data is stored in contiguous locations in memory, you can do simple addition and subtraction to find the memory location of the data at the nth node. For example, array[3] is just 3 memory locations from array[0]. Linked lists, on the other hand, do not need contiguous memory allocated. Data in a linked list can be stored in any open location in memory and each node in the list points to where the next node is located so you can follow the nodes sequentially.

Because of the memory allocation, a linked list will have no wasted space, because it can grow and shrink dynamically. This is also unlike arrays. Traditionally, an array always needs to be allocated to maximum size because you need to reserve the contiguous space in memory. If the array needs to grow, it is copied to a new array of the required size at a new location in memory. We tend to forget this if we work exclusively with Javascript since JS Arrays behave more like ArrayList (doing the copying to a new array for you automatically).

However, because a linked list node needs to store its data and a reference to the next node, it does take up a bit more space than an array of the same data.

Linked lists have fast insertion at the tail and insertion/deletion at the head (O(1)—see this post if you are unfamiliar with big O notation). But to insert into the middle of a linked list is O(n), less performant, because we need to iterate through the list to the place we want to insert, update the previous node's pointer to the inserted node and update the inserted nodes pointer to the next node.

Being asked to implement a linked list in an interview is common. But it’s not as complicated as it sounds. Let’s look at some pictures and code samples to make it easier (extended code samples can be found on my Github in Javascript, Ruby, and Python).

Adding to a linked list

Adding to a linked list can be done at the head or tail in constant time—O(1). In this code sample, we add at the tail.

add(data) {
  const newNode = new LinkedListNode(data);
  if (this._head === null) {
    this._head = newNode;
  } else {
    this._tail.next = newNode;
  }
  this._tail = newNode;
  return newNode;
}

When adding the first node, when nothing exists in the list yet, we add the node as both the head and the tail of the list.

If nodes already exist in the list, we only worry about the tail node.

When adding additional nodes, we set the next pointer of the current tail node to the new tail node.

And then we update the list’s tail pointer to be the new tail node.

Removing from a linked list

Removing from a linked list can be done at the head in constant time—O(1). Removing from the tail would require iterating through the whole list to be able to update the second to last node’s next pointer to null.

remove() {
  if (this._head === null) return undefined;
  let removed = this._head;
  this._head = this._head.next;
  return removed;
}

When removing from the linked list, we update the new head node to be what was the initial head node’s next pointer.

Inserting into the middle of a linked list

Remember, we said that adding at the head or tail of a linked list is efficient, (O(1)), but inserting into the middle is less so, (O(n)). Let’s look at why that is and why we wouldn’t choose a linked list if we need random access.

insert(data, index) {
  // abbreviated for blog post, removed logic for index < 0 and index === 0
  // else case: index > 0
  else {
    let current = this._head;
    let previous = null;
    let i = 0;
    while (current !== null && i < index) {
      previous = current;
      current = current.next;
      i++;
    }
    if (current !== null) {
      previous.next = newNode;
      newNode.next = current;
    } else if (previous === this._tail) {
      this.add(data);
    }
  }
}

Let’s say that we want to insert a new node into the list at index 2.

We iterate through the list looking for the nodes that are immediately previous to the node at index 2 (previous in the code) and the node that exists at index 2 (current in the code).

We update the previous node’s next pointer to point to the new node.

We update the inserted node’s next pointer to point to the node that was originally at index 2 (current).

I find that pictures help me understand what the code is doing and are easier to remember in an interview situation. If you are asked this interview question, don’t be afraid to draw out the process and code from that 👩🏽‍💻

Linked list uses

You would choose to use a linked list as a data structure when you don’t know the size of your data set ahead of time and you don’t require efficient random access (if you won’t be inserting or reading from the middle of the list). As an example, linked lists are the foundational data structure used for stacks or queues. But in all of these cases, you probably would never implement your own linked list. Almost every language already has a library or package with an efficient and performant implementation of a linked list so you don’t need to reinvent the wheel.