Implementing a Singly Linked List

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Understanding Singly Linked Lists

A linked list is a data structure that represents a sequence of nodes. In a singly linked list, each node points to the next node.

In memory, these nodes do not need to be sorted contiguously (adjacent to one another) since we are not relying on indexing. When we iterate through a linked list, we pass through each reference of a node until we hit a null pointer.

Structure of a Node

In a singly linked list, each node typically contains two fields:

data: the value or information contained in the node
next: the reference (pointer) to the next node in the list

Head and Tail Pointers

The head is a reference to the first node in the list. It is essential because it allows access to the linked list’s start. It sometimes acts as a sentinel node (placed before the actual head node) for easier operations like inserting at the head. The tail is a reference to the last node in the list. It’s next pointer is null indicating the end of the list.

Memory Efficiency of Insertions/Deletions

Compared to arrays, linked lists are more memory efficient in terms of insertion/deletion since these operations do not require “shifting” of elements. The operation of adding or removing an element from anywhere in a linked list takes $O(1)$ time. However, it takes $O(n)$ time in the worst case to traverse through the linked list to then add/remove an element (does not apply for adding/removing first element).

It's worth pointing out that linked lists have extra memory overhead due to the storage of pointers along with data in each node.

Time Complexity Analysis

Insertion:

at beginning or end (with head/tail pointers) → $O(1)$
at specific position (due to traversal) → $O(n)$

Deletion:

at beginning → $O(1)$
at end → $O(n)$
at specific position → $O(n)$

Traversal/Search: $O(n)$

JavaScript Implementation

Classical OOP

class ListNode {
    constructor(val, nextNode = null) {
        this.val = val;
        this.next = nextNode;
    }
}

class LinkedList {
    constructor() {
        // sentinel node for easy operations on head
        this.head = new ListNode(-1);
        this.tail = this.head;
    }

    // get the value at the specified index.
    get(index) {
        let curr = this.head.next;
        let i = 0;
        while (curr !== null) {
            if (i === index) return curr.val;
            curr = curr.next;
            i++;
        }
        return -1;
    }

    // insert a new value at the head of the list.
    insertHead(val) {
        const newNode = new ListNode(val);
        newNode.next = this.head.next;
        this.head.next = newNode;
        if (newNode.next === null) {
            this.tail = newNode;
        }
    }

    // insert a new value at the tail of the list.
    insertTail(val) {
        const newNode = new ListNode(val);
        this.tail.next = newNode;
        this.tail = newNode;
    }

    // remove the node at the specified index.
    remove(index) {
        let curr = this.head;
        let i = 0;
        while (i < index && curr.next !== null) {
            i++;
            curr = curr.next;
        }

        if (curr !== null && curr.next !== null) {
            if (curr.next === this.tail) this.tail = curr;
            curr.next = curr.next.next;
            return true;
        }
        return false;
    }

    // get all values in the list as an array.
    getValues() {
        const values = [];
        let curr = this.head.next;
        while (curr !== null) {
            values.push(curr.val);
            curr = curr.next;
        }
        return values;
    }

    // get the length of the list.
    length() {
        let length = 0;
        let curr = this.head.next;
        while (curr !== null) {
            length++;
            curr = curr.next;
        }
        return length;
    }
}

Prototype-Based OOP

function ListNode(val, nextNode = null) {
    this.val = val;
    this.next = nextNode;
}

function LinkedList() {
    this.head = new ListNode(-1); // Sentinel node
    this.tail = this.head;
}

// get the value at the specified index
LinkedList.prototype.get = function(index) {
    let curr = this.head.next;
    let i = 0;
    while (curr !== null) {
        if (i === index) return curr.val;
        curr = curr.next;
        i++;
    }
    return -1;
};

// insert a new value at the head of the list
LinkedList.prototype.insertHead = function(val) {
    const newNode = new ListNode(val);
    newNode.next = this.head.next;
    this.head.next = newNode;
    if (newNode.next === null) {
        this.tail = newNode;
    }
};

// insert a new value at the tail of the list
LinkedList.prototype.insertTail = function(val) {
    const newNode = new ListNode(val);
    this.tail.next = newNode;
    this.tail = newNode;
};

// remove the node at the specified index
LinkedList.prototype.remove = function(index) {
    let curr = this.head;
    let i = 0;
    while (i < index && curr.next !== null) {
        i++;
        curr = curr.next;
    }

    if (curr !== null && curr.next !== null) {
        if (curr.next === this.tail) this.tail = curr;
        curr.next = curr.next.next;
        return true;
    }
    return false;
};

// get all values in the list as an array
LinkedList.prototype.getValues = function() {
    const values = [];
    let curr = this.head.next;
    while (curr !== null) {
        values.push(curr.val);
        curr = curr.next;
    }
    return values;
};

// get the length of the list
LinkedList.prototype.length = function() {
    let length = 0;
    let curr = this.head.next;
    while (curr !== null) {
        length++;
        curr = curr.next;
    }
    return length;
};

Blog