Data Structure Series: Linked List
Tags: datastructure, linkedlist, programming, javascript
Published: 2021-08-09 16:15:48

## Introduction

![data-structure-series-intro](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5xpt6in1hml7m89611hj.png)

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?](#first)**
**2. [Implementation in JavaScript](#second)**
**3. [Helper Methods](#third)**
**4. [Big O](#fourth)**
**5. [Helpful Resources](#fifth)**

***

## 1. What is Linked List? <a name="first"></a>
> 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'*.

![linked-list1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0n3m9367xhmbbntpaaxs.png)
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 <a name="second"></a>
**Singly Linked List**
```javascript
// 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**
```javascript
// 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) <a name="third"></a>

**push()**
``` javascript
// 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()**
``` javascript
// 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()**
``` javascript
// 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()**
``` javascript
// 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()**
``` javascript
// 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()**
``` javascript
// 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 <a name="fourth"></a>
![linked-list-big-o](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/38wer67h7y7yvvf0b92d.png)

- **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 <a name="fifth"></a>
[**Online Course**](https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/) **(Udemy Course)**
Check out this Udemy course named JavaScript Algorithms and Data Structures Masterclass! It is created by [Colt Steele](https://www.youtube.com/c/ColtSteeleCode), 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**](https://visualgo.net/en) **(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**](https://www.interviewcake.com/data-structures-reference) **(Interview Cake)**
Also, here's a really well-summarized cheat sheet/visualizations on data structures.