Linked Lists: A Comprehensive Guide and Detailed Implementation with JavaScript

Abstract

This article provides an in-depth tutorial on linked lists, a fundamental data structure in computer science. Linked lists allow for dynamic memory allocation and offer efficient insertion and deletion operations. This guide explores the conceptual understanding, operations, and detailed implementation of linked lists, complete with a Big O analysis for each operation. Detailed explanations of each line of code within the LinkedList class methods are provided, along with practical examples to illustrate their usage. By the end of this guide, readers will have a thorough understanding of linked lists and their implementation in JavaScript, making it easier to apply this knowledge in various software development scenarios.

Introduction

Linked lists are a versatile data structure that allows for efficient dynamic memory management. Unlike arrays, linked lists do not require contiguous memory allocation, making them ideal for situations where the size of the data set is unknown or changes dynamically. This article aims to provide a comprehensive overview of linked lists, starting from their structure to detailed explanations of each method used in their implementation.

Linked Lists vs. Arrays

Arrays are a commonly used data structure in programming, characterized by their contiguous memory allocation and ability to access elements via indices. However, arrays come with limitations, such as fixed size and costly insertion and deletion operations when elements need to be added or removed from the middle.

Linked lists, on the other hand, consist of nodes where each node contains a value and a pointer to the next node in the sequence. This non-contiguous memory allocation allows linked lists to grow and shrink dynamically, offering flexibility that arrays lack. However, accessing elements in a linked list requires traversal from the head, making certain operations less efficient compared to arrays.

Key Differences:

• Contiguous Memory: Arrays have contiguous memory allocation, while linked lists do not.
• Indices: Arrays allow direct access to elements via indices, while linked lists require traversal.
• Dynamic Size: Linked lists can easily grow or shrink, whereas arrays have a fixed size unless reallocated.

Structure of a Linked List

A linked list is composed of nodes, where each node has two main components:

• Value: The data stored in the node.
• Pointer (Next): A reference to the next node in the list.

In a linked list, two pointers are typically maintained:

• Head: Points to the first node in the list.
• Tail: Points to the last node in the list, which terminates with a null pointer.

Node Class

Before we explore the methods of the LinkedList class, it's essential to understand the Node class.

class Node {

    constructor(value) {

        this.value = value;

        this.next = null;

    }

}        

Explanation:

• constructor(value): This method initializes a new node. It takes one argument, value, which is the data stored in the node. The next property is set to null because when a node is created, it doesn't point to any other node yet.

Example:

const node = new Node(4);        

console.log(node); // Node { value: 4, next: null }        

Here, a node is created with the value 4, and since it doesn’t point to any other node, next is null.

Detailed Explanation of Linked List Methods

Each method in the LinkedList class is designed to perform a specific operation on the linked list. Below, we will delve into the purpose of each line of code within these methods, providing examples and explaining why certain approaches are used.

LinkedList Constructor

class LinkedList {

    constructor(value) {

        const newNode = new Node(value);

        this.head = newNode;

        this.tail = newNode;

        this.length = 1;

    }
}        

Explanation:

• constructor(value): This method initializes the linked list. It creates a new node with the given value, sets both the head and tail of the list to this node, and initializes the list length to 1.

Example:

const list = new LinkedList(4);        

console.log(list);?        

// LinkedList { head: Node { value: 4, next: null }, tail: Node { value: 4, next: null }, length: 1 }        

Here, a linked list is created with a single node containing the value 4. The head and tail both point to this node, and the list length is 1.

Push Method

push(value) {

    const newNode = new Node(value);

    if (!this.head) {

        this.head = newNode;

        this.tail = newNode;

    } else {

        this.tail.next = newNode;

        this.tail = newNode;

    }

    this.length++;

    return this;

}        

Explanation:

• const newNode = new Node(value);: A new node is created with the provided value.
• if (!this.head) { ... } else { ... }: This conditional checks if the list is empty (i.e., head is null). If the list is empty, both head and tail are set to the new node. If not, the next pointer of the current tail is updated to point to the new node, and then tail is updated to this new node.
• this.length++;: The length of the list is incremented by one.
• return this;: The entire linked list object is returned, allowing method chaining.

Example:

list.push(5);        

console.log(list);        

// LinkedList { head: Node { value: 4, next: Node { value: 5, next: null } }, tail: Node { value: 5, next: null }, length: 2 }        

