Data Structure Series: Linked List

Introduction

We use forks to eat pasta, spoons to eat soup, and chopsticks to eat dumplings. Each silverwares have its advantages/disadvantages, hence working better than the other for the food that it interacts well with. Just like that, different data structures are better suited and perform better than the others based on the situations/use cases. They each have their pros and cons. Understanding these pros and cons can help you be a better programmer, as it will allow you to choose an appropriate data structure(s) based on the circumstances/goals you have, and it helps to drastically improve the performance of the algorithm being applied. Feel free to leave a comment if you have any questions!

Table of Contents

1. What is Linked List?
2. Implementation in JavaScript
3. Helper Methods
4. Big O
5. Helpful Resources

1. What is Linked List?

A Linked List is a collection of data in a sequence, with each of the data referencing its next node (or previous node if it is a Doubly Linked List) from its 'head' to the 'tail'.

A Linked List is a type of data that is represented in a sequential collection. Each piece of data in that collection is called the node, which references its adjacent node in the sequence. The first node of a linked list is called the 'head', and the last node is called the 'tail'. There are two types of linked lists: Singly Linked List and Doubly Linked List. As the names suggest, Singly Linked Lists’ nodes are linked in only single direction, so each nodes references its next node. On the other hand, Doubly Linked Lists’ nodes reference both its previous and the next node. In summary, a Linked List is a collection of data in a sequence, with each of the data referencing its next node (or previous node if it is a Doubly Linked List) from its 'head' to the 'tail'.

It sounds a bit similar to a built-in data structure Array, doesn't it? The difference is that Arrays store each data in a consecutive manner in the memory meaning that the elements are stored next to each other. And each elements is indexed based on the position, and each element is directly accessible using those indices. Meanwhile, Linked Lists store each data anywhere in the memory, but the nodes reference their next and previous node. So in order to access a specific node in a Linked List, you need to traverse the list sequentially from its head or tail to the other end until you get to the node you are looking for.

Because of these differences, there are things that linked lists can do better than arrays, and vice versa:

• Arrays can search faster

  As we discussed, Arrays support random access, so we can access any elements in the (n)th index very quickly while Linked Lists support sequential access, so we have to start from the head or tail to the (n)th node or value of the node we are looking for, thus taking longer time to search an element.

• Linked Lists can insert/delete faster

  In order to insert or delete an element in the beginning or middle of an Array, you have to shift all of the elements on the right since its consecutive index positions will change. So inserting and deleting an element in an array can be costly unless you are inserting or removing the last element of the array (since there's no elements after the last element). With Linked Lists, inserting/deleting the first and the last element takes constant time since we just have to update the head/tail. Inserting/deleting an element in the middle can take linear time as well though, since you'd have to find the position to insert/delete by traversing the list one element at a time. However, there's no need to update all the elements that come afterwards, you just have to rearrange its adjacent nodes.

2. Implementation in JavaScript

Singly Linked List

// each node references its NEXT node
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class SinglyLinkedList {
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}

let SLL = new SinglyLinkedList();
let firstNode = new Node(16)
let secondNode = new Node(2)
let thirdNode = new Node(46)

// set the first new node as the SLL's head
SLL.head = firstNode;
SLL.length++;

// second as its next
firstNode.next = secondNode;
SLL.length++;

// the third as the second's next 
// while also setting it as a tail since it's the last one.
secondNode.next = SLL.tail = thirdNode;
SLL.length++;

// This SLL will look something like this:
// (16) => (2) => (46)

Doubly Linked List

// each node references both its NEXT and PREVIOUS node
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}

let DLL = new DoublyLinkedList();
let firstNode = new Node(361)
let secondnode = new Node(99)
let thirdNode = new Node(4)

// set the first new node as the DLL's head
DLL.head = firstNode;
DLL.length++;

// second as its next, and head as its prev
firstNode.next = secondNode;
secondNode.prev = firstNode;
DLL.length++;

// the third as the second's next 
// while also setting it as a tail since it's the last one.
secondNode.next = DLL.tail = thirdNode;
thirdNode.prev = secondNode;
DLL.length++;

// This SLL will look something like this:
// (361) <=> (99) <=> (4)

We will set up a Node class which accepts a value and set it to its value, with its next property (and prev if Doubly Linked List) initialized to null. Linked List class will be a sequential collection of these nodes, which will have its head and tail. We will want to keep track of the list's length, and increment/decrement it every time a new node is added or removed. Since Singly Linked Lists's nodes only reference the next node and Doubly Linked Lists' nodes reference both their next and previous nodes, Singly Linked Lists are simpler but less powerful than Doubly Linked Lists.

If you were to implement a helper method to pop the last element of the list, it's easier to do that with Doubly Linked Lists as you simply have to remove the tail of the list, and set the new tail to be the previous node of the tail being removed. On the other hand, we can access the tail of the list, but will have to traverse the entire list and remember the previous node until you hit the tail so you can remove the tail and set the remembered previous node to be the new tail.

The main drawback of using Doubly Linked List vs Singly Linked List is that Doubly Linked List takes up more space than the Singly Linked List since you have to set each nodes' next and previous node. But in return, it opens up more doors to make your data and its algorithms efficient. With that being said, here are couple helper methods to utilize Linked Lists better. However, we will only focus on Doubly Linked Lists for this blog post.

