Basic Interview Data Structures in JavaScript: Linked Lists

Welcome to my follow up article to Basic Interview Data Structures in JavaScript, where I describe the JavaScript implementations of arrays, array lists / vectors, hash maps and hash sets for the use in coding interviews. This article focuses on linked lists.

A linked list is a simple data structure that can be very handy when you need to efficiently insert/remove nodes at any position of the list. To do that efficiently you simply need a pointer to the previous node.

As in my previous article, I will give you the runtime complexity for the data structure:

• Insertion (insert an element): O(1)
• Random access (access any element): O(n)*
• Find (find a specific element): O(n)
• Random removal (remove any element): O(n)

*Fetching the first and last element of a list can actually be done in O(1).

Unlike in Java, there is no default linked list implementation in JavaScript. In practise you would probably use a third party implementation if you needed a linked list. However, in an interview situation this might not be possible. If the implementation of the linked list is not the core of the interview question, you can discuss with your interviewer if you can just pretend there is an implementation and simply use it in your algorithm. In all other cases you need to be able to code up a simple linked list from scratch.
Singly or doubly linked list?
During an interview where you need to code up your linked list yourself you should not use a doubly linked list if not really necessary for the task, because it adds too much complexity to your code. A doubly linked list enables you to delete a node in O(1) instead of O(n) if you have a pointer to that node. Furthermore a doubly linked list allows to efficiently insert a node before some other node while a singly linked list only allows efficient adding after it.
A simple singly linked list
A simple approach for a singly linked list is the following data structure:

const createNode = (data) => ({
 next: null,
 data,
});

It is a simple list node object that contains data as well as a pointer to the next element in the list. But as simple as this data structure might be the complexity comes with the operations.
Insertion
The complexity in both runtime and code depends on where you want to insert an element into the list. It is fairly easy to append an element to the beginning of the list in O(1). If you want to add an element after any node than you can do this in O(1) if you have a pointer to that node. Otherwise you first need to traverse the list to find the node which is only possible in O(n).

const insertAfter = (node, data) => {
 const newNode = createNode(data);
 newNode.next = node.next;
 node.next = newNode;
 return node;
}const insertBefore = (head, data) => {
 const newHead = createNode(data);
 newHead.next = head;
 return newHead;
}// create new list
let head = createNode('one');// insert element after head
insertAfter(head, 'two');// insert to head of list
head = insertBefore(head, 'zero');

Random access
To access an element at any given index in the list you have to start at the head and follow the list until you reached the specified index. This operation has O(n) time complexity.

const getElementAt = (head, index) => {
 let currentIndex = 0;
 let currentNode = head;
 while (currentIndex < index && currentNode !== null) {
 currentIndex++;
 currentNode = currentNode.next;
 }
 return currentNode;
}

Find
Finding a specific element is similar to accessing a random element. The only difference is that you need to compare the data of the current element with the one you are looking for. The runtime complexity of this operation is O(n).

const getElement = (head, data) => {
 let currentNode = head;
 while (currentNode.data !== data && currentNode !== null) {
 currentNode = currentNode.next;
 }
 return currentNode;
}

Random removal
Removing any element from the list is a combination of finding the element and its predecessor and updating the next pointers. This operations also has a runtime complexity of O(n) caused by the find operation.

const remove = (head, data) => {
 if (head.data === data) return head.next; let currentNode = head;
 while (currentNode.next !== null ) {
 if (currentNode.next.data === data) {
 currentNode.next = currentNode.next.next;
 return head;
 }
 currentNode = currentNode.next;
 }
 return head;
}

More sophisticated implementations
The presented implementation is a very simple one that has the advantage of being simple and fast to code up during an interview. However, there are some drawbacks, too. For instance getting the size of the list is only possible in O(n) with this implementation. Of course you could just keep a variable to track the size of the list but this is very error prone. Additionally it can be dangerous if the same list is used in two places within the program and the head of the list changes. While one part of the program might change the head, the other part might not get informed and still points to the old head. So using a wrapper object for the whole list is recommended.
Doubly linked list
If you really need a doubly linked list you need to modify the operations and the data structure a bit.

const createNode = (data) => ({
 next: null,
 previous: null,
 data,
});

Insertion
Not only do we have to update the next pointers of the nodes but now also the previous pointers. It is easy to mess this up and forget to update a pointer during an interview.

const insertAfter = (node, data) => {
 const newNode = createNode(data);
 newNode.next = node.next;
 newNode.previous = node;
 node.next && (node.next.previous = newNode);
 node.next = newNode;
 return node;
}const insertBefore = (node, data) => {
 const newNode = createNode(data);
 newNode.next = node;
 newNode.previous = node.previous;
 node.previous && (node.previous.next = newNode);
 node.previous = newNode;
 return newNode;
}

Random removal
Random removal simply works by finding the element and then updating the pointers of the previous and next element. If we do not need to find the element to remove then this operation is possible in O(1). This was not possible with a singly linked list because finding the previous element takes O(n) there.

const removeNode = (node) => {
 if (!node) return null;
 node.previous && (node.previous.next = node.next);
 node.next && (node.next.previous = node.previous);
 return node;
}
const remove = (head, data) => removeNode(getElement(head, data));

Conclusion
Linked lists are essential for coding interviews. However, clarify with your interviewer if you really need to implement it from scratch. There are coding tasks where it is essential that you recognise to use a linked list but there is no need to implement it. Make sure to know the different operations and their time complexity.

I wish you good luck for your interviews!

WRITTEN BY

Johannes Baum