After pushing the value 5 to the list, the new node is added to the end, the tail now points to this new node, and the list length is updated to 2.

Why Use It?: The push method is essential for adding elements to the end of the list efficiently in O(1) time.

Pop Method

pop() {

    if (!this.head) return undefined;

    let temp = this.head;

    let pre = this.head;

    while (temp.next) {

        pre = temp;

        temp = temp.next;

    }
    this.tail = pre;

    this.tail.next = null;

    this.length--;

    if (this.length === 0) {

        this.head = null;

        this.tail = null;

    }

    return temp;
}        

Explanation:

• if (!this.head) return undefined;: If the list is empty, undefined is returned since there's nothing to pop.
• let temp = this.head; let pre = this.head;: temp and pre are both initialized to head. temp will be used to traverse the list, while pre will follow one node behind temp.
• while (temp.next) { ... }: This loop traverses the list until temp reaches the last node. pre will point to the second-to-last node when the loop finishes.
• this.tail = pre; this.tail.next = null;: tail is updated to pre, and tail.next is set to null, effectively removing the last node.
• this.length--;: The list length is decremented by one.
• if (this.length === 0) { ... }: If the list becomes empty after the pop, both head and tail are set to null.
• return temp;: The removed node is returned.

Example:

list.pop();        

console.log(list);        

// LinkedList { head: Node { value: 4, next: null }, tail: Node { value: 4, next: null }, length: 1 }        

After popping, the last node (with value 5) is removed, the tail now points to the node with value 4, and the list length is 1.

Why Use It?: The pop method efficiently removes the last element in O(n) time (due to the need to traverse the list) and is useful for stack implementations.

Unshift Method

unshift(value) {

    const newNode = new Node(value);

    if (!this.head) {

        this.head = newNode;

        this.tail = newNode;

    } else {

        newNode.next = this.head;

        this.head = newNode;

    }
    this.length++;
    return this;
}        

Explanation:

• const newNode = new Node(value);: A new node is created with the provided value.
• if (!this.head) { ... } else { ... }: If the list is empty, both head and tail are set to the new node. Otherwise, newNode.next is set to the current head, and then head is updated to newNode.
• this.length++;: The length of the list is incremented by one.
• return this;: The linked list object is returned for chaining.

Example:

list.unshift(3);        

console.log(list);        

// LinkedList { head: Node { value: 3, next: Node { value: 4, next: null } }, tail: Node { value: 4, next: null }, length: 2 }        

After unshifting, a new node with value 3 is added to the start of the list, and the list length is updated to 2.

Why Use It?: The unshift method efficiently adds elements to the beginning of the list in O(1) time, useful for queue implementations.

Shift Method

shift() {

    if (!this.head) return undefined;

    let temp = this.head;

    this.head = this.head.next;

    this.length--;

    if (this.length === 0) {

        this.tail = null;

    }
    return temp;
}        

Explanation:

• if (!this.head) return undefined;: If the list is empty, undefined is returned.
• let temp = this.head;: temp is used to store the current head before moving it.
• this.head = this.head.next;: head is updated to the next node in the list.
• this.length--;: The length of the list is decremented by one.
• if (this.length === 0) { ... }: If the list becomes empty, tail is set to null.
• return temp;: The removed node is returned.

Example:

list.shift();        

console.log(list);        

// LinkedList { head: Node { value: 4, next: null }, tail: Node { value: 4, next: null }, length: 1 }        

After shifting, the first node (with value 3) is removed, and the head now points to the node with value 4.

Why Use It?: The shift method removes the first element in O(1) time, which is essential for implementing queues.

Get Method

get(index) {
    if (index < 0 || index >= this.length) return undefined;
    let temp = this.head;
    for (let i = 0; i < index; i++) {
        temp = temp.next;
    }
    return temp;
}        

Explanation:

• if (index < 0 || index >= this.length) return undefined;: This line checks if the given index is out of bounds (i.e., either less than 0 or greater than or equal to the length of the list). If it is out of bounds, the method returns undefined.
• let temp = this.head;: A temporary variable temp is initialized to point to the head of the list. This variable will be used to traverse the list.
• for (let i = 0; i < index; i++) { temp = temp.next; }: This loop iterates through the list until temp points to the node at the specified index. During each iteration, temp is updated to point to the next node in the list.
• return temp;: After the loop completes, temp should be pointing to the node at the desired index. This node is then returned.

