Learn and Implement Data Structure in JS - Singly LinkedList

Learn and Implement Data Structure in JS - Singly LinkedList

The problem is that many of the people trying to learn data structures but not implementing them.

People start worrying about data structures. This occurs because everyone has heard that a good knowledge of data structures is important for technical interviews and so people get obsessed with trying to learn these topics. They don't realize they'd be better served by implementing them rather than just read about it.

So I have started this series to focus on each data structure and how to implement them in Javascript.

In this article, we will be implementing a Singly LinkedList data structure in Javascript.

What is Singly Linked List

A linked list is a linear data structure, in which we can add or remove elements at ease, and it can even grow as needed. Just like arrays, but elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.

single linked list.png

Implementing Singly Linked List

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

As in the code above, we have two properties elements which holds the data of the current node and next holds the pointer (address) of the next node which initialized to null.

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

Above code shows a SinglyLinkedList class with constructor, the Linked list has a property called head which will hold the first node of the linked list**.

Adding element into list

add(element) {
    //create new node
    let node = new Node(element);

    let current = null;

    //If head is empty then insert at first item
    if (this.head == null) {
        this.head = node;
    } else {
        current = this.head;

        //iterate to end of list
        while (current.next) {
            current = current.next;
        }


        //Finally add new node
        current.next = node;
    }

    this.size++;
}

In order to add an element, in the end, we should consider the following :

  • If the list is empty then add an element and it will be head

  • If the list is not empty then iterate to end of the list then add an element to end of the list.

Removing element from the list

removeElement(element) {
    if (this.head === null) {
        throw Error ('List is empty');
    }

    let current = this.head;
    let prev = null;

    //Iterate over the list
    while (current != null) {

        if (current.element === element) {
            //If prev node is null then first node is required element
            if (prev === null) {
                this.head = current.next;
            } else {
                //if prev node found then unset current node
                prev.next = current.next;
            }

            return current.element;
        }

        prev = current;

        //iterate to next node
        current = current.next;
    }
    return 'Element not found';
}
  • this.head === null If List is empty then throw an error `
  • while (current != null)` Iterate list till find the element
  • prev === null If prev node is null then first node is required element so make second node as head
  • If prev node is found then prev.next = current.next detach current node from list

That's it we have covered basics of Singly LinkedList.

Unit Test

var assert = require('assert');
const LinkedList = require('./single.linkedlist');

describe('Single Linked List', () =>{

    const linkedList = new LinkedList();
    it('Should add an element', () =>{
        linkedList.add(10);
        let result = linkedList.get('list');
        assert.equal(JSON.stringify(result), '{"element":10,"next":null}')
    })

    it('Should add two element', () =>{
        linkedList.add(20);
        linkedList.add(30);
        let result = linkedList.get('list');
        assert.equal(JSON.stringify(result), '{"element":10,"next":{"element":20,"next":{"element":30,"next":null}}}')
    })

    it('Should remove an element', () =>{
        linkedList.removeElement(20);
        let result = linkedList.get('list');
        assert.equal(JSON.stringify(result), '{"element":10,"next":{"element":30,"next":null}}')
    })
})

Capture.PNG

Check Github Repo for full source code.

Stay Tuned for the next story.