Linked List Basics in Java

Linked Lists are one of the most fundamental data structures in programming. Unlike arrays, linked lists store elements in separate nodes, where each node contains:

• Data — the value stored in the node.
• Next — a reference (pointer) to the next node in the list.

Linked lists are widely used because they allow efficient insertion and deletion of elements without shifting existing data.

1. Insert at the Beginning

Adding a node at the front is one of the fastest operations in a linked list.

class Solution {
    public Node insertAtFront(Node head, int x) {
        Node newNode = new Node(x);
        newNode.next = head;
        return newNode;
    }
}

Time Complexity: O(1) Space Complexity: O(1)

2. Insert at the End

To insert at the end, traverse the list until the last node and attach the new node.

class Solution {

    public Node insertAtEnd(Node head, int x) {

        Node newNode = new Node(x);

        if (head == null)
            return newNode;

        Node temp = head;

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

        temp.next = newNode;

        return head;
    }

}

Time Complexity: O(n) Space Complexity: O(1)

3. Delete the Head Node

Deleting the first node simply means moving the head to the next node.

class Solution {

    public Node deleteHead(Node head) {

        if (head == null)
            return null;

        return head.next;
    }

}

Time Complexity: O(1) Space Complexity: O(1)

4. Delete the Last Node

Traverse to the second-last node and remove its link to the last node.

class Solution {

    public Node removeLastNode(Node head) {

        if (head == null || head.next == null)
            return null;

        Node temp = head;

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

        temp.next = null;

        return head;
    }

}

Time Complexity: O(n) Space Complexity: O(1)

5. Get the Nth Node

Traverse the list while counting nodes until the required index is reached.

class Solution {
    public int GetNth(Node head, int index) {

        Node temp = head;
        int count = 1;

        if (head == null)
          return -1;

        if (head.next == null && index == count)
          return head.data;

        while (temp != null) {
            if (count == index) {
                return temp.data;
            }
            temp=temp.next;
            count++;
        }

        return -1;
    }
}

Time Complexity: O(n) Space Complexity: O(1)

6. Search in a Linked List

Traverse the list and compare each node’s value with the target key.

class Solution {
    public boolean searchKey(Node head, int key) {

        Node temp = head;

        while (temp != null){
            if(temp.data == key)
                return true;
            temp = temp.next;
        }

        return false;
    }
}

Time Complexity: O(n) Space Complexity: O(1)

7. Reverse a Linked List (Using Recursion)

This recursive approach reaches the last node first, then reverses the links while the recursive calls return.

class Solution {

    ListNode newHead ;
    ListNode temp;

    public ListNode reverseList(ListNode head) {
        if(head==null)
            return null;

        recur(head);

        temp.next = null;
        return newHead;

    }

    public void recur(ListNode node) {

        if(node.next==null){
            newHead = node;
            temp = node;
            return;
        }

        recur(node.next);

        temp.next=node;
        temp=node;

    }
}

Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)

8. Reverse a Linked List (Without Recursion)

This recursive approach reaches the last node first, then reverses the links while the recursive calls return.

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head; 

        ListNode slow = head; 
        ListNode fast = head.next;

        head.next = null; 

        while(fast != null) {
            ListNode temp = fast.next;
            fast.next = slow;
            slow = fast;
            fast = temp;
        }
        return slow;
    }
}

Time Complexity: O(n) Space Complexity: O(1)

9. Middle of the Linked List

This recursive approach reaches the last node first, then reverses the links while the recursive calls return.

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null || head.next == null)
            return head;

        ListNode slow = head;
        ListNode fast = head;

        while( fast.next != null && fast.next.next != null) {
            slow = slow.next; // increasing slow by one
            fast = fast.next.next; // increasing fast by two

        }

        if (fast.next==null)
            return slow; // if it is odd return slow


        return slow.next; // if above condition is false, it is even and return slow.next (since the ques isto return second middle node)

    }
}

Time Complexity: O(n) Space Complexity: O(1)

9. Insertion at a Given Position in a Linked List

This recursive approach reaches the last node first, then reverses the links while the recursive calls return.

class Solution {

    public Node insertPos(Node head, int pos, int val) {

        Node newNode = new Node(); 
        newNode.data = val; 
        int count = 1;

        if(head == null)
            return null;

        if (count == pos) {
            newNode.next = head;
            return newNode;
        }

        Node slow = head;
        Node fast = head.next;

        while(fast != null){

            if (count+1 == pos){
                slow.next = newNode;
                newNode.next = fast;
                return head;
            }

            count++;
            slow = fast;
            fast = fast.next;
        }

        if (count+1 == pos){
            slow.next = newNode;
        }

        return head;
    }
}

Time Complexity: O(n) Space Complexity: O(1)

10. Kth from End of Linked List

This recursive approach reaches the last node first, then reverses the links while the recursive calls return.

class Solution {

    public int getKthFromLast(Node head, int k) {
        // code here

        Node temp;
        Node slow = head; 
        Node fast = head.next;
        int count = 1;

        head.next = null;

        while (fast != null){
            temp = fast.next;
            fast.next = slow;
            slow = fast;
            fast = temp;
        }

        while (slow != null) {
            if(count == k)
                return slow.data;
            count++;
            slow = slow.next;
        }

        return -1;

    }

}

Time Complexity: O(n) Space Complexity: O(1)