Understanding LinkedList for Interviews

1. What is a LinkedList?

A LinkedList is a linear data structure. It stores elements in nodes. Each node has two parts:

Part	Description
data	The value stored.
next	The reference (pointer) to the next node.

So, nodes are connected like a chain.

Example representation:

[10 | next] -> [20 | next] -> [30 | next] -> null

The last node points to null, meaning the end of the list.

---

2. How LinkedList Is Different from Array?

Feature	Array	LinkedList
Storage	Continuous memory	Non-continuous memory
Access time	O(1) to access element using index	O(n), must traverse
Insertion/Deletion	Costly (shifting needed)	Easy (just change links)
Best use case	When searching is frequent	When insertion/deletion is frequent

So if your program does many insertions in the middle, LinkedList is better.

---

3. Types of LinkedLists

Type	Description
Singly LinkedList	Each node points to next node only.
Doubly LinkedList	Each node has next and prev.
Circular LinkedList	Last node points back to first node.

Here, we focus on Singly LinkedList, as it is the base concept.

---

4. Creating a Node in Java

class Node {
    int data;
    Node next;

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

This is the basic structure. Each time we create a node, we assign data and set next to null.

---

5. Creating a Simple LinkedList

class LinkedListExample {
    public static void main(String[] args) {
        Node a = new Node(10);
        Node b = new Node(20);
        Node c = new Node(30);

        a.next = b; // link 10 -> 20
        b.next = c; // link 20 -> 30

        Node head = a; // head refers to first node

        // Print list
        Node temp = head;
        while(temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
}

Output:

10 20 30

Here, head stores the starting point.

---

6. Inserting a Node

Insert at the Beginning:

Node newNode = new Node(5);
newNode.next = head;
head = newNode;

Insert at the End:

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

---

7. Deleting a Node

Delete First Node:

head = head.next;

Delete a Node with Specific Value:

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

---

8. Example Questions

Q1. Find the Length of a LinkedList

Problem: Count the number of nodes.

int length(Node head) {
    int count = 0;
    Node temp = head;
    while(temp != null) {
        count++;
        temp = temp.next;
    }
    return count;
}

Logic: Move through each node and count.

---

Q2. Search for a Value in LinkedList

boolean search(Node head, int key) {
    Node temp = head;
    while(temp != null) {
        if(temp.data == key) return true;
        temp = temp.next;
    }
    return false;
}

Understanding: You cannot jump directly. Must move one by one.

---

Q3. Reverse a LinkedList (Very Common Interview Question)

Original:

10 -> 20 -> 30 -> null

Reversed:

30 -> 20 -> 10 -> null

Logic: Change next links step-by-step.

Node reverse(Node head) {
    Node prev = null;
    Node curr = head;
    Node next;

    while(curr != null) {
        next = curr.next;   // store next node
        curr.next = prev;   // reverse link
        prev = curr;        // move prev
        curr = next;        // move curr
    }
    return prev;
}

This is important. Practice this.

---

9. Real-Life Analogy

Think of LinkedList like train coaches:

• Each coach has passengers (data)
• Each coach is attached to the next coach
• If one coach is removed, you can simply reattach links
• No need to reorder the whole train

But, If you want the 5th coach, you must walk from the first coach. You cannot jump directly like arrays.

---

10. When to Use LinkedList?

Use LinkedList when:

• Frequent insertion and deletion in the middle
• Memory is fragmented
• You don’t know exact size initially

Avoid LinkedList when:

• You need frequent random access (like arr[5])

---

11. Memory Representation

Head
 ↓
Node(10) -> Node(15) -> Node(25) -> null

Each node is stored anywhere in memory. Pointers connect them.

---

12. Summary

Point	LinkedList Key Idea
Structure	Data + Next pointer
Access	Sequential only
Best Use	When frequent insert/delete
Weakness	Slow to search

LinkedList teaches pointer management. Understanding next relationships is the core.

---

Thank You for Reading

Saquib Aftab