Example:

const node = list.get(1);        

console.log(node); // Node { value: 4, next: null }        

In this example, the get(1) method retrieves the node at index 1. If the list has the structure Node { value: 3, next: Node { value: 4, next: null } }, it will return the node with value 4.

Why Use It?: The get method is essential for accessing elements at specific indices within the list. Though it operates in O(n) time due to the need to traverse the list, it is a straightforward and efficient way to retrieve a node by its position.

Set Method

set(index, value) {
    let temp = this.get(index);
    if (temp) {
        temp.value = value;
        return true;
    }
    return false;
}        

Explanation:

• let temp = this.get(index);: This line uses the get method to retrieve the node at the specified index and assigns it to the temp variable.
• if (temp) { temp.value = value; return true; }: If temp is not null (meaning the node was found at the specified index), this line updates the node's value with the new value provided and returns true to indicate success.
• return false;: If the node does not exist at the specified index (i.e., temp is null), the method returns false to indicate that the update was unsuccessful.

Example:

list.set(1, 10);        

console.log(list.get(1)); // Node { value: 10, next: null }        

In this example, the set(1, 10) method sets the value of the node at index 1 to 10. The node's value is then updated accordingly.

Why Use It?: The set method is useful for updating the value of a node at a specific index, without altering the list's structure. It allows for efficient in-place modifications to the list.

Insert Method

insert(index, value) {

    if (index < 0 || index > this.length) return false;

    if (index === 0) return this.unshift(value);

    if (index === this.length) return this.push(value);

    const newNode = new Node(value);

    const temp = this.get(index - 1);

    newNode.next = temp.next;

    temp.next = newNode;

    this.length++;

    return true;

}        

Explanation:

• if (index < 0 || index > this.length) return false;: This line checks if the index is out of bounds (either negative or greater than the length of the list). If it is out of bounds, the method returns false.
• if (index === 0) return this.unshift(value);: If the index is 0, the new value is inserted at the beginning of the list using the unshift method.
• if (index === this.length) return this.push(value);: If the index is equal to the length of the list, the new value is inserted at the end of the list using the push method.
• const newNode = new Node(value);: A new node is created with the given value.
• const temp = this.get(index - 1);: The node immediately before the desired insertion point is retrieved using the get method.
• newNode.next = temp.next; temp.next = newNode;: The new node is inserted into the list by adjusting the pointers: the new node's next pointer is set to point to the node that was originally after temp, and then temp.next is set to point to the new node.
• this.length++;: The length of the list is incremented by one.
• return true;: The method returns true to indicate that the insertion was successful.

Example:

list.insert(1, 7);        

console.log(list.get(1)); // Node { value: 7, next: Node { value: 4, next: null } }        

In this example, the insert(1, 7) method inserts a node with the value 7 at index 1, shifting the original node at index 1 to index 2.

Why Use It?: The insert method allows for flexible insertion of elements at any position within the list. It is especially useful when you need to insert an element in the middle of the list, maintaining the order of the existing elements.

Remove Method

remove(index) {

    if (index < 0 || index >= this.length) return undefined;

    if (index === 0) return this.shift();

    if (index === this.length - 1) return this.pop();

    const before = this.get(index - 1);

    const temp = before.next;

    before.next = temp.next;

    temp.next = null;

    this.length--;

    return temp;

}        

Explanation:

• if (index < 0 || index >= this.length) return undefined;: This line checks if the index is out of bounds. If so, it returns undefined, indicating that there is no element to remove at the specified index.
• if (index === 0) return this.shift();: If the index is 0, the shift method is called to remove the first element of the list.
• if (index === this.length - 1) return this.pop();: If the index is the last position in the list, the pop method is called to remove the last element.
• const before = this.get(index - 1);: Retrieves the node immediately before the node to be removed.
• const temp = before.next;: Stores the node to be removed in temp.
• before.next = temp.next;: Bypasses the

node to be removed by setting the next pointer of the before node to the node after temp.

• temp.next = null;: Removes the next reference from temp, effectively isolating it from the list.
• this.length--;: The length of the list is decremented by one.
• return temp;: The removed node is returned.

Example:

list.remove(1);        

console.log(list.get(1)); // Node { value: 4, next: null }        

In this example, the remove(1) method removes the node at index 1. The list is updated, and the removed node is returned.

