My Point of View for Linked Lists | maikomiyazaki

Course Recap (1): Introduction and My Point of View for Linked Lists

15/12/2019

JavaScript

It took a month to complete JavaScript Algorithms and Data Structures course on Udemy, and it was absolutely stimulating. Before taking the course, I only knew how to implement array and simple object and I didn’t even know that it can be inefficient depends on the data types. Therefore it was perfect timing to learn data structures, and it gave me such inspirations.

At the beginning of the course, I had already realized that the way I stored the main data wasn’t suitable for my Chrome Extension project. I was using arrays and objects to store three types of data in chrome local storage.

The main data was stored like this:

I wanted to implement features to remove/edit each element efficiently. But as long as this structure, removing/editing a single element takes O(n) time complexity which can involve re-indexing the whole data, so it’s not so good.

Is Singly Linked list a good choice?

The data structure I learned first on the course was singly linked list. 

This list type looks like this visually:

Each element is called node, and doesn’t have indexes. Instead, you need to define what is the starting node(head) and the end(tail), and each node contains an arrow to point out which the next node is.

To implement it in JavaScript, it will look like this:

// Instantiate Node
class Node{
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

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

To add a node at the end of the list, you just need to point out the current tail’s next arrow to the new node, and define the new node as the new tail.

push(val) {
    let newEl = new Node(val);
    if (!this.head) {
        this.head = newEl;
        this.tail = newEl;
    } else {
        this.tail.next = newEl;
        this.tail = newEl;
    }
    this.length += 1;
    return this;
}

It is not the most efficient data structure if you are editing/deleting node often, because if you want to find out a specific node, you need to start from the very beginning and go through all the nodes until you find the one.

In the beginning, I thought singly linked list is useless, but it’s actually useful if the node already exists somewhere else, and also if it doesn’t require removing/editing nodes. For example, music streaming services such as Spotify might be using it when it comes to shuffling random music. I realized that you can’t go back to previous music in certain situations, and in that case, singly linked list contains just what it needs.

How about Doubly linked list ?

Doubly linked list is almost the same as singly linked list, but each node contains another arrow to point out the previous node as well as the next node. It looks like this visually:

In this case, if you implement it to the Spotify example that I mentioned earlier, you can forward the playlist and also go back to previous music. As well as singly linked list, it doesn’t require to crone each node and you just need to connect previous/next music with arrows. So I think general playlists on music streaming service can be a good example of doubly linked list.

To implement it in JavaScript, simply add this.prev property.

It will look like this:

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

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

To add a node at the end of the list, you just need to point out the current tail’s next arrow to the new node, and define the new node as the new tail. Also don’t forget to point out new tail’s prev to the old tail.

push(val) {
        let newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            let currentTail = this.tail
            currentTail.next = newNode;
            newNode.prev = currentTail;
            this.tail = newNode;
        }
        this.length += 1;
        return this;
    }

Conclusion

Both of the linked lists are not suitable for my chrome extension project because removing/editing elements are required regularly. These data structures work well if you are going to display each element one by one, but if you want to display all the data/selected data on a single page, then there’s no point using a linked list.

Next article, I’m going to write about stacks/queues, and my point of view of their usage.