🔍 What is a Linked List?
A linked list is a linear data structure where each element (called a node) contains:
The actual data
A reference (or pointer) to the next node in the sequence
Unlike arrays, linked lists do not use contiguous memory. This allows for efficient insertion and deletion but makes random access slower.
🧠 Memory Layout
In memory, each node of a linked list is stored at random locations, not sequentially like arrays. Each node has:
data: actual valuenext: memory address (reference) of the next node
This pointer-based structure allows dynamic memory allocation and efficient memory utilization.
Here’s a basic diagram to visualize it:
[10 | next] → [20 | next] → [30 | null]
You can imagine each box being scattered in memory, connected only by the references.
🔗 Types of Linked Lists
Singly Linked List
Nodes contain data + pointer to the next node
Traversal: One direction only
Doubly Linked List
Each node contains data + pointer to both next and previous nodes
Traversal: Both directions
Circular Linked List
Last node points back to the head
Used for buffering and scheduling applications
📊 Time Complexity Table for Linked List Operations
1. Access (by index)
Singly Linked List: O(n)
Doubly Linked List: O(n)
Circular Linked List: O(n)
2. Search (by value)
Singly Linked List: O(n)
Doubly Linked List: O(n)
Circular Linked List: O(n)
3. Insertion at Head
Singly Linked List: O(1)
Doubly Linked List: O(1)
Circular Linked List: O(1)
4. Insertion at Tail
Singly Linked List: O(n)*
Doubly Linked List: O(1)**
Circular Linked List: O(1)***
5. Deletion at Head
Singly Linked List: O(1)
Doubly Linked List: O(1)
Circular Linked List: O(1)
6. Deletion at Tail
Singly Linked List: O(n)
Doubly Linked List: O(1)
Circular Linked List: O(1)
7. Space Complexity
Singly Linked List: O(n)
Doubly Linked List: O(n)
Circular Linked List: O(n)
Footnotes:
* Tail insertion in singly linked lists is O(n) unless a tail pointer is maintained.
** With a maintained tail pointer, tail insertion in doubly linked lists is O(1).
*** In circular linked lists, tail insertion is O(1) due to circular references.
⚙️ Common Operations in Java
1. Insert at the Beginning
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
Node head = null;
void insertAtBeginning(int value) {
Node newNode = new Node(value);
newNode.next = head;
head = newNode;
}
2. Insert at the End
void insertAtEnd(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
return;
}
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
3. Delete by Value
void deleteNode(int value) {
if (head == null) return;
if (head.data == value) {
head = head.next;
return;
}
Node temp = head;
while (temp.next != null && temp.next.data != value) {
temp = temp.next;
}
if (temp.next != null) {
temp.next = temp.next.next;
}
}
4. Search an Element
boolean search(int key) {
Node temp = head;
while (temp != null) {
if (temp.data == key) return true;
temp = temp.next;
}
return false;
}
🧪 Must-Do LeetCode Problems
Here are some highly recommended problems to practice linked lists:
Reverse Linked List – LeetCode 206
Merge Two Sorted Lists – LeetCode 21
Linked List Cycle – LeetCode 141
Remove Nth Node From End – LeetCode 19
Intersection of Two Linked Lists – LeetCode 160
💡 Tips for Interview Prep
🔁 Master the Two-Pointer Technique
This is your go-to tool for solving a wide range of linked list problems! Whether you're detecting a cycle (Floyd’s algorithm), finding the middle node, or removing the Nth node from the end, two pointers (slow and fast) make life easier.
🧪 Simulate with a Whiteboard or Pen & Paper
Linked list operations are easier to visualize than to imagine in your head. During interviews, drawing node diagrams can help avoid pointer mistakes — and shows your clarity of thought.
🧹 Be Mindful of Edge Cases
Watch out for:
Empty list
Single-element list
Circular references
Head manipulation (especially in deletion or reversal)
Handling these gracefully shows you're a detail-oriented engineer.
🧠 Advanced Variants (Beyond the Basics)
Tail Pointer Linked List
Maintains an additional pointer to the tail node.
Speeds up insertion at the end (O(1)) without traversal.
Skip List
A multi-level linked list where each higher level acts like an "express lane".
Allows O(log n) search time — often used in databases and memory stores like Redis.
Unrolled Linked List
Each node stores a block/array of elements instead of a single one.
Reduces memory overhead and improves cache performance.
Used in text editors and high-performance apps.
XOR Linked List (Memory Efficient)
Uses XOR of addresses instead of storing two separate pointers.
Requires low-level pointer manipulation (rare in Java, more in C/C++).
Saves space but is harder to implement/debug.
Self-Adjusting Linked List
Reorders nodes based on usage (e.g., move-to-front on access).
Optimized for scenarios with non-uniform access patterns.
Multilevel (Flattenable) Linked List
Nodes can have a pointer to another linked list (a child).
Common in nested data structures.
Used in problems like Flatten a Multilevel Doubly Linked List.
🙌 Wrapping Up
Linked Lists are a fundamental concept that often intimidate beginners — but once mastered, they unlock a deeper understanding of memory management and reference manipulation. From simple traversals to solving interview classics like cycle detection and K-group reversal, linked lists offer a rich set of problems to practice and master.
I hope this post helped demystify how linked lists work and why they’re so valuable in interviews and real-world systems. If you found this helpful or have any questions, feel free to leave a comment — I’d be happy to discuss further!
📬 Stay updated: This is part of my ongoing series on data structures for interviews.
👉 Subscribe to my blog and follow me on LinkedIn for more practical insights.
Happy coding! 🚀
Nitin
Hashnode | Substack | LinkedIn | GIT | Youtube | Instagram
