Linked list

data structure - linked list

What is a linked list?

Are container where data is stored in nodes
The nodes consist single data item and pointer/reference to the next node

What is a node?

The node is nothing but a link in the linked list
The node contains two things
It contains a value
Its contain reference to the next list

Types of linked list

Singly-linked list
Doubly linked list

Singly-linked list

Is a linked list that provides forward iteration from the start to the end of the list
The iteration starts from the first node and ends at the last node

Doubly linked list

Is a linked list that provides forward iteration from the start to the end of the list and reverses iteration from end to start
Traversing from the current node to the next and previous node is possible

Singly vs Doubly linked list

Singly-linked list requires lesser memory compared doubly
Singly-linked list cant be iterated in reverse while doubly linked can be
Deleting the previous node in doubly linked doesn’t require traversing

Write a code

Let’s write a linked list in javascript

// Linked in Javascript
  class LinkedList {
    constructor(data) {
        this.head = {
            data: data,
            next: null
        };
        this.tail = this.head;
        this.length = 1;
    }
    addData(data) {
        const newNode = {
            data: data,
            next: null
        }
        this.tail.next = newNode;
        this.tail = newNode;
        this.length++;
        return this;
    }
    insert(index, data) {
        if (index >= this.length) {
            return this.addData(data);
        }

        const newNode = {
            data: data,
            next: null
        }
        const leader = this.traverseToIndex(index - 1);
        const holdingPointer = leader.next;
        leader.next = newNode;
        newNode.next = holdingPointer;
        this.length++;
        return Promise.resolve(true);
    }
    traverseToIndex(index) {
        let counter = 0;
        let currentNode = this.head;
        while (counter !== index) {
            currentNode = currentNode.next;
            counter++;
        }
        return currentNode;
    }
    remove(index) {
        let traversingItem = index - 1;
        if (index === 0) {
            traversingItem = 0;
        }
        const leader = this.traverseToIndex(traversingItem);
        const removeNode = index === 0 ? null : leader.next;
        leader.next = index === 0 ? null : removeNode.next;
        this.length--;
        return Promise.resolve(true);
    }
}

let linkedListInstance = new LinkedList(1);
linkedListInstance.addData(2);
linkedListInstance.addData(3);
linkedListInstance.insert(2, 99);
linkedListInstance.insert(5, 88);
console.log(linkedListInstance);

// LinkedList {
//   head: { data: 1, next: { data: 2, next: [Object] } },
//   tail: { data: 88, next: null },
//   length: 4
// }