LINKED LIST
What is a Linked List?
A Linked List is a linear data structure where each element (called a node) contains:
1. Data (the value)
2. A pointer/reference to the next node in the sequence
Unlike arrays, elements are not stored in contiguous memory locations.
Types of Linked Lists
1. Singly Linked List – Each node points to the next node.
2. Doubly Linked List – Each node points to both the next and previous nodes.
3. Circular Linked List – The last node points back to the head.
Basic Operations on Linked Lists
Insertion – Add a new node at beginning, middle, or end
Deletion – Remove a node from the list
Traversal – Access each node and process the data
Search – Find an element in the list
Basic structure for a LinkedList Node class in Java
class Node {
int val; // value stored in the node
Node next; // reference to the next node
// Constructor
Node(int val) {
this.val = val;
this.next = null;
}
}
Basic structure for a Double LinkedList Node class in Java
class DoublyListNode {
int val;
DoublyListNode prev;
DoublyListNode next;
DoublyListNode(int val) {
this.val = val;
this.prev = null;
this.next = null;
}
}
Basic structure for a Circular LinkedList Node class in Java
class Node {
int val; // value stored in the node
Node next; // reference to the next node
// Constructor
Node(int val) {
this.val = val;
this.next = null;
}
}
LinkedList programs
Middle of the Linked List (Leetcode 876)
Detect a cycle in a linked list (Floyd’s Algorithm) (leetcode 141)
Linked List cycle II (leetcode 142)
Reverse a linked list (Leetcode 206)
Reverse Linked list II (leetcode 92)
Palindome Linked List (Leetcode 234)
Remove Linked List Element (Leetcode 203)
Remove duplicates from sorted list (leetcode 83)
Delete node in linked list (Leetcode 237)
Intersection of Two Linked Lists (Leetcode 160)
Merge two sorted linked lists (Leetcode 21)
Remove Nodes from Linkedlist (Leetcode 2487)
Reorder list (Leetcode 143)
Remove Nodes from the end (Leetcode 19)
Interview Questions
1. What is a linked list? How is it different from an array?
2. What are the types of linked lists? Explain each with an example.
3. How is memory allocated for linked lists?
4. What is a node in a linked list? What are its components?
5. How do you represent an empty linked list?
6. What are the basic operations supported by a linked list?
7. How do you traverse a linked list?
8. How do you insert a node at a given position in a linked list?
9. How do you delete a node from a linked list?
10. What are the time complexities of various linked list operations?
11. Linked list vs array – when and why would you use one over the other?
12. What are the advantages and disadvantages of linked lists?
13. What are circular linked lists used for in real-world scenarios?
14. Why is a doubly linked list preferred in some applications over a singly linked
list?
15. How does the fast and slow pointer technique work in linked lists?
16. What is a cycle in a linked list? How can it be detected?
17. What is a sentinel or dummy node in a linked list? Why is it useful?
18. Can we implement a stack or queue using linked list? How?
19. Explain how memory leaks can occur in linked lists.
20. How would you implement a linked list in a programming language (e.g., Java or
C++)?
21. Where are linked lists used in real-world software systems?
22. How are linked lists used in OS kernel structures or memory management?
23. Explain an example where a circular linked list is better than other types.
