Linked Lists: Singly & Doubly Linked

Links To Code:

// Linked Lists - Singly & Doubly Linked - Greg Hogg DSA Course Materials Lecture 3


#include <iostream>
#include <string>

class SinglyNode {
public:
    int val;
    SinglyNode* next;

    SinglyNode(int val, SinglyNode* next = nullptr) : val(val), next(next) {}

    std::string toString() const {
        return std::to_string(val);
    }
};

class DoublyNode {
public:
    int val;
    DoublyNode* next;
    DoublyNode* prev;

    DoublyNode(int val) : val(val), next(nullptr), prev(nullptr) {}

    std::string toString() const {
        return std::to_string(val);
    }
};

void display(SinglyNode* head) {
    SinglyNode* curr = head;
    std::cout << "Singly linked list: ";
    while (curr) {
        std::cout << curr->val << " -> ";
        curr = curr->next;
    }
    std::cout << "null" << std::endl;
}

bool search(SinglyNode* head, int val) {
    SinglyNode* curr = head;
    while (curr) {
        if (curr->val == val) return true;
        curr = curr->next;
    }
    return false;
}

void display(DoublyNode* head) {
    DoublyNode* curr = head;
    std::cout << "Doubly linked list: ";
    while (curr) {
        std::cout << curr->val << " <-> ";
        curr = curr->next;
    }
    std::cout << "null" << std::endl;
}

DoublyNode* insertAtBeginning(DoublyNode* head, DoublyNode*& tail, int val) {
    DoublyNode* newNode = new DoublyNode(val);
    newNode->next = head;
    if (head) head->prev = newNode;
    else tail = newNode;
    return newNode;
}

DoublyNode* insertAtEnd(DoublyNode* head, DoublyNode*& tail, int val) {
    DoublyNode* newNode = new DoublyNode(val);
    if (tail) {
        tail->next = newNode;
        newNode->prev = tail;
    } else {
        head = newNode;
    }
    tail = newNode;
    return head;
}

int main() {
    // Singly Linked List
    SinglyNode* head = new SinglyNode(1);
    SinglyNode* A = new SinglyNode(3);
    SinglyNode* B = new SinglyNode(4);
    SinglyNode* C = new SinglyNode(7);

    head->next = A;
    A->next = B;
    B->next = C;

    std::cout << "Head of the list: " << head->toString() << std::endl;
    std::cout << "Traversing the singly linked list: ";
    display(head);

    int searchValue = 7;
    bool found = search(head, searchValue);
    std::cout << "Search for value " << searchValue << " in list: " << (found ? "true" : "false") << std::endl;

    // Doubly Linked List
    DoublyNode* headD = new DoublyNode(1);
    DoublyNode* tailD = headD;
    std::cout << "Head of the doubly linked list: " << headD->toString() << std::endl;
    display(headD);

    headD = insertAtBeginning(headD, tailD, 3);
    display(headD);

    headD = insertAtEnd(headD, tailD, 7);
    display(headD);

    return 0;
}

// Linked Lists - Singly & Doubly Linked - Greg Hogg DSA Course Materials Lecture 3


// Singly Linked Lists

class SinglyNode {
    int val;
    SinglyNode next;

    SinglyNode(int val, SinglyNode next) {
        this.val = val;
        this.next = next;
    }

    SinglyNode(int val) {
        this(val, null);
    }

    public String toString() {
        return Integer.toString(val);
    }
}

public class Main {
    public static void main(String[] args) {
        SinglyNode head = new SinglyNode(1);
        SinglyNode A = new SinglyNode(3);
        SinglyNode B = new SinglyNode(4);
        SinglyNode C = new SinglyNode(7);

        head.next = A;
        A.next = B;
        B.next = C;

        System.out.println("Head of the list: " + head); // Output: 1

        // Traverse the list - O(n)
        SinglyNode curr = head;
        System.out.println("Traversing the singly linked list:");
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();

        // Display linked list - O(n)
        display(head);

        // Search for node value - O(n)
        int searchValue = 7;
        boolean found = search(head, searchValue);
        System.out.println("Search for value " + searchValue + " in list: " + found);

        // Doubly Linked Lists
        DoublyNode headD = new DoublyNode(1);
        DoublyNode tailD = headD;
        System.out.println("Head of the doubly linked list: " + tailD); // Output: 1

        // Display - O(n)
        display(headD);

        // Insert at beginning - O(1)
        headD = insertAtBeginning(headD, tailD, 3);
        display(headD);

        // Insert at end - O(1)
        tailD = insertAtEnd(headD, tailD, 7);
        display(headD);
    }

