What Are Linked Lists?
A singly linked list is a data structure which represents a series of nodes where each node points to the next node in the list. A doubly linked list, in contrast, has nodes which point to the element preceding and following it.
Unlike an array, a linked list doesn’t provide constant-time access to specific indices within the list. So if you need the third element in the list, you have to iterate past the first and second nodes to reach it.
One benefit of a linked list is the ability to add and remove items from the beginning and end of the list in constant time.
These are popular data structures to be questioned about during a technical interviews, so let’s jump right in.
A singly-linked list may be LIFO (last-in-first-out) or FIFO (first-in-first-out). If the list is using the LIFO method, the nodes will be added to and deleted from the same end. If it’s using FIFO, nodes will be added to one end and deleted from the opposite end.
Additionally, the linked list may be sorted. This means that as each node is added to the list, it’s placed into its appropriate spot relative to the other nodes.
Node
A linked list is just a series of nodes, so let’s start with our Node object.
A node has two pieces of information:
- A pointer, or reference, to the next item in the list (for a singly linked list)
- The value of the node
For our node, we’ll just create a function which takes a value, and returns an object with the two values above: a pointer to the next node and the value of the node. Note that we’re able to just declare value instead of value: value. This is because the variables have the same name. You can learn more about the object property shorthand here.
function Node(value) {
return {
value,
next: null
}
}
NodeList
Now, let’s delve into the NodeList class. This is just that: a list of nodes.
Our node list will contain five methods:
-
push(value): Pushes a value on to the end of the linked list -
pop(): Pops off the last value from the list -
get(index): Returns an item from a given index -
delete(index): Deletes an item from a given index -
isEmpty(): Returns a boolean indicating whether the list is empty -
printList(): A method, not native to linked lists, which will print out our list; it’s primarily for debugging purposes
Constructor
I’m going to be using JavaScript class syntax, although you could also use a closure to create a linked list. So let’s set up the constructor.
We’ll need three pieces of information in our constructor:
- head: A reference to the node at the beginning of the list
- tail: A reference to the node at the end of the list
- length: How many nodes are in the list
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
IsEmpty
The isEmpty() method is a helper function which returns true if the list is empty.
isEmpty() {
return this.length === 0;
}
printList
This utility method will print the nodes in the list. This is solely meant for debugging purposes.
printList () {
const nodes = [];
let current = this.head;
while (current) {
nodes.push(current.value);
current = current.next;
}
return nodes.join(' -> ');
}
Push
Our push method needs to check whether the list is empty or not before adding a new node. How do we know if the list is empty? Two ways:
- Our
isEmpty()method returns true (the length of the list is zero) - The head pointer is null
For this example, we’ll check whether head is null, although either solution works fine.
If there are no items in the list, we can simply set both the head and tail pointers to the new node and update the length of the list.
if (this.head === null) {
this.head = node;
this.tail = node;
this.length++;
return node;
}
If the list isn’t empty, we have to do the following:
- Set
tail.nextto point to the new node - Set
tailto point to the new node - Increment the list length
Here is our completed push method:
push(value) {
const node = Node(value);
// The list is empty
if (this.head === null) {
this.head = node;
this.tail = node;
this.length++;
return node;
}
this.tail.next = node;
this.tail = node;
this.length++;
}
Pop
Our pop method needs check the following two things before removing the last item in the list:
- Check whether the list is empty
- Check whether there is only one item in the list
We can use our isEmpty method to check whether a list contains nodes.
if (this.isEmpty()) {
return null;
}
How do we know if there’s only one node in the list? If head and tail are pointing to the same node. But what do we need to do in this instance? Removing the only node means we’re essentially resetting the list.
if (this.head === this.tail) {
this.head = null;
this.tail = null;
this.length--;
return nodeToRemove;
}
If there is more than one element in the list, we can do the following:
while there are nodes in the list
if the next node in the list is the tail
update tail to point to the current node
set the current node to point to null
decrement the length of the list
return the previous tail element
It will look something like this:
let currentNode = this.head;
let secondToLastNode;
// Start at the front and iterate until
// we find the second to last node
while (currentNode) {
if (currentNode.next === this.tail) {
// Move the pointer for the second to last node
secondToLastNode = currentNode;
break;
}
currentNode = currentNode.next;
}
// Pop off that node
secondToLastNode.next = null;
// Move the tail to the second to last node
this.tail = secondToLastNode;
this.length--;
// Initialized to this.tail
return nodeToRemove;
If you’re having trouble visualizing this, let’s walk through it.
Lines 6–10: If the next node in the list is the last item, this current item is the new “tail” so we need to save it’s reference.
if (currentNode.next === this.tail) {
secondToLastNode = currentNode;
}
Line 15: Update secondToLastNode to point to null. This is the act of “popping” off the last element from the list.
secondToLastNode.next = null;
Line 16: Update tail to point to secondToLastNode.
this.tail = secondToLastNode;
Line 17: Decrement the length of the list because we just removed a node.
Line 18: Return the node we just popped off.
Here’s our full pop method:
pop() {
if (this.isEmpty()) {
return null;
}
const nodeToRemove = this.tail;
// There's only one node!
if (this.head === this.tail) {
this.head = null;
this.tail = null;
this.length--;
return nodeToRemove;
}
let currentNode = this.head;
let secondToLastNode;
// Start at the front and iterate until
// we find the second to last node
while (currentNode) {
if (currentNode.next === this.tail) {
// Move the pointer for the second to last node
secondToLastNode = currentNode;
break;
}
currentNode = currentNode.next;
}
// Pop off that node
secondToLastNode.next = null;
// Move the tail to the second to last node
this.tail = secondToLastNode;
this.length--;
// Initialized to this.tail
return nodeToRemove;
}
Get
Our get method must check for three situations:
- The index requested is outside the bounds of the list
- The list is empty
- We’re requesting the first element
If the requested index doesn’t exist within the list, return null.
// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
return null;
}
If the list is empty, return null. You can combine these if statements, but to keep it clear, I separated them.
if (this.isEmpty()) {
return null;
}
If we’re requesting the first element, return the head.
// We're at the head!
if (index === 0 ) {
return this.head;
}
Otherwise, we just iterate through the list one by one until we find the index we’re looking for.
let current = this.head;
let iterator = 0;
while (iterator < index) {
iterator++;
current = current.next;
}
return current;
Here is the full get(index) method:
get(index) {
// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
return null;
}
if (this.isEmpty()) {
return null;
}
// We're at the head!
if (index === 0 ) {
return this.head;
}
let current = this.head;
let iterator = 0;
while (iterator < index) {
iterator++;
current = current.next;
}
return current;
}
Delete
Our delete method will also have to account for three special use cases:
- The index we want to delete is outside the bounds of the list
- The list is empty
- We want to delete the head
If the index we want to delete doesn’t exist within the list, return null.
// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
return null;
}
If the list is empty, return null. You could combine this logic with the logic to determine whether the index is outside the bounds of the list, but for clarity’s sake I have kept them separate.
if (this.isEmpty()) {
return null;
}
If we want to delete the head, set head to the next value in the list, decrement the length, and return the value we just deleted.
if (index === 0) {
const nodeToDelete = this.head;
this.head = this.head.next;
this.length--;
return nodeToDelete;
}
If none of these booleans are true, the logic for deleting a node is as follows:
while the iterator isn't the index we're looking for
increase the iterator
move the previous and current pointers up by one
save the current value as the node to be deleted
update the previous node's pointer to point to the next node
if the next value is null
set tail to the new last node
decrement list length
return the deleted node
If you need help visualizing this, please refer to the diagram found in the Pop section.
The difference between the delete method and the pop method is that the pop method will always delete the last item in the list. In contrast, the delete method can delete an index between 0 and the length of the list.
Here is the completed delete method:
delete(index) {
// Index is outside the bounds of the list
if (index < 0 || index > this.length - 1) {
return null;
}
if (this.isEmpty()) {
return null;
}
if (index === 0) {
const nodeToDelete = this.head;
this.head = this.head.next;
this.length--;
return nodeToDelete;
}
let current = this.head;
let previous;
let iterator = 0;
while (iterator < index) {
iterator++;
previous = current;
current = current.next;
}
const nodeToDelete = current;
// Re-direct pointer to skip the element we're deleting
previous.next = current.next;
// We're at the end
if(previous.next === null) {
this.tail = previous;
}
this.length--;
return nodeToDelete;
}
If you’d like to play around with the code, feel free to fork my CodePen.
Top comments (6)
If you define push/pop to work on the front of the list you can have an effective stack. One that both push and pop can be implemented in constant time.
Interestingly, as it might come up in an interview, you can do this even if you want to define it as the back. Internally you'll be storing the list in reverse order (or alternately, using a
prevfield rather thannext) The index of get/delete and the order of print, need to be tweaked, but you can get the same result.That is, whether you say push/pop works on the front or back, you can implement it in constant time.
The doubly-linked list lets you have constant time on both ends.
Great post, thanks for sharing.
I want to mention that lists store and manage values not nodes. In fact, the nodes are internals and should not be exported. For example,
popanddeletemethods have to return the stored value not its wrapper.Very educational good job.
you can also get a shortcut for gettting the last Node
That is if i'm not mistaken and the length property can be trusted
I love this. I will try to play with this series this weekend. I have been following on twitter and I really gaining vast knowledge from all your tweets. Worth following you. #keepCoding #keepInspiring. Cheers!
Really great post and series!
One question, should push return something when the list isn't empty or am i missing something?
Thanks! Your graphical illustrations really helped me understand the Push() method!