Day 31: Implementing Singly, Doubly & Circular Linked Lists from Scratch in Java | My DSA Journey – Linked List

---

🚀 Introduction

Welcome to Day 31 of my DSA Journey!
After wrapping up an intense few weeks on Recursion, I recently shifted gears into one of the most foundational data structures in DSA — the Linked List.

This shift from recursion to linked lists has been exciting, as both concepts are deeply connected — especially when it comes to problems involving traversal and pointer manipulation.

Over the past 3 days, I’ve worked on:
Singly Linked List
Doubly Linked List
Circular Linked List

Each with full CRUD operations including create, insert, delete, search, and traverse.

I’m documenting this journey publicly to stay consistent and to help others who are starting their own DSA path from scratch.

📅 Here’s What I Covered Over the Last 3 Days:

Day 28

• Implemented Singly Linked List

Day 29

• Implemented Doubly Linked List

Day 30

• Implemented Circular Linked List

Let’s break down each of these topics below 👇

---

1. Singly Linked List Implementation:

Here’s how I implemented a Singly Linked List from scratch in Java — including all the fundamental operations like insertion, deletion, traversal, and search.

Class Structure:

• head: Points to the first node.
• tail: Points to the last node.
• size: Tracks the number of nodes in the list.

public class LinkedList {
    private Node head;
    private Node tail;
    private int size;

    public LinkedList() {
        this.size = 0;
    }
}

Node Class (Inner Class):

• Represents a node in the list.
• Each node contains an integer value and a reference to the next node.

private static class Node {
    int value;
    Node next;

    public Node(int value) {
        this.value = value;
    }

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}

Get Size of the List:

Returns the current number of nodes in the list.

public int getSize() {
    return size;
}

Insert at Beginning:

• Creates a new node.
• Points it to the current head.
• Updates head to the new node.
• If the list was empty, tail is also updated.

public void insertAtFirst(int val) {
    Node node = new Node(val);
    node.next = head;
    head = node;

    if (tail == null) {
        tail = head;
    }
    size++;
}

Insert at End:

• Adds the node at the end using the tail pointer.
• If list is empty, reuses insertAtFirst().

public void insertAtLast(int val) {
    if (tail == null) {
        insertAtFirst(val);
        return;
    }

    Node node = new Node(val);
    tail.next = node;
    tail = node;

    size++;
}

Insert at Specific Index:

• Handles edge cases: beginning or end.
• Finds the node at index - 1.
• Inserts the new node between temp and temp.next.

public void insert(int index, int val) {
    if (index == 0) {
        insertAtFirst(val);
        return;
    }
    if (index == size) {
        insertAtLast(val);
        return;
    }

    Node temp = head;
    for (int i = 1; i < index; i++) {
        temp = temp.next;
    }

    Node node = new Node(val, temp.next);
    temp.next = node;

    size++;
}

Delete from Beginning:

• Removes the first node by updating head.
• If list becomes empty, reset tail.
• Returns deleted value.

public int deleteAtFirst() {
    int val = head.value;
    head = head.next;

    if (head == null) {
        tail = null;
    }

    size--;
    return val;
}

Delete from End:

• Traverses till second-last node.
• Updates tail, breaks link to last node.
• Edge case for single-node list handled using deleteAtFirst().

public int deleteAtLast() {
    if (size <= 1) {
        return deleteAtFirst();
    }

    Node temp = head;
    while (temp.next.next != null) {
        temp = temp.next;
    }

    int val = temp.next.value;
    tail = temp;
    tail.next = null;

    size--;
    return val;
}

Delete at Specific Index:

• Traverses to node before the target.
• Bypasses the target node.
• Returns the deleted value.

public int delete(int index) {
    if (index == 0) {
        return deleteAtFirst();
    }

    if (index == size - 1) {
        return deleteAtLast();
    }

    Node temp = head;
    for (int i = 1; i < index; i++) {
        temp = temp.next;
    }

    int val = temp.next.value;
    temp.next = temp.next.next;

    size--;
    return val;
}

Search a Value:

• Linear search from head to null.
• Returns true if value is found.

public boolean search(int val) {
    Node temp = head;
    while (temp != null) {
        if (temp.value == val) {
            return true;
        }
        temp = temp.next;
    }
    return false;
}

Display the List:

• Prints all node values sequentially.
• Indicates end with END.

public void display() {
    for (Node temp = head; temp != null; temp = temp.next) {
        System.out.print(temp.value + " -> ");
    }
    System.out.print("END\n");
}

Final Thoughts:

Implementing a Singly Linked List from scratch has deepened my understanding of how dynamic data structures work under the hood. While built-in collections in Java make it easy to manage data, building my own linked list helps me to truly grasp:

• How memory is allocated and connected through references.
• How insertion and deletion work in constant time at specific positions.
• The importance of managing head, tail, and size carefully to avoid bugs.