3. Helper Methods (Doubly Linked List only)

push()

// accepts a value as an argument
// appends a new node with the value passed at the end of the list
push(value) {
    let newNode = new Node(value);
    if(!this.head) {
        this.head = this.tail = newNode;
    } else {
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
    }
    this.length++;
    return this;
}

Pseudo code:

• Create a new node with the value passed to the function
• If the head property is null, set the head and tail to be the newly created node
• If the head is not null, set the next property on the tail to be that node
• Set the prev property on the newly created node to be the tail
• Set the tail to be the newly created node
• Increment the length
• Return the Linked List

pop()

// removes the last node (tail) of the list
pop() {
    if(!this.head) return undefined;
    let removedNode = this.tail;
    if(this.length === 1) {
        this.head = this.tail = null;
    } else {
        this.tail = removedNode.prev;
        this.tail.next = null;
        removedNode.prev = null;
    }
    this.length--;
    return removedNode;
}

Pseudo code:

• If there is no head, return undefined
• Store the current tail in a variable to return later
• If the length is 1, set the head or tail to be null
• Update the tail to be the previous Node
• Set the new tail's next to null
• Decrement the length
• Return the node removed

unshift()

// accepts a value as an argument
// prepends a new node with the value passed at the beginning of the list
unshift(value) {
    let newNode = new Node(value);
    if(this.length === 0) {
        this.head = newNode;
        this.tail = this.head;
    } else {
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
    }
    this.length++;
    return this;
}

Pseudo code:

• Create a new node with the value passed to the function
• If the length is 0, set the head and tail to be the new node
• Otherwise
  • Set the prev property on the head to be the new node
  • Set the next property on the new node to be the head property
  • Update the head to be the new node
• Increment the length
• Return the Linked List

shift()

// removes the first node (head) of the list
shift() {
    if(this.length === 0) return undefined;
    let oldHead = this.head;
    if(this.length === 1) {
        this.head = null;
        this.tail = null;
    } else {
        this.head = oldHead.next;
        this.head.prev = null;
        oldHead.next = null;
    }
    this.length--;
    return oldHead;
}

Pseudo code:

• If length is 0, return undefined
• Store the current head property in a variable
• If the length is one, set the head and tail to be null
• Update the head to be the next of the old head
• Set the head's prev property to null
• Set the old head's next to null
• Decrement the length
• Return old head

get()

// accepts an index as an argument
// returns the node at the index passed
get(idx) {
    if(idx < 0 || idx >= this.length) return null;
    let count, current;
    if(idx <= this.length/2 ) {
        count = 0;
        current = this.head;
        while (count !== idx) {
            current = current.next
            count++
        }
        return current;
    } else {
        count = this.length-1;
        count = this.tail;
        while (count !== idx) {
            current = current.prev
            count--
        }
        return current;
    }
}

Pseudo code:

• If the index is less than 0 or greater or equal to the length, return null
• If the index is less than or equal to half the length of the list
  • Loop through the list starting from the head and loop towards the middle
  • Return the node once it is found
• If the index is greater than half the length of the list
  • Loop through the list starting from the tail and loop towards the middle
  • Return the node once it is found

set()

// accepts an index and value as arguments
// finds the node at the index, and updates the node's value to the value passed
// returns false if the node is not found, true if the value is updated
set(idx, value) {
    let foundNode = this.get(idx);
    if(!foundNode) return false;
    foundNode.value = value;
    return true;
}

Pseudo code:

• Create a variable which is the result of the get method at the index passed to the function
• If the get method does not return a valid node, return false
• Set the value of the node found from get method to the value passed to the function
• return true

4. Big O

• Space Complexity:

  • O(n)
  • Space complexity of this data structure is linear, as the size of the list increase, so does the space

• Push/Pop and Shift/Unshift:

  • O(1) Time Complexity
  • It will take constant time to add/remove the node at the head and tail of a Linked List, since we just have to add a new node to the either end, and update the newly added node as its head/tail, or its previous/next element as head or tail if the node is being removed.

• Get/Set and Insert/Delete:

  • O(n) Time Complexity
  • In order for us to find an element in a Linked List, we will need to traverse the list to find the index or value of the index. Due to this nature of the Linked List, modifying the node in the middle of the list will take linear time (the time complexity changes based on the list size). Although Insert/Delete methods are not listed in the helper method above, you get the idea that we will have to traverse the list to find an index of the list to insert/delete the element.

5. Helpful Resources

Online Course (Udemy Course)
Check out this Udemy course named JavaScript Algorithms and Data Structures Masterclass! It is created by Colt Steele, and I referenced his code for the data structure implementation part of this blog post. Personally, I didn't know where to start with algorithms and data structures especially coming from a non-tech background. This course is very well structured for beginners to build a foundation on these topics.

Visual Animation (VisuAlgo)
Data structures can be difficult to comprehend for some people just by looking at the code/text. The instructor in the course above uses a website named VisuAlgo that has visual representation of algorithms and data structures through animation.

Data Structure Cheat Sheet (Interview Cake)
Also, here's a really well-summarized cheat sheet/visualizations on data structures.