Linked List in JavaScript

What is a Linked List in JavaScript?

The linked list in Javascript is a data structure that stores a collection of ordered data that can only be accessed sequentially. The data element (technically a node) consists of some information and a pointer. In contrast to an array, data elements in a linked list are not stored at contiguous memory locations and thus cannot be accessed randomly.

The $1$^st node is pointed by a distinctive pointer called as head of linked list. From the $n$^th node we can reach to $n+1$^th node only.

Properties of a Linked List

• Linked lists are dynamic, which means they can grow or shrink during the runtime of a program.
• Linked lists can be accessed only sequentially.
• The nodes are not stored in contiguous memory locations.
• Node contains the data and pointer.
• A particular node is pointed and can be accessed by the pointer stored in the previous node.
• The first node of the linked list is pointed by a specific pointer called the head.
• The last node of the linked list points to null, which specifies the end of the list.

Types of Linked lists

1. Singly Linked List

This is the most basic linked list that we were discussing till now, it can be traversed only in one direction that is from start to end.

• Only one-directional access is allowed.

2. Doubly Linked List

The node of this linked list contains two pointers instead of one, making it possible to access the next as well as the previous node from the current node.

• We can access the linked list from both directions.
• We can insert a node before the current node easily.

3. Circular Linked List

The last node of the linked list instead of pointing to null points to the first node.

• We can traverse this linked list in a sequential as well as circular manner.
• It is generally used in the queue-related concepts.

Implementation

After all theoretical discussion of linked list, here we will implement the entire module of linked list in Javascript.

Linked List

Node

Operations of a Linked List

Since every user-defined data structure has its own operations, linked lists have a couple of their own as well. Listed Below are all the operations commonly performed on the linked list data structure.

appendNode(node)

This method will append the node in the linked list.

Example:

Output:

insertAt(index)

This function will insert the node at specified index.

Example:

Output:

removeFrom(index)

This function will remove the node from specified index.

Example:

Output:

getNode(index)

This function will return the node from specified index.

Example:

Output:

clear()

This function will empty a linked list by making head pointing towards null.

Example:

Output:

reverse()

This function will reverse the entire list.

Example:

Output:

Helper Methods

We will need several helper methods so that object of this class can perform the required operation, we are going to discuss the implementation of those helper methods in detail. Use this JavaScript Beautifier to beautify your code.

indexOf(element)

This function will return first index which matches with the passed element.

Example:

Output:

isEmpty()

This function will return true if our linked list is empty otherwise return false.

Example:

Output:

listSize()

This function will return the size of the linked list, or we can say number of nodes. $Number of Nodes = Size of Linked List$

Example:

Output:

getFirst()

This function will return the first node of linked list.

Example:

Output:

getLast()

Similar to the last one, this function will return the last node of linked list.

Advantages of Linked List

• Dynamic in Nature: Linked list can grow or shrink during program execution according to user requirements.
• Memory Optimization: The linked list efficiently uses memory. As opposed to arrays, where we allocate more memory than the current need, linked lists do not require us to allocate memory in advance.
• Constant time Insertion and Deletion: If we have a pointer to a certain location where we either want to insert a new node or delete the node from that location, it will take a constant amount of time. During insertion, we simply create a new node and store its address at the specified location. A delete operation simply releases the memory associated with the particular pointer.

Disadvantages of Linked List

• No Random Access: Linked list doesn't have random access to any node, we can only traverse sequentially.

• Management of Pointers: The nodes of the linked list stores data and a pointer, which is completely overhead because it's not storing any useful data from the view of the user.

• Reverse Traversing Issue: Linked lists do not allow reverse traversal, although we can use doubly linked lists to achieve this, but this will incur a memory overhead for storing the extra pointers.