---

2. Doubly Linked List Implementation:

Here’s how I implemented a Doubly Linked List from scratch in Java — including insertion, traversal (both forward and reverse), and search operations. I also added deletion methods to complete the core functionality.

Node Structure:

• Represents a node in the list.
• Each node contains an integer value, a reference to the next node, and a reference to the previous node.

private static class Node {
    int value;
    Node next;
    Node prev;

    public Node(int value) {
        this.value = value;
    }

    public Node(int value, Node next, Node prev) {
        this.value = value;
        this.next = next;
        this.prev = prev;
    }
}

Insert at Beginning

• Creates a new node.
• Points its next to the current head.
• Updates the previous head's prev pointer to the new node if head exists.
• Updates head to the new node.
• Increments the size.

public void insertAtFirst(int val) {
    Node node = new Node(val);

    node.next = head;
    if(head != null) {
        head.prev = node;
    }
    head = node;
    size++;
}

Insert at End:

• If the list is empty, delegates to insertAtFirst.
• Otherwise, traverses to the last node.
• Creates a new node and links it after the last node.
• Updates the prev pointer of the new node.
• Increments the size.

public void insertAtLast(int val) {
    if(head == null) {
        insertAtFirst(val);
        return;
    }

    Node temp = getLastNode(head);
    Node node = new Node(val);
    temp.next = node;
    node.prev = temp;
    node.next = null;
    size++;
}

Insert at Given Index:

• Inserts at the beginning or end if index is 0 or size, respectively.
• Otherwise, traverses to the node before the index.
• Inserts the new node between nodes, adjusting both next and prev pointers accordingly.
• Increments the size.

public void insert(int index, int val) {
    if(index == 0){
        insertAtFirst(val);
        return;
    }

    if(index == size) {
        insertAtLast(val);
        return;
    }
    Node temp = head;
    for(int i=1; i<index; i++) {
        temp = temp.next;
    }
    Node node = new Node(val);

    temp.next.prev = node;
    node.next = temp.next;
    node.prev = temp;
    temp.next = node;

    size++;
}

Insert After a Specific Node Value:

• Searches for the node with the given value.
• If not found, prints an error message.
• Otherwise, inserts a new node right after it, updating pointers properly.
• Increments the size.

public void insertAfterNode(int nodeVal, int val) {
    Node temp = search(nodeVal);
    if(temp == null) {
        System.out.println("Node does not exist");
        return;
    }

    Node node = new Node(val);
    if(temp.next != null) {
        temp.next.prev = node;
    }
    node.next = temp.next;
    node.prev = temp;
    temp.next = node;

    size++;
}

Search for a Node:

• Traverses the list from head.
• Returns the node if its value matches.
• Returns null if not found.

public Node search(int nodeVal){
    Node temp = head;
    while (temp != null){
        if(temp.value == nodeVal) {
            return temp;
        }
        temp = temp.next;
    }
    return null;
}

Display the List (Forward):

• Traverses from head to end.
• Prints node values separated by arrows.

public void display(){
    Node temp = head;
    while (temp != null) {
        System.out.print(temp.value + " -> ");
        temp = temp.next;
    }
    System.out.print("END");
    System.out.println();
}

Display the List (Reverse):

• Finds the last node.
• Traverses backward using prev pointers.
• Prints node values separated by arrows.

public void displayRev() {
    Node temp = getLastNode(head);

    while (temp != null) {
        System.out.print(temp.value + " -> ");
        temp = temp.prev;
    }
    System.out.print("START");
    System.out.println();
}

Helper Method: Get Last Node

• Traverses from the given node to the last node in the list.

private Node getLastNode(Node node) {
    Node temp = node;
    while (temp.next != null) {
        temp = temp.next;
    }
    return temp;
}

Delete at First:

• Saves the current head value.
• Moves head to the next node.
• Sets the new head's prev to null if head is not null.
• Decrements size.
• Returns deleted value.

public int deleteAtFirst() {
    if(head == null) {
        throw new RuntimeException("List is empty");
    }
    int val = head.value;
    head = head.next;
    if(head != null) {
        head.prev = null;
    }
    size--;
    return val;
}

Delete at Last:

• If the list has 0 or 1 node, delegates to deleteAtFirst.
• Otherwise, traverses to the last node.
• Updates the previous node’s next to null.
• Decrements size.
• Returns deleted value.

public int deleteAtLast() {
    if(head == null) {
        throw new RuntimeException("List is empty");
    }
    if(size == 1) {
        return deleteAtFirst();
    }

    Node temp = getLastNode(head);
    int val = temp.value;

    temp.prev.next = null;
    size--;

    return val;
}

Delete at Given Index:

• If index is 0, deletes at first.
• If index is the last, deletes at last.
• Otherwise, traverses to the node at the given index.
• Adjusts the next and prev pointers of neighboring nodes to remove the node.
• Decrements size.
• Returns deleted value.

