DEV Community

Bvnkumar
Bvnkumar

Posted on • Edited on

Javascript Linked List data structure

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())
Enter fullscreen mode Exit fullscreen mode

Any comments or suggestions are welcome.

Top comments (0)