Linked List Javascript. Easier than you think.
Tags: javascript, react, datastructures, node
Published: 2023-07-09 04:56:11

Thinking about data structure, let's take a closer look at Linked List. 

**Linked list** is one of the most popular and efficient data structures. Basically, Linked List is a collection of "nodes", each node contain _data_, _next_ and _previous_, basically _next_ refers to next node and _previous_ refers to the previous node.

We can say that, array and linked list is similar. but in array, elements are stored in a specific location or index.

On the other hand, in Linked List everything works as a separate object. Each element (node) contain few things, data, link to the next node, link to the previous node.


**Types of Linked List:**
There are three types of linked list,

**1. Singly Linked List:** Each node contains data and a pointer to the next node. Basically its unidirectional. 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bjinw2ggf3bmmncp7qrq.png)

Analyzing the above image, it start with _Head_, so _Head_ is the entry point. If a Linked list is empty then the _Head_ will be null. So _Head_ reference to the first node and _Last_ node points to the null. 


```
const linkedList = {
    head: {
        value: 5
        next: {
            value: 7                                             
            next: {
                value: 2
                next: {
                    value: 15
                    next: null	
                    }
                }
            }
        }
    }
};
```


Basic example,


```
// class of node
class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

/* LindedList class. remember, if the head node is not passed then head will be null */
class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

/* lets create some nodes */

let node1 = new ListNode(5) // data will be 5
let node2 = new ListNode(7) // data will be 7
let node3 = new ListNode(2) //  data will be 2
let node4 = new ListNode(15) // data will be 15

node1.next = node2 // points to the node2
node2.next = node3 // points to the node2
node3.next = node4

let list = new LinkedList(node1) // Linked List completed

```


**Advantage and Uses of Singly Linked List**

**- Dynamic data structure:** Memory is dynamically allocated to the linked List. easily we can add or remove an element. We don't need to think about initial size.
**- Implementation:** Other data structure can be easily implemented here such as Queues and Stacks.
**- Versatility:** Lined list can be used to implement a wide range of data structures, such as stacks, queues, graphs, truees and has tables. 


**Disadvantage of Singly Linked List**

**- Memoray usage:** We need to store address of the next data, so it takes more memory.
**- Accessing an element:** Its impossible to access any element directly. If we need to find nth value, then we need to traverse until nth element found.
**- Reverse traversal:** It impossible for the Singly linked List. Because we don't have the memory address of the previous pointer. 
**- More complex implementation:** Similar to Array, Its implementation is very complex. We need to understand dynamic memory location and pointer manipulation. 
**- Lack of cache locality:** It may not take advantage of the caching mechanisms in modern processors. Its slower in performance.


**2. Doubly Linked List:** Each node contains two pointers one for next node and one for previous node.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/glt2shao3auv8a7yu8bd.png)

in the above image, we understand that,

- prev: refers to the previous node
- data: data item
- next: address to the next node

below image shows us representation of doubly Linked list, Here each node contain _next _and _prev_ to point _next node_ and _prev node_

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cc37m2zeaxb7ar4goaen.png)

Basic example

```
class ListNode  {
	constructor(value) {
		this.value = value;
		this.next = null;
		this.previous = null;
	}
}

class DoublyLinkedList {
	constructor(value) {
		this.head = {
			value: value,
			next: null,
			previous: null
		};
		this.length = 0;
		this.tail = this.head;
	}

	// Insert node at end of the list
	add(newNode) {
		this.tail.next = newNode;
		newNode.previous = this.tail;
		this.tail = newNode;
		this.length++;
	}

    printList() {
		let current = this.head;
		let result = [];
		while (current !== null) {
			result.push(current.value);
			current = current.next;
		}
		console.log(result.join(' '));
		return this;
	}
}

let numList = new DoublyLinkedList();
numList.add(new ListNode (12));
numList.add(new ListNode (13));
numList.add(new ListNode (14));
numList.add(new ListNode (15));
numList.add(new ListNode (16));
numList.add(new ListNode (17));
numList.printList();
console.log(numList)
console.log(numList.head)

```


**Advantage of Doubly Linked List:** 

**- Reversing:** Reversing the doubly linked list is very easy.
**-Traversal:** The traversal of this doubly linked list is bidirectional which is not possible in a singly linked list.
**-Deletion:** Deletion of nodes is easy as compared to a Singly Linked List.


**Disadvantage of Doubly Linked List:**

- It uses extra memory when compared to the array and singly linked list.
- Traversing a doubly linked list can be slower than traversing a singly linked list
- Implementing and maintaining doubly linked lists can be more complex than singly linked lists.


**Uses of Doubly Linked List:**

**- Navigation Systems:** It is used in the navigation systems where front and back navigation is required. 
**- Undo and Redo:** It is also used by various applications to implement undo and redo functionality.
**- MRU/LRU:** Doubly Linked List is also used in constructing MRU/LRU (Most/least recently used) cache.
**- Thread Scheduler:** Also in many operating systems, the thread scheduler(the thing that chooses what process needs to run at which time) maintains a doubly-linked list of all processes running at that time.
**- Browser:** next and previous page.
**- Image viewer:** next and previous image
- Implementing **Graph **algorithms


**3. Circular Linked Lists:** Its different than others, its last node points to the first nor or any other node before it.
It has two types,

- Circular Singly Linked List
- Circular Doubly Linked List


We will learn Circular Linked List in the next. that's it for today. See yaaa.