    // Display singly linked list - O(n)
    static void display(SinglyNode head) {
        SinglyNode curr = head;
        StringBuilder elements = new StringBuilder();
        while (curr != null) {
            elements.append(curr.val).append(" -> ");
            curr = curr.next;
        }
        elements.append("null");
        System.out.println("Singly linked list: " + elements);
    }

    // Search for node value in singly linked list - O(n)
    static boolean search(SinglyNode head, int val) {
        SinglyNode curr = head;
        while (curr != null) {
            if (curr.val == val) {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }

    // Doubly Linked Lists
    static class DoublyNode {
        int val;
        DoublyNode next, prev;

        DoublyNode(int val) {
            this.val = val;
        }

        public String toString() {
            return Integer.toString(val);
        }
    }

    // Display doubly linked list - O(n)
    static void display(DoublyNode head) {
        DoublyNode curr = head;
        StringBuilder elements = new StringBuilder();
        while (curr != null) {
            elements.append(curr.val).append(" <-> ");
            curr = curr.next;
        }
        elements.append("null");
        System.out.println("Doubly linked list: " + elements);
    }

    // Insert at beginning of doubly linked list - O(1)
    static DoublyNode insertAtBeginning(DoublyNode head, DoublyNode tail, int val) {
        DoublyNode newNode = new DoublyNode(val);
        newNode.next = head;
        if (head != null) {
            head.prev = newNode;
        }
        return newNode;
    }

    // Insert at end of doubly linked list - O(1)
    static DoublyNode insertAtEnd(DoublyNode head, DoublyNode tail, int val) {
        DoublyNode newNode = new DoublyNode(val);
        newNode.prev = tail;
        if (tail != null) {
            tail.next = newNode;
        }
        return newNode;
    }
}

// Linked Lists - Singly & Doubly Linked - Greg Hogg DSA Course Materials Lecture 3

// Singly Linked Lists
class SinglyNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }

toString() {
        return this.val.toString();
    }
}

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

// Add a new node at the end
    append(val) {
        if (!this.head) {
            this.head = new SinglyNode(val);
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = new SinglyNode(val);
        }
    }

// Display linked list - O(n)
    display() {
        let elements = "";
        let current = this.head;
        while (current) {
            elements += current.val + " -> ";
            current = current.next;
        }
        elements += "null";
        console.log("Singly linked list: " + elements);
    }

// Search for node value - O(n)
    search(val) {
        let current = this.head;
        while (current) {
            if (current.val === val) {
                return true;
            }
            current = current.next;
        }
        return false;
    }
}

// Doubly Linked Lists
class DoublyNode {
    constructor(val) {
        this.val = val;
        this.next = null;
        this.prev = null;
    }

toString() {
        return this.val.toString();
    }
}

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

// Insert at beginning - O(1)
    insertAtBeginning(val) {
        const newNode = new DoublyNode(val);
        if (this.head) {
            newNode.next = this.head;
            this.head.prev = newNode;
        }
        this.head = newNode;
        if (!this.tail) {
            this.tail = newNode;
        }
    }

// Insert at end - O(1)
    insertAtEnd(val) {
        const newNode = new DoublyNode(val);
        if (this.tail) {
            this.tail.next = newNode;
            newNode.prev = this.tail;
        }
        this.tail = newNode;
        if (!this.head) {
            this.head = newNode;
        }
    }

// Display doubly linked list - O(n)
    display() {
        let elements = "";
        let current = this.head;
        while (current) {
            elements += current.val + " <-> ";
            current = current.next;
        }
        elements += "null";
        console.log("Doubly linked list: " + elements);
    }
}

// Example Usage
const singlyList = new SinglyLinkedList();
singlyList.append(1);
singlyList.append(3);
singlyList.append(4);
singlyList.append(7);
console.log("Head of the list: " + singlyList.head);
singlyList.display();

const searchValue = 7;
const found = singlyList.search(searchValue);
console.log("Search for value " + searchValue + " in list: " + found);

const doublyList = new DoublyLinkedList();
doublyList.insertAtBeginning(1);
console.log("Head of the doubly linked list: " + doublyList.head);
doublyList.display();

doublyList.insertAtBeginning(3);
doublyList.display();

doublyList.insertAtEnd(7);
doublyList.display();

Summary

