Singly Linked List

A Singly Linked List is a linear data structure wherein elements (nodes) are not stored in contiguous memory locations. Instead, each node points to the next node.

Node Structure

Each node contains:

1. Data: The value stored.
2. Next Pointer: Reference (address) to the next node in the sequence.

Time Complexity

Operation	Time Complexity	Description
Access	O(n)	Must traverse from head
Search	O(n)	Must traverse checking each node
Insert	O(1) or O(n)	O(1) at head, O(n) at end/middle
Delete	O(1) or O(n)	O(1) at head, O(n) at end/middle

Implementation in Java

public class SinglyLinkedList {

    // Inner class representing a Node
    class Node {
        int data;
        Node next;

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

    // Head of the list
    private Node head = null;

    // Insertion at the end
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode; // link the last node
    }

    // Traversal
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.add(10);
        list.add(20);
        list.add(30);
        
        list.display(); // Output: 10 -> 20 -> 30 -> null
    }
}