Unlocking the Power of Data Structures: A Deep Dive into Singly Linked Lists

Introduction

Data structures are essential components of computer programming that allow efficient storage and retrieval of data. One fundamental data structure is the linked list, which consists of nodes linked together by pointers. Mastering linked lists is crucial for understanding more complex data structures and algorithms.

What is a Linked List?

A linked list is a linear data structure where each node contains data and a pointer to the next node in the sequence. Unlike arrays, linked lists do not have a fixed size and can dynamically grow or shrink. This flexibility makes linked lists ideal for scenarios where the size of the data is unknown or frequently changing.

Singly Linked List

In a singly linked list, each node points to the next node in the sequence, forming a unidirectional chain. Traversing a singly linked list can only be done in one direction, starting from the head node.

Here’s a basic implementation of a singly linked list in JavaScript:

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

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

    // Add node to the end
    append(data) {
        let newNode = new Node(data);
        if (this.head === null) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next !== null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Print the linked list
    printList() {
        let current = this.head;
        while (current !== null) {
            console.log(current.data);
            current = current.next;
        }
    }

    // Sum of all node values
    sum() {
        let total = 0;
        let current = this.head;
        while (current !== null) {
            total += current.data;
            current = current.next;
        }
        return total;
    }

    // Find a value in the list
    find(value) {
        let current = this.head;
        while (current !== null) {
            if (current.data === value) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // Reverse the linked list
    reverse() {
        let prev = null;
        let current = this.head;
        let next = null;
        while (current !== null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        this.head = prev;
    }

    // Get node value at a specific position
    getNodeValue(position) {
        let current = this.head;
        let count = 0;
        while (current !== null) {
            if (count === position) {
                return current.data;
            }
            count++;
            current = current.next;
        }
        return null; // Return null if the position is out of bounds
    }
}

let list = new SinglyLinkedList();
list.append(1);
list.append(2);
list.append(3);
list.printList();  // Output: 1 2 3

console.log("Sum of all nodes: ", list.sum());  // Output: 6
console.log("Finding value 2: ", list.find(2));  // Output: true
console.log("Finding value 4: ", list.find(4));  // Output: false

list.reverse();
list.printList();  // Output: 3 2 1

console.log("Node value at position 1: ", list.getNodeValue(1));  // Output: 2
console.log("Node value at position 3: ", list.getNodeValue(3));  // Output: null

Advantages of Singly Linked Lists

• Dynamic Size: They can grow or shrink dynamically.
• Easy Insertion and Deletion: Adding or removing nodes is efficient.
• No Wasted Memory: Memory is allocated as needed.

Disadvantages of Singly Linked Lists

• Slower Access: Accessing elements is slower compared to arrays.
• Extra Memory: Requires additional memory for pointers.
• Lack of Random Access: Directly accessing elements by index is not possible.

Conclusion

Mastering data structures like singly linked lists is a crucial step in becoming a proficient programmer. Understanding their characteristics, advantages, and disadvantages provides a solid foundation for tackling more complex algorithms and data structures in the future.

Stay tuned for our next articles where we’ll dive into doubly linked lists and circular linked lists, exploring their unique properties and use cases!