Data Structures & Algorithms: Linked Lists
- This article assumes some familiarity with Big O notation, objects & pointers, and JavaScript syntax
What is a Linked List?
A Linked List is pretty much exactly as the name suggests: a series of objects called nodes that each point to the next node in the list, “linking” all of them together.
There are a few variations of Linked Lists, but the most basic is a Singly Linked List, in which each node contains two properties, a value and a next pointer.
- The value property can contain anything–a primitive (string, number, boolean, etc.), object or array, or even another Linked List if you want to go full inception!
- The next property is simply a pointer for the very next node in the Linked List (or NULL if it is the last node in the list).
The first node in a Linked List is called the head, while the last node is called the tail.
Comparison to Arrays
If you have any familiarity with other data structures, you might be thinking that Linked Lists just sound like cumbersome arrays! Why should each node need to keep track of the next one when arrays already offer constant time access to every item, provided we know the index? Let’s highlight a few of the main differences between the two.
While it is possible to splice elements into and out of arrays, it comes with the linear time (O(n)) overhead of having to shift every following element either down to the next available index (splice into), or up to the earliest available index (splice out of). This isn’t ideal if you are working with large arrays or if you’ll be doing these sorts of operations often.
With a Linked List, we can create a new node and update the appropriate pointers to insert it where we choose (provided we already have access to the previous node).
Similarly, deleting a node is as simple as updating the previous node’s next pointer to “skip over” the node-to-delete, losing reference to it. This gives us constant time insertion and deletion!
Linked Lists do, however, give up the ability to access items by index. Linked Lists typically only keep track of the head and the tail, requiring each node to point to the next node in the list. Therefore, the inner nodes of a Linked List can be a bit of a black box until we traverse them (ex. retrieving the 50th node of the Linked List requires us to start at the head and follow next pointer 50 times).
It is also significantly easier to shuffle & sort arrays since Linked Lists introduce the complexity of manually updating pointers.
Doubly Linked List
A Doubly Linked List is identical to a Singly Linked List except that each node also contains a previous pointer, allowing each node to be aware of both the node before it and after it.
While the actual process of deleting a node is constant, we must know the previous node. In a Singly Linked List, we must search for the node whose next property points to the node we want to delete–search is a linear operation. A Doubly Linked List gives us constant time access to all three nodes (previous, current, next) so long as we have the current.
When To Use a Linked List
Here’s a quick breakdown of the runtime complexities of common Linked List interactions:
- Access (retrieving the n-th node): Linear — O(n)
- Search (retrieving a specified node): Linear — O(n)
- Insertion (adding a node to the list): Constant — O(1)
- Deletion (removing a specified node): Constant — O(1)
A Linked List can make a great solution if insertion and deletion will be heavily utilized.
Doubly Linked Lists are ideal if you will be deleting from the middle of the list or traversing in reverse order.
In JavaScript (ES6)
ListNode: This defines each node in the Linked List. A simple object containing a value and a next pointer.
constructor(): The constructor function initializes both the head & tail as NULL, as the list begins empty.
addToTail(): we need to create a new ListNode, and then either add this new node to the current tail (if the list is not empty), or pointing the head to this node. Either way, we will point the tail to this new node. Time Complexity: O(1)
removeFromHead(): We need to handle a few edge cases. If the list is empty, there is no node to remove and we can just return NULL. If there is only one node in the list, both the head and tail are pointing to it, so both will need to point to NULL to remove it. Otherwise we can just set the head to the second node in the list and return the removed node. Time Complexity: O(1)
contains(): This method demonstrates how to traverse the list. Each iteration of our loop first checks to see if the current node contains the target value. If not, then we must move to the very next node in the list. The node will eventually equal NULL (falsey) if we do not return early, and our loop will break. Time Complexity: O(n)
— Algorithmic Challenges —
Before reading further in this section, I would suggest taking some time to implement this data structure yourself. Be very comfortable traversing Linked Lists and removing/inserting nodes as many challenges will require these actions to be used in novel ways.
I’ve tried to pick questions that exemplify a type of common solution. If you are ever stuck on where to start in an interview setting, run through this list of techniques to see if one begins to shed light on a performant, elegant solution.
Note: Rarely are you given the full data structure in interviews. Likely, you will be asked to interact with a Linked List given only a single node (often the head). This is the same format that you will find most coding challenge sites implement. I will link each title to the leetcode implementation of the below questions and encourage you to try them for yourself before reading on.
[ Reverse a Singly Linked List ]
Reverse a Singly Linked List — LeetCode
Instructions: “Reverse a Singly Linked List”
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULLTECHNIQUE: UPDATE WHILE TRAVERSING
There are several possible solutions to this problem where the sub-problems of traversing and reversing are broken up, but they tend to come at the cost of more space being utilized.
By holding onto three nodes at once, we can update each node’s next pointer as we traverse the list. With each iteration of our loop, we will only be concerned with updating the curr.next pointer but we will need the previous node (prev) so that we know just where to point curr.next.
To make sure that we don’t lose reference to the next node once we update curr.next, we’ll also put curr.next in the variable next before updating the current node.
This technique is purely an exercise in pointers & logic and, while it can be tricky to remember the proper update order for each variable, I have found that it is quite intuitive to draw and check to see when each pointer can be updated. You will physically see if a node becomes orphaned at any point because your diagram will reveal a node with nothing pointing to it.
Our while loop requires that we traverse all n nodes once, so the time complexity is linear O(n). Since we cannot complete the problem without visiting each node at least once to update its next pointer, it is impossible to improve this. We are only ever using three variables, regardless of the number of nodes in the Linked List, therefore the space complexity is constant O(1) and cannot be improved.
Time Complexity: O(n) | Space Complexity: O(1)
Similar problems:
[ Detect a Cycle ]
Instructions: “Given a linked list, determine if it has a cycle in it.”
Input: 3->2->0->-4->[2->0...]
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the second node.TECHNIQUE: MULTIPLE TRAVERSALS AT DIFFERING SPEEDS
While there are a few solutions to help keep track of what you’ve already seen, none are as elegant and performant as the tortoise & hare approach–which will show up in several algorithmic challenges involving Linked Lists.
By having one pointer move “slowly” through the list (one node at a time) and a second pointer traverse the list at a “fast” speed (two nodes at a time), the fast one will inevitably catch up to the slow pointer if a cycle exists–like two runners on a track.
If the two pointers are ever equal, we are in a cycle and can confidently return true. If there is no cycle, the fast pointer will eventually reach the end of the list, we will break out of our while loop and return false.
Time Complexity: O(n) | Space Complexity: O(1)
Similar problems:
[ Swap Nodes In Pairs ]
Instructions: “Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list’s nodes, only nodes itself may be changed.”
Given 1->2->3->4->NULL, return the list as 2->1->4->3->NULL.TECHNIQUE: TRAVERSE RECURSIVELY
As with most every recursive problem, there are iterative solutions to this problem. I mostly want to shed light on the fact that Linked List traversal does not immediately demand a loop. And that there are cases where making use of the implicit call stack can offer elegant solutions to otherwise manual and cumbersome problems.
Recursive problems can be difficult to explain without visual aid, so I’ll be referencing the below diagram to step through the code.
The top of the diagram represents the Linked List that we are operating on: 987–>76–>670–>-291–>NULL. The containers below it represent various states of the call stack, with each stack frame showing information relevant to our algorithm–the value of shouldSwap, the current stack frame’s node, and that each node’s next pointer is waiting to receive the return value from the next recursive case.
Our diagram picks up when we reach our base case–the current node.next is NULL (the tail) [1]. We handle this by returning the current node, popping this stack frame from the call stack [2]. The previous stack frame’s node.next was waiting on this return value and we can now continue through the body of our function. Because shouldSwap is true in this stack frame [3], we will swap the current node (first) and the next node (second) before returning the second node and popping off the call stack [4]. This exact process will continue until the call stack is clear, ensuring that we have swapped every node in pairs.
It’s important to note that, while recursive implementations can produce elegant solutions, the stack frames produced are not free and contribute to the overall space complexity of your algorithm. Additionally, the call stack has a limit and large enough Linked Lists can cause stack overflow. A common follow up question to any algorithm is how you would change your your answer if you were working with such a magnitude of data. If you have implemented a recursive solution, the interviewer is probably hinting towards refactoring to an iterative solution.
Time Complexity: O(n) | Space Complexity: O(n)
[ LRU Cache ]
Instructions: “Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value of the key if the key exists in the cache, otherwise return -1.put(key, value) - Set or insert the value if the key is not already present.
When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. Could you do both operations in O(1) time complexity?”
LRUCache cache = new LRUCache( 2 /* capacity */ );cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
TECHNIQUE: IMPLEMENT DOUBLY LINKED LIST
This might feel like a lot, but let’s break down the requirements of the challenge to find suitable solutions for each subproblem.
- We know that we want to be able to get values from our cache given a key in constant time. Hopefully this brings to mind a hash table as they are made specifically to handle the storage and retrieval of data via key/value pairs in constant time.
- We also need to be able to delete the least recently used item in our storage when we reach maximum capacity–also in constant time. This means a few things:
- We want to insert new data in such a way that provides reliable, constant-time access the oldest item.
- Every time we get an item from our cache, we need to move it to be the most recently used.
- We often need to delete the oldest item.
We now have the primary actions of our data structure: delete, insert, and move (essentially delete & re-insert) elements in constant time. A Doubly Linked List is perfect for all of these things!
One solution to this problem is essentially to wrap a Doubly Linked List in a storage dictionary.
I find it easiest to think through the logic of the cache and just pretend that we have a Doubly Linked List class available to us. This will reveal all of the methods our Double Linked List will need to expose to us in order to complete the challenge.
Line 6 makes the Doubly Linked List available to our cache. It will handle all of the sub-problems of moving, inserting, and deleting nodes.
Line 9 will keep track of the cache’s capacity. This will tell us when we need to start ejecting the least recently used.
Line 13 is a simple storage object so that we can reference each ListNode in constant time given key.
The get method is responsible solely for retrieving the node from our storage object. Assuming it exists, we will need our underlying list to move this node to the tail (where we will keep our most recently used). We will need to later create the method moveToTail when implementing our Doubly Linked List.
The put method needs to handle a bit more logic than get.
- If the key already exists in our storage object, update that ListNode and exit the function.
- If our cache is not yet at capacity; add the node to the tail of the linked list (most recently used position), add the new ListNode to the storage object, update the capacity, and exit the function. Our list will need an addToTail method.
- We must eject the least recently used if neither of the above are true. Since we’re keeping the least recently used node at the head of the list, we can use a simple removeFromHead method to remove it from the list. We must also delete the node from our storage object.
- We can finally add a new node to the tail (most recently used position) and our storage object.
Great! Now that our LRUCache is built, we can work backwards to ensure that our DoublyLinkedList provides the necessary methods.
The code is heavily commented, so I will aim to just highlight a few key points and explain the purpose of the methods I have added.
The head of our list will point to the least recently used node in our cache. Removing the least recently used node is a key part of this challenge, so the removeFromHead method can easily handle that for us.
The tail of our list will point to the most recently used node in our cache. When adding a new node to our cache, we will want it to take the spot of most recently used and a simple implementation of addToTail can handle this well.
Every time we get a node from our cache, we will need to pluck it from wherever it is in the list and move it to the most recently used position (the tail). The method moveToTail essentially deletes the node from the list and reuses the logic of our addToTail method by passing in the node we want to add.
.get() & .put() — Time Complexity: O(1) | Space Complexity: O(1)
LRUCache — Overall Space Complexity: O(k) (where k = capacity)
Conclusion
When working through algorithms involving Linked Lists, it can be helpful to have these techniques on hand as there is a good chance that one of these will be utilized in some way:
- Simple traversal, with enough variables to update while traversing
- Multiple traversals at differing speeds
- Traverse with recursion
- Utilize a Doubly Linked List
You will rarely be asked explicitly to manipulate a given list, but rather to solve an abstract problem in which a particular data structure’s strengths can be utilized (LRUCache is a perfect example). Know the strengths & weaknesses of as many data structures as you can, as well as common manipulation techniques and you will be significantly more prepared for your next interview!