Linked lists are dynamic data structures made of nodes that store values and pointers. Singly linked lists link nodes in one direction, while doubly linked lists have forward and backward links. They are ideal for applications where elements are frequently added or removed from the front or back without the overhead of resizing or shifting elements like in arrays.

Linked Lists: Singly & Doubly Linked

A linked list is a linear data structure where each element (called a node) contains a value and a reference to the next node in the sequence. This differs from arrays, which store elements in contiguous memory. Linked lists allow for efficient insertions and deletions, especially at the beginning or end.

Singly vs Doubly Linked Lists

In a singly linked list, each node points only to the next node, enabling forward traversal. A doubly linked list extends this by allowing each node to also reference its previous node, enabling bidirectional traversal.

Common Operations

Insertion: Adding a node at the head or tail — O(1)
Search: Traverse nodes until value is found — O(n)
Deletion: Remove node by value or position — O(n)

Use Cases

Linked lists are useful in implementing stacks, queues, and adjacency lists in graphs. They're also common in scenarios where memory reallocation is costly or predictable indexing isn’t required.

Conclusion

Mastering linked lists teaches you how memory is handled under the hood and prepares you for more advanced pointer-based structures like trees and graphs. They're also a popular topic in coding interviews due to the logic-heavy operations they require.

Linked Lists in Data Structures: Singly vs Doubly Linked Lists

Linked lists are a fundamental data structure in computer science, providing a dynamic alternative to arrays for storing data. Unlike arrays, linked lists consist of individual nodes connected via pointers, allowing for flexible memory usage and efficient insertions and deletions.

Singly Linked Lists

A singly linked list is composed of nodes, where each node contains:

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

The list starts with a special node called the head, and the end of the list is marked by a node whose next pointer is null or None. Nodes are stored at distinct memory locations (i.e., not contiguous like arrays).

Common Operations in Singly Linked Lists

Insert at Head: O(1) – Create a new node and point it to the current head.
Delete at Head: O(1) – Simply move the head pointer to the next node.
Insert at Position: O(n) – Requires traversal to the position before insertion.
Delete at Position: O(n) – Requires traversal to adjust the previous node’s next pointer.
Search (Lookup): O(n) – Traverse from the head until the value is found.

Limitations of Singly Linked Lists

No direct access to previous nodes (only forward traversal).
Deletion of a node is not O(1) unless the previous node is known.
Must always traverse from the head, leading to O(n) time for most operations.

Doubly Linked Lists

A doubly linked list enhances the singly linked list by adding an additional pointer to each node. Each node contains:

Value: The data stored in the node.
Next Pointer: A reference to the next node.
Previous Pointer: A reference to the previous node.

The head node's prev pointer is null, and the tail node’s next pointer is null. Doubly linked lists support bidirectional traversal, making them more flexible in certain applications.

Common Operations in Doubly Linked Lists

Insert at Head or Tail: O(1) – Direct manipulation using head or tail pointers.
Delete Node (with reference): O(1) – Efficient since both prev and next are accessible.
Search from Head or Tail: O(n) – Traverse from either end until the value is found.

Advantages of Doubly Linked Lists

Support for two-way traversal.
Efficient deletion if node reference is known.
Insertions at both ends are straightforward and fast.

Trade-offs of Doubly Linked Lists

Requires more memory per node due to the additional pointer.
More complex implementation and maintenance of node links.

Linked List Implementation in Python

Both singly and doubly linked lists can be implemented using Python classes. Each Node class typically includes:

Singly Linked List Node: Attributes: value, next
Doubly Linked List Node: Attributes: value, next, prev

Basic Patterns in Linked List Code

Creating nodes and linking via node.next = next_node
Traversal using a temporary pointer like curr = head
Updating links carefully to avoid breaking the list structure

Singly vs Doubly Linked List: Comparison

Feature	Singly Linked List	Doubly Linked List
Direction	Forward only	Forward and backward
Memory per Node	Lower (1 pointer)	Higher (2 pointers)
Deletion with Reference	O(n)	O(1)
Insert at Head/Tail	Head: O(1), Tail: O(n)	Head & Tail: O(1)
Traversal Flexibility	One direction only	Two-way traversal

Conclusion

Singly linked lists and doubly linked lists are core components in the study of data structures. They offer flexible alternatives to arrays, particularly for applications requiring frequent insertions or deletions. Understanding their structure, operations, and time complexity is essential for mastering algorithms in Python and other programming languages.

Get Personalized Lessons at AlgoMap Bootcamp 💡