public int delete(int index) {
    if(index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Invalid index");
    }
    if(index == 0){
        return deleteAtFirst();
    }
    if(index == size - 1){
        return deleteAtLast();
    }

    Node temp = head;
    for(int i = 0; i < index; i++) {
        temp = temp.next;
    }
    int val = temp.value;

    temp.prev.next = temp.next;
    temp.next.prev = temp.prev;

    size--;
    return val;
}

Final Thoughts:

Building the Doubly Linked List from scratch helped me understand the added complexity of maintaining two pointers per node (next and prev) compared to singly linked lists.

This structure enables:

• Easy traversal in both directions.
• Efficient insertion and deletion at both ends and in the middle of the list.

By implementing all core operations manually, I’ve strengthened my grasp on:

• Pointer manipulation
• List traversal
• Data structure design

All of which are critical for solving many complex coding problems and technical interviews.

---

3. Circular Linked List Implementation:

After implementing Singly Linked List (SLL) and Doubly Linked List (DLL), I moved on to implement a Circular Linked List (CLL).

Unlike regular linked lists, the key idea behind a Circular Linked List is that the tail node points back to the head, forming a loop.

Since the core logic of node structure, insertion, and traversal is quite similar to a Singly Linked List, I chose to implement only the essential methods to demonstrate the concept.

Key Highlights of Circular Linked List:

Only Two Methods Implemented:

• insertAtFirst(int val)
• display()

This is intentional — because:

• The operations are mostly similar to Singly Linked List.
• The only difference is:
  The tail.next is updated to point to head to form a circular structure.

Insert At First:

• Creates a new node.
• If the list is empty:
  • Head and tail both point to the new node.
• Else:
  • New node points to the current head.
  • Head is updated to the new node.
  • Tail’s next is updated to point to the new head to maintain the circle.

public void insertAtFirst(int val) {
        Node node = new Node(val);
        if(head == null){
            head = node;
            tail = node;
            size++;
            return;
        }
        node.next = head;
        head = node;
        tail.next = head;

        size++;
    }

Display:

• Uses a do-while loop to ensure the circular nature is respected.
• Starts from the head and prints node values until it loops back to the head.
• Ends with a "HEAD" marker to show it circles back.

public void display() {
        Node temp = head;
        if(head != null) {
            do {
                System.out.print(temp.value + " -> ");
                temp = temp.next;
            } while (temp != head);
        }

        System.out.print("HEAD");
        System.out.println();
    }

Why I Didn’t Implement All Operations?

Just like in Doubly Circular Linked List, most operations (insertion, deletion, search) follow the same principles as SLL/DLL.

The only difference is:

• For CLL, tail connects back to head.
• For DCLL, both next and prev wrap around.

So, instead of duplicating similar code, I focused on the circular behavior through minimal and effective implementation.

Final Thoughts:

Implementing a Circular Linked List reinforced my understanding of how linked structures can be adapted to meet different requirements.

By simply connecting the tail back to the head, a circular list enables continuous traversal without hitting a null reference — which is particularly useful in scenarios like round-robin scheduling or buffer management.

Since the insertion and traversal logic closely mirrors that of a Singly Linked List, I didn’t feel the need to implement every operation again. The primary goal was to internalize the unique circular behavior and ensure proper pointer updates.

With this, I’ve now explored all three major types of linked lists — Singly, Doubly, and Circular — and have a much stronger grasp of their inner workings, advantages, and trade-offs.

---

4. What's next:

I’m excited to keep growing and sharing along the way! Here’s what’s coming up:

• Posting new blog updates every 3 days to share what I’m learning and building.
• Alongside mastering DSA concepts, I’m also documenting my web development journey — check out my ongoing Web dev Journey Blog for ReactJS concepts, UI projects, Codes, and more.
• Sharing regular progress and insights on X (Twitter) — feel free to follow me there and join the conversation!

Thanks for being part of this journey!

---

5. Conclusion:

In this blog of my dsa journey, I walked through the implementation of three fundamental types of Linked Lists:
🔹 Singly Linked List (SLL)
🔹 Doubly Linked List (DLL)
🔹 Circular Linked List (CLL)

By building each from scratch, I not only learned how these structures work internally but also how operations like insertion, deletion, traversal, and searching differ depending on pointer configurations.

Here’s what I gained from this experience:

• A deep understanding of node linkage and pointer manipulation
• The differences and trade-offs between SLL, DLL, and CLL
• Practical coding experience that will help in interview problem-solving
• Confidence in handling custom data structures without relying on built-in libraries

This hands-on practice has laid a strong foundation for moving on to more complex data structures like stacks, queues, and eventually trees and graphs.

If you're on a similar learning path, feel free to follow along or reach out — let’s grow together.