Working With Linked Lists
Linked lists are data structures that are similar to arrays however they differ in one major way, there are no indices. As a result, you cannot randomly access data within a linked list, instead you must traverse the list if you want to find any one element.
So, why would you ever use a linked list instead of an array? The answer depends on the problem you are working with. If you are dealing with a large dataset where you need to constantly add or remove data from the beginning or end of the data set — like in a stack or queue — then linked lists are your ticket.
Arrays are great because they allow us random access to any element within. However, if we only need to add and remove from the beginning and end of the data, then spending the memory to create indices for every element is a waste.
Additionally, arrays become even more inefficient when we add or remove data from the beginning. If you use shift or unshift then internally the array must re-index every element. Again, this is costly and not need if you are working with a queue or stack data structure.
For a linked list, the Big O complexity is always O(1) when removing from the beginning or end of the list. Well, unless you are popping an element off the end in a singly linked list, but when implemented in a stack structure — there are ways around this.
Potential Uses for Stacks and Queues
A stack is a data structure that follows the LIFO principle or Last In First Out. A queue on the other hand follows the FIFO principle or First In First Out. Examples of each include:
- Stack: Saving your browser history
- Stack: Undo/Redo in a text editor
- Queue: Sending files to a printer
- Queue: Standing in line for anything
So, let’s take a look at a basic implementation of linked list. As alluded to above, linked lists come in two flavors, singly and doubly linked. The two are very similar except for the fact that doubly link lists contain an extra pointer. I’ll begin with singly linked list and then show how they differ from a doubly linked list. Finally, I’ll conclude with how to reverse either as this is a question that comes up often in interview settings and their implementation in both a stack and a queue.
Basic Implementation of a Singly Linked List
We’ll create two classes, a Node class and SinglyLinkedList class. The Node class is pretty basic, it stores two pointers, one to the data it was initialized with and another, called next which points to the next node in the list.
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}With this in place, we can start creating our list like so:
var a = new Node(3)
var b = new Node(5)
var c = new Node(8)a.next = b
b.next = c
// 3-5-8
This creates the main portion of the list, however, we need another class so we can keep track of the metadata about the list — like where is the beginning and end of the list and how big is the list overall.
The goal is to have code which resembles this diagram:
class SinglyLinkedList{
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
} push(val){
let node = new Node(val)
if (this.head === null){
this.head = node
this.tail = node
} else {
this.tail.next = node
this.tail = node
}
this.length++
return this;
}
}
I added a push method to allow us to get data into the list.
var list = new SinglyLinkedList
list.push(3).push(5).push(8).push(10)
//3-5-8-10Arrays come with many built in methods. Our SinglyLinkedList class only has a push method. If you are up for it, you can take a stab at adding the following instance methods:
pop(){} //removes the last node from list, returns the nodeshift(){} //removes node from top of list, returns nodeunshift(val){} //adds new node to top of list, returns listget(idx){} //returns node at given indexset(idx, value){} //updates the value of node at given indexinsert(idx, value){} //adds new node at index, returns booleanremove(idx){} // removes node at index, returns removed node
The above are all manageable, but I find that reversing a singly linked list in place to be very confusing because of the setting and resetting of three pointers.
The first thing to understand is the process. We’ll create three pointers — previous, node, and next which will refer to the previous node, the current node and the next node. We’ll create a loop that runs for the length of the list and each iteration we’ll shift our pointers by one node to the right.
Starting List
3-5-8-10 //key: p=previous, n=node, nx=nextLoop 0: //prev: null, node: 3, next: 5
3-5-8-10
_ _ _
p n nxLoop 1: //prev: 3, node: 5, next: 8
3-5-8-10
_ _ _
p n nxLoop 2: //prev: 5, node: 8, next: 10
3-5-8-10
_ _ _
p n nxLoop 3: //prev: 8, node: 10, next: null
3-5-8-10
_ _ _
p n nx
In this way, we flip the head and tail of the list and set each node’s next property to the previous node (store in the previous pointer).
Again, here’s another image of what is happening.
Let’s take a look at the final implementation code.
reverse(){
var node = this.head
this.head = this.tail
this.tail = node
var next = null;
var prev = null;
for(let i=0;i<this.length;i++){
next = node.next
node.next = prev;
prev = node
node = next
}
return this
}Doubly Linked List
Now, let’s take a peak at how we’d structure our Node class for a doubly linked list.
class Node {
constructor(value){
this.value = value
this.next = null;
this.prev = null;
}
}As you can see, we’ve added one additional pointer — a reference to the previous node. With this addition, we can now traverse up and down the list. The below diagram should illustrate the point.
Space vs Time Complexity
As a result of adding the additional pointer we increase our memory requirements, but we improve of time efficiency for removing an element from the end of the list. In a singly linked list, you would need to traverse the entire list so that you could update the second to last element to be the new tail. However, because we now have a reference to the previous node, we can start with the tail and move just one position to the left to make our updates.
Additionally, our reverse method becomes a bit more intuitive to understand as all we have to do is flip the next and prev pointers.
reverse(){
let node = this.head
this.head = this.tail
this.tail = node let next = null;
let prev = null; for (let i=0;i<this.length;i++){
next = node.prev
prev = node.next
node.next = next
node.prev = prev
node = prev
} return this;
}
Using a Linked List for a Stack or Queue
As discussed in the beginning of this article, linked lists make a great option when you need to create a stack or queue. As singly linked list are a bit more performant, I’ll show the stack and queue implementations using it.
The verbage also changes slightly so instead of head, tail and length we’ll being using first, last and size. Finally, stacks and queues usually only have two functions, one to add the data and one to retrieve the data.
Stack Implementation
class Stack {
constructor(){
this.first = null
this.last = null
this.size = 0
} push(value) {
//unshift
let newNode = new Node(value)
if (this.size === 0){
this.first = newNode
this.last = newNode
} else {
newNode.next = this.first
this.first = newNode
}
return ++this.size
} pop() {
//shift
if (this.size === 0) return null
let temp = this.first
if (this.size === 1) {
this.first = null
this.last = null
} else {
this.first = this.first.next
} this.size--
return temp.value;
}
}
Queue Implementation
class Queue {
constructor(){
this.first = null;
this.last = null;
this.size = 0;
} enqueue(value){
let newNode = new Node(value)
if (this.size === 0) {
this.first = newNode;
this.last = newNode
} else {
this.last.next = newNode
this.last = newNode
}
return ++this.size
} dequeue() {
if (this.size === 0) return null
let removedNode = this.first
if (this.size === 1) {
this.first = null
this.last = null
} else {
this.first = removedNode.next
}
this.size--
return removedNode.value
}
}
