Javascript Linked List data structure

Published at

4/26/2022

Categories

4 categories in total

LinkedList:

A linked list is a linear data structure similar to an array. However, unlike arrays, elements are not stored in a particular memory location or index. Rather each element is a separate object that contains a pointer or a link to the next object in that list.

Advantages:

Nodes can easily be added or removed from a linked list without re-organizing the entire data structure.

Disadvantages:

Search operations are slow in linked list over arrays, random access of data element is not allowed. Nodes are accessed sequentially from first node.
It uses more memory than arrays because of storage of the pointer.

Internal Design of linked list

function LinkedList() {
    let length = 0;
    let head = null;
    const Node = function(element) {
        this.element = element;
        this.next = null;
    }
    this.size = function() {
        return length;
    }
    this.head = function() {
        return head;
    }
    this.add = function(element) {
        let node = new Node(element);
        if (head == null) {
            head = node;
        } else {
            let currentNode = head;
            while (currentNode.next) {
                currentNode = currentNode.next;
            }
            currentNode.next = node;
        }
        length++
    }

    this.remove = function(element) {
        let currentNode = head;
        let previousNode;
        if (currentNode.element == element) {
            head = currentNode.next;
        } else {
            while (currentNode.element !== element) {
                previousNode = currentNode;
                currentNode = currentNode.next;
            }
            previousNode.next = currentNode.next;
        }
        length--;
    }
    this.isEmpty = function() {
        return length == 0;
    }
    this.indexOf = function(element) {
        let currentNode = head;
        let index = -1;
        while (currentNode) {
            index++;
            if (currentNode.element == element) {
                return index;
            }
            currentNode = currentNode.next;
        }
        return -1;
    }
    this.elementAt = function(index) {
        let currentNode = head;
        let count = 0;
        while (count < index) {
            count++
            currentNode = currentNode.next;
        }
        return currentNode.element;
    }
}
var link = new LinkedList();
link.add("hello");
link.add("hello")
console.log(link)
console.log("elementAt", link.elementAt(0))
console.log("indexOf", link.indexOf("bye"))
link.remove("hello")
link.remove("hello")
console.log("isEmpty", link.isEmpty())
console.log("length", link.size())

Any comments or suggestions are welcome.

dev-resources.site

Javascript Linked List data structure