Photo by Jon Tyson on UnsplashThis article is originally published on dev.to on 3 Jan 2020.

In the previous article, I wrote about implementing linked lists on my Chrome Extension. Ended up not using them on the project, but I could see why it can be useful for certain situations.

Completed JavaScript Data Structure Course, and Here is What I Learned About Linked List

Currently, I'm storing the main data as objects in an array like this:

// Result of console.log(main-data)
(4)[{...}, {...}, {...}, {...}]
0: {category: "cat1", id: "4", meaning: "information of the vocabulary.", tag: ["tag1", "tag2"], word: "Example Vocab 1"}
1: {category: "cat3", id: "3", meaning: "Hello World", tag: ["tag1", "tag4"], word: "Example Vocab 2"}
2: {category: "cat2", id: "2", meaning: "This is new vocabulary.", tag: ["tag4"], word: "Example"}
3: {category: "cat4", id: "1", meaning: "You can write anything.", tag: ["tag2", "tag4", "tag5"], word: "Sample"}

In this situation, insertion and deletion take O(n). So I'm still looking for a data structure that is hopefully O(1).

What I learned after the linked list was stack and queue, so in this article, I'm going to think if I can implement them or not.

Can stack be the best choice?

As we can call stacks ‘Last in first out’ data structure, the last element that added to the stack will be removed first.

It is just like a stack of anything in real life, like a pile of dirty dishes in the sink. You put another dish to be washed on top of the pile, and once you decide to wash them, you wouldn’t pick one up from the bottom of the pile — you will pick the one you just put it last. It’s the same in stacks for the data structure.

To implement it as a singly linked list, JavaScript code will be like this:

class Node {
    constructor(value) {
        // store value in val
        this.val = value;
        // initialize next property empty
        this.next = null;
    }
}

class Stack {
    constructor() {
        // initialize the beginning of the list as first 
        this.first = null;
        // initialize the end of the list as last
        this.last = null;
        // initialize the length of the list as size
        this.size = 0;
    }
}

We are going to push a node to the beginning of the list instead of the end. Therefore it’ll be much easier to pop. We can write code like this:

push(val) {
    // create a new node with value
    const newNode = new Node(val);
    if(this.size === 0) {
        // if nothing in the list, define new node as first and last
        this.first = newNode;
        this.last = this.first;
    } else {
        // otherwise, define next property of new node as current first node 
        newNode.next = this.first;
        // define new node as first
        this.first = newNode;
    }
    // imcrement size of the list
    return this.size++;
}
pop() {
    // define the node which will be removed
    const remove = this.first;
    if(this.size === 1) {
        // if there is only one node in the list, empty first and last
        this.first = null;
        this.last = null;
    } else {
        // otherwise, store 2nd node from the beginning in newFirst
        const newFirst = this.first.next;
        // define next property of removed node empty
        remove.next = null;
        // define newFirst as first
        this.first = newFirst;
    }
    // decrement size of the list
    this.size--;
    return remove.val;
}

This structure works best when you want to especially record the current action, and want to make the action to be able to go back/forth. Your text editor can be a good example of this — you can Undo and Redo, but it doesn’t need to be able to pick up one certain point of the previous action.

It is not the best way for my project to store the main data because I want the data to be faster than O(n) when an element is removed/edited not only at the end of the list but anywhere.

How about queues?

I have already the answer to this question. It is not suitable for the main data of my project, because the structure is almost the same as the stack which is linked list or array.

The difference from the stack is that the first element that was added to the queue will be removed first — which we can call it ‘First in First out’ structure.

To implement it in a singly linked list, JavaScript code will be like this:

class Node {
    constructor(value) {
        // store value in val
        this.val = value;
        // initialize next property empty
        this.next = null;
    }
}

class Queue {
    constructor() 
        // initialize the beginning of the list as first 
        this.first = null;
        // initialize the end of the list as last
        this.last = null;
        // initialize the length of the list as size
        this.size = 0;
    }
}

Initialization is the same as a stack. To make it easier, when you remove the first node that you added, we are going to add a node at the end, and remove a node from the beginning of the queue.

enqueue(val) {
    // create new node
    const newNode = new Node(val);
    if(!this.first) {
        // if nothing in the list, define new node as both first and last
        this.first = newNode;
        this.last = this.first;
    } else {
        // otherwise, define next property of current last node as new node
        this.last.next = newNode;
        // replace last node to new node
        this.last = newNode;    
    }
    // increment the size of the list
    this.size++
    return this;
}
dequeue() {
    // store the node that will be removed in remove
    const remove = this.first;
    if(this.size === 1) {
        // if there is just one node in the list, empty first and last property 
        this.first = null;
        this.last = null;
    } else {
        // otherwise, define 2nd node from the beginning as new first
        this.first = remove.next;
        // empty next property of removed node
        remove.next = null;
    }
    // decrement the size of the list
    this.size--;
    return remove.val;
}

Although a queue might not be a suitable data structure for my project, it is commonly used for many occasions. For instance, when we are printing a document with a printer, and if we continuously add more documents to print out, the printer will process the data which was added first.

Therefore queues are more suitable for the situation where the order is more important for the whole process.

Conclusion

Stacks and queues are useful for data that you want to keep them ordered in a certain duration of the process, and also no need to keep them when it’s done. As I am in search of data structure that would be suitable for storing data, stacks and queues are not the best choices this time, but I’m certain that I would be using them very often in the future.

Next article, I’m going to write about binary search trees.