Why Use It?: The remove method is crucial for dynamically managing the contents of the list, allowing nodes to be removed from any position. It ensures that the list structure remains intact after the removal.

Reverse Method

reverse() {

    let temp = this.head;

    this.head = this.tail;

    this.tail = temp;

    let next = null;

    let prev = null;

    for (let i = 0; i < this.length; i++) {

        next = temp.next;

        temp.next = prev;

        prev = temp;

        temp = next;

    }

    return this;

}        

Explanation:

• let temp = this.head;: Initializes a temporary variable temp to start at the head of the list.
• this.head = this.tail; this.tail = temp;: Swaps the head and tail of the list, which is the first step in reversing the list.
• let next = null; let prev = null;: Initializes two additional variables, next and prev, to help with the reversal process.
• for (let i = 0; i < this.length; i++) { ... }: A loop that iterates through the entire list, reversing the direction of the pointers.
• next = temp.next;: Stores the next node in the list to keep track of it before changing the pointer.
• temp.next = prev;: Reverses the pointer of the current node to point to the previous node.
• prev = temp;: Moves the prev pointer forward to the current node.
• temp = next;: Advances the temp pointer to the next node in the original sequence.
• return this;: Returns the reversed list.

Example:

list.reverse();        

console.log(list);        

// LinkedList { head: Node { value: 4, next: Node { value: 3, next: null } }, tail: Node { value: 3, next: null }, length: 2 }        

In this example, the reverse() method reverses the order of the nodes in the list.

Why Use It?: The reverse method is a common operation in algorithms that require reversing the order of elements. It is also a popular interview question due to the complexity involved in manipulating pointers during the reversal process.

Complete LinkedList Class

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    constructor(value) {
        const newNode = new Node(value);
        this.head = newNode;
        this.tail = newNode;
        this.length = 1;
    }

    push(value) {
        const newNode = new Node(value);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }

    pop() {
        if (!this.head) return undefined;
        let temp = this.head;
        let pre = this.head;
        while (temp.next) {
            pre = temp;
            temp = temp.next;
        }
        this.tail = pre;
        this.tail.next = null;
        this.length--;
        if (this.length === 0) {
            this.head = null;
            this.tail = null;
        }
        return temp;
    }

    unshift(value) {
        const newNode = new Node(value);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }

    shift() {
        if (!this.head) return undefined;
        let temp = this.head;
        this.head = this.head.next;
        this.length--;
        if (this.length === 0) {
            this.tail = null;
        }
        return temp;
    }

    get(index) {
        if (index < 0 || index >= this.length) return undefined;
        let temp = this.head;
        for (let i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    set(index, value) {
        let temp = this.get(index);
        if (temp) {
            temp.value = value;
            return true;
        }
        return false;
    }

    insert(index, value) {
        if (index < 0 || index > this.length) return false;
        if (index === 0) return this.unshift(value);
        if (index === this.length) return this.push(value);

        const newNode = new Node(value);
        const temp = this.get(index - 1);
        newNode.next = temp.next;
        temp.next = newNode;
        this.length++;
        return true;
    }

    remove(index) {
        if (index < 0 || index >= this.length) return undefined;
        if (index === 0) return this.shift();
        if (index === this.length - 1) return this.pop();

        const before = this.get(index - 1);
        const temp = before.next;
        before.next = temp.next;
        temp.next = null;
        this.length--;
        return temp;
    }

    reverse() {
        let temp = this.head;
        this.head = this.tail;
        this.tail = temp;
        let next = null;
        let prev = null;
        for (let i = 0; i < this.length; i++) {
            next = temp.next;
            temp.next = prev;
            prev = temp;
            temp = next;
        }
        return this;
    }
}
        

This complete class, LinkedList, encapsulates all the fundamental operations needed for managing a singly linked list, making it a versatile and essential data structure in various programming scenarios.

Conclusion

Linked lists are a fundamental data structure that provides efficient dynamic memory management. Each method in the LinkedList class serves a specific purpose, whether it’s adding, removing, accessing, or modifying nodes. The detailed explanations and examples provided here illustrate the practical use of each method and reinforce the importance of understanding linked lists as a core component of data structures and algorithms.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Goodrich, M. T., & Tamassia, R. (2014). Data Structures and Algorithms in Java (6th ed.). Wiley.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.