Linked List Tutorial - Singly + Doubly + Circular (Theory + Code + Implementation)

Introduction

In this tutorial, you'll learn about linked lists, one of the essential data structures in computer science, particularly useful for coding interviews. We will cover three types of linked lists: singly, doubly, and circular linked lists. You'll also see how to implement these structures in code, understand their internal workings, and learn about common operations such as insertion, deletion, and traversal.

Step 1: Understanding Linked Lists

Linked lists are a dynamic data structure that consist of nodes, where each node contains data and a reference (or pointer) to the next node in the sequence. This structure allows for efficient insertion and deletion of elements compared to arrays.

Limitations of Arrays

• Fixed size: Arrays require a predefined size, leading to wasted space or overflow.
• Costly insertions/deletions: Inserting or deleting an element in the middle requires shifting elements, which is inefficient.

Step 2: Singly Linked List

A singly linked list consists of nodes connected linearly where each node points to the next node.

Implementation

1. Node Structure

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

2. Creating the Linked List

   • Define a head node to point to the start of the list.
   • Initialize the linked list as empty.

Insertion in Singly Linked List

• At the Beginning

  • Create a new node and point its next to the current head. Update the head to this new node.

• At the End

  • Traverse to the last node and set its next to the new node.

• At a Specific Position

  • Traverse to the desired position and adjust pointers accordingly.

Displaying the Linked List

• Traverse from the head to the end, printing each node's data.

Deletion in Singly Linked List

• Handle three cases: deleting the head, a middle node, or the last node.
• Adjust pointers to remove the node and prevent memory leaks.

Step 3: Doubly Linked List

A doubly linked list allows traversal in both directions, with each node containing pointers to both the next and previous nodes.

Implementation

1. Node Structure

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

Insertion in Doubly Linked List

• Similar to singly linked lists but update both next and prev pointers.

Displaying the Doubly Linked List

• Start from the head and traverse forward, then backward using the prev pointer.

Reversal of Doubly Linked List

• Swap the next and prev pointers for all nodes and update the head.

Step 4: Circular Linked List

In a circular linked list, the last node points back to the first node, forming a loop.

Implementation

1. Node Structure (similar to singly linked list)

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

Insertion in Circular Linked List

• Insert as in singly linked lists but ensure the last node's next points to the head.

Displaying the Circular Linked List

• Start from the head and continue until you reach the head again to avoid infinite loops.

Deletion in Circular Linked List

• Handle deletion similarly to singly linked lists, ensuring the circular structure remains intact.

Conclusion

In this tutorial, we covered the fundamentals of linked lists, including singly, doubly, and circular linked lists. You learned how to implement each type, perform basic operations like insertion and deletion, and understand their advantages over arrays.

As next steps, consider practicing these implementations in your preferred programming language, exploring more complex operations, or integrating linked lists into larger data structures.