Linked List Implementation in JavaScript

Linked lists are among the most fundamental data structures. In the following sections, we will explore linked list types of linked lists and then, we will implement linked list in JavaScript. At the end of this article, you will know linked lists, and you will use linked lists in code with confidence

What is a Linked List?

Linked List is a linear structure where data elements are stored at non-contiguous location parts and the element connected using pointer (Pointer is a variable that holds memory address). A node is made of two parts:

1. Data: The data that a node contains.
2. Pointer: To the next node in the sequence (or null if it’s the last node).

As opposed to an array, linked lists do not allocate memory in contiguous locations. Instead every node points to the next, creating a chained structure. This is because linked lists can increase or decrease in size without needing to move anything in memory, making them more dynamic.

Types of Linked Lists

It has multiple varieties, each for a different use case. Let us discuss the three main types of linked lists with their descriptions and code snippets.

Singly Linked List

In a singly linked list each node points to the next node. Each list node consists of two pieces of data and a link to the next node. The pointer of the last node points to null, which denotes the end of the list.

Characteristics:

• One-way (traverse in one direction only).
• Simple to implement.

JavaScript Implementation:

Code:

Output:

 10 20 30 

Doubly Linked List

Doubly linked list is the enhanced version of the singly linked list with the additional pointer. Each Node comprises three components:

1. Data
2. A pointer to the next node
3. Pointer for the previous node

Characteristics:

• Bidirectional traversal (can traverse in both forward and reverse direction).
• More flexible but it needs another memory for the additional pointer.

JavaScript Implementation:

Code:

Output:

 10 20 30 30 20 10 

Circular Linked List

For circular linked list, instead of a null reference for the last node, it points to the first node and thus becomes a circular chain. Circular linked lists, as in other linked lists, can be unidirectional (singly connected) or bidirectional (doubly connected).

Characteristics:

• The list has no null references.
• Good for use cases where a circular flow is needed (like round-robin scheduling).

JavaScript Implementation (Singly Circular):

Code:

Output:

 10 20 30 

Key Differences between Linked Lists and Arrays

Advantages of Linked Lists

1. Dynamic Size: A linked list has a dynamic size unlike an array, which is of fixed size.
2. Efficient Insertions/Deletions: It requires only O(1) time complexity for inserting or deleting from the head/ tail of a linked list, because we only need to change some pointers by adding and removing from the list.
3. Memory Utilization: Since linked lists don’t need contiguous blocks of memory, they can be used for dynamic memory allocation.
4. Ease of Implementation for Queues/Stacks: Linked lists can be used in the implementation of other data structures like queues and stacks.

Disadvantages of Linked Lists

1. Sequential Access: Elements in a linked list are accessed by starting at the head node and its complexity is (O(n)) whereas elements in an array are accessed randomly and it have the complexity (O(1)).
2. Memory Overhead: Each node contains an extra pointer/reference, making it more memory-intensive than arrays.
3. Complex Operations: Accessing, searching or traversing the list is slower and more complex than Arrays.
4. Cache Performance: The elements of a linked list are scattered randomly throughout memory, leading to poor cache performance.

Conclusion

Linked lists are a very flexible and dynamic data structure that serves as the basic building blocks for a number of advanced algorithms and systems. Despite needing more memory for pointers and having slower access times than arrays, their dynamicity makes them uniquely powerful for situations involving frequent adding and removing elements. Thus learning singly, doubly and circular linked lists can help in developing applications very efficient and robust way in JavaScript.