Part 3 — Linked List Data structure in js

Introduction

A Linked list is a linear data structure in which every element contains information about the data it holds and a pointer to next element. Each such element in a linked list is called as node. The nodes may be at different memory locations, unlike arrays where all the elements are stored continuously.

Types of Linked Lists

A linked list is designed depending on its use. The 3 most common types of a linked list are:

1. Singly Linked List — This is the most common type of linked list, where each node has one pointer to the next node in the sequence. This means that the list can only be traversed from the beginning to the end in one direction. In this section, we will focus on implementation and operations of a singly linked-list.
2. Doubly Linked List — A doubly linked list has 2 pointers, one pointing to the next node and one to the previous node. This allows for moving in both directions while traversing.
3. Circular Linked List — A circular linked list is like a regular one except for the last element of the list pointing to the first. This has the advantage of allowing to go back back to the first element while traversing a list without starting over.

Implementation

In order to implement a linked list, we have to define a root node while creating a linked list which will point to null initially. To insert data in a linked list, we will create a Node constructor which will create a node with data and next pointer.

Below is the implementation :

function LinkedList() {
    this.root = null;
}
function Node(value) {
    this.value = value;
    this.next = null;
}
// This will create an empty linked-list
let list = new LinkedList();

An empty linked-list can be created using above implementation but we still cannot add any data to our linked-list. In the operations section, we will add more operations to the linked-list such as insert, insertAt , removeAt, search, findMiddle, etc.

Operations

Numerous operations can be performed on a linked-list. For the understanding sake, we will focus on basic operations listed below:

Insert at the end of the list - insertEnd()
Find a value in the list - search(value)
Find Length of a linked-list - getSize()
Delete value from Linked List - deleteValue(value)
Print middle element of a linked list - printMiddle()
Get Nth node in a LinkedList - getNthNode()
Print List values - printList()

Insert At the end of the list

LinkedList.prototype.insertAt = function insertAt(value, node){
	if(node == null){
		return new Node(value);
	} else {
		node.next = insertAt(value, node.next);
		return node;
	}
}

LinkedList.prototype.insert = function(value, node){
	this.root = this.insertAt(value, this.root);
}

Find a value in the list

LinkedList.prototype.search = function search(value, node) {
    if(node === undefined){
        node = this.root;
    }
    if(node === null) {
        return "Not found";
    }
    if(node.value === value) {
        return node;
    } else {
        return search(value, node.next);
    }
  return "Not found";
}

Find Length of a linkedList

LinkedList.prototype.getSize = function(){
    let current = this.root;
    let count = 0;
    while(current !== null){
	count++;
	current = current.next;
    }  
    return count;
}

Delete value from Linked List

LinkedList.prototype.deleteValue = function(value){
	let current = this.root;
	if(current === null){
		return new Error("cannot delete from an empty list");
	}
	if(current.value === value){
		this.root = current.next;
		return;
	}
	let prev;
	while(current.next !== null){
		prev = current;
		current = current.next;
		if(current.value === value){
			let temp = current.next;
			prev.next = temp;
			return;
		}
	}
	return "value not found";
}

Print middle element of a linked list

LinkedList.prototype.printMiddle = function(){
	let slowRef = this.root;
	let fastRef = this.root;
	while( fastRef !== null && fastRef.next !== null){
		slowRef = slowRef.next;
		fastRef = fastRef.next.next;
	}
	console.log(slowRef.value);
}

Get Nth node in a LinkedList

LinkedList.prototype.getNthNode = function(n){
	let current = this.root;
	let i = 0;
	while(current !== null){
        if(n === i){
        	return current.value;
        }
		current = current.next;
		i++;
	}
	return "not found";
}

Print List

LinkedList.prototype.print = function printNode(node = this.root){
    if(node == null) return;
    console.log(node.value);
    printNode(node.next);
}

Time Complexity

Linked list is again a linear data structure hence to access any element, we have to iterate through each node one by one until we reach the required element. The time complexity is therefore O(n).

In case of insertion and deletion, time complexity varies depending upon the location. If we are inserting or deleting from the beginning, time complexity will be O(1). For all other cases, it’s O(n).

Usage

1. Linked-lists are generally used to implement other data structures such as stacks, queues and non-linear ones like trees and graphs.
2. It has uses in hash chaining for the implementation in open chaining.
3. Polynomials can be represented and manipulated by using linked lists.
4. It can be used to perform operations on long integers.

Conclusion

In this section, we got a good understanding of linked list, its implementation and uses. There are a lot of operations related to a linked list. I will recommend you to spend good amount of time in understanding and implementing such operations on a linked list. In the next section, we will continue our exploration with other linear and non-linear data structures. Stay tuned!