Linked Lists

A linked list is a linear data structure consisting of nodes. Each node contains a data element and a reference to the next node in the sequence.

Linked lists are implemented using objects.

// Definition of a Linked List Node.
class Node {
    constructor(data){
        this.data = data;
        this.next = null;
    }
}

Types of Linked Lists

1. Singly Linked List: Each node contains a data element and a reference to the next node in the sequence.

2. Doubly Linked List: Each node contains references to both the next and previous nodes.

3. Circular Linked List: The last node points back to the first node, forming a circular structure.

Characteristics of Linked Lists

• A linked list uses extra memory to store links.

• Each node contains a data element and a reference (or pointer) to the next node in the sequence.

• The first node of a linked list is called the Head.

• The next reference of the last node always points to NULL.

• Unlike arrays, which require a predetermined size and allocate a fixed amount of memory - static memory allocation, linked lists can grow and shrink dynamically as elements are added or removed - dynamic memory allocation.

• Nodes can easily be added or removed from a linked list without reorganizing the entire data structure.

• Random access is not possible in linked lists; only sequential access is allowed. To find an element, the entire list must be traversed until the element is located or the end of the list is reached. As a result, search operations in linked lists tend to be slower compared to arrays.

Random access refers to the ability to access elements directly using their index or position in the data structure, as is possible in an array. In contrast, Sequential access means that the data structure must be traversed from the beginning to reach a specific element.

For example, accessing the 5th element in an array can be done in constant time O(1) because the memory address of the 5th element can be calculated directly. In a linked list, each node contains a reference to the next node but does not contain any information about the position of nodes relative to one another. This makes it impossible to jump directly to a node based on its index.

Implementing Linked Lists in JavaScript

Step 1: Define a Node

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

Step 2: Define a Linked List

Implementation of a basic singly linked list includes four essential functions.

1. append(data) : inserts a new node at the end of a linked list.

2. prepend(data) : inserts a new node at the beginning of a linked list.

3. delete(data) : removes the first occurrence of a node with the given data.

4. search(data) : finds the first occurrence of a node with the given data.

class LinkedList{
    constructor(){
        this.head = null;
    }

    //append: inserts a new node at the end of a linked list.
    append(data){
        const newNode = new Node(data);
        if(!this.head){ 
            this.head = newNode;
        }else{
            let current = this.head
            while (current.next !== null){
                current = current.next;
            }
            current.next = newNode;
        }
    }

    //prepend: inserts a new node at the beginning of a linked list.
    prepend(data){
        const newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
    }

    //delete: removes the first occurrence of a node with the given data.
    delete(data){
        if(!this.head){
            return; // list is empty
        }
        if(this.head.data === data){
            this.head = this.head.next;
            return;
        }
        let current = this.head;
        while(current.next !== null){
            if(current.next.data === data){
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    //search: finds the first occurrence of a node with the given data.
    search(data){
        let current = this.head;
        while(current !== null){
            if(current.data === data){
                return true; // data found
            }
            current = current.next;
        }
        return false; // data not found
    }
}

Complexity Analysis

Real-Life Applications of Linked Lists

• Music playlist management. Music applications often use linked lists to manage playlists. Each song represents a node in the list, allowing users to add, remove, or re-arrange songs dynamically.

• Browser history management. Web browsers also may use linked lists to manage the history of visited web pages. Each page can be a node, with links to the previous and next pages, enabling users to navigate back and forth easily.

---

And that, dear friends, wraps up our article on linked lists! Any thoughts and comments, would love to hear those.

Until next time, happy coding!🤠

P.S. The code demonstrating what has been covered in this article can be found on my Github repository here.

Credits:

• Cover photo by Joey Kyber