Java LinkedList: Doubly-Linked Implementation Guide
Java LinkedList: Doubly-Linked Implementation Guide
Introduction to LinkedList in Java
अगर आप Java language में data structure पढ़ रहे हैं, तो LinkedList एक बहुत ही important topic है। ये Collection Framework का हिस्सा है और java.util package में मौजूद होता है। LinkedList का use तब किया जाता है जब हमें elements को बार-बार जोड़ना या हटाना होता है, क्योंकि ये operations इसमें बहुत fast होते हैं।
ArrayList की तुलना में LinkedList memory में अलग तरीके से काम करता है। यह elements को continuous memory blocks में store नहीं करता, बल्कि हर element एक node के रूप में रहता है, जो अपने next और previous node को point करता है। इसी वजह से इसे Doubly Linked List कहा जाता है।
Internal Structure of LinkedList
LinkedList internally Doubly Linked List के concept पर काम करता है। इसका मतलब हर node के पास तीन चीज़ें होती हैं — data, previous pointer और next pointer।
Node Structure
हर node में actual value (data) और दो reference होते हैं — एक previous node के लिए और एक next node के लिए। इससे हम list को दोनों directions (forward और backward) में traverse कर सकते हैं।
class Node<E> {
E data;
Node<E> next;
Node<E> prev;
Node(E data) {
this.data = data;
}
}
LinkedList Class Structure
Java की LinkedList class internally इसी node structure को use करती है। इसमें दो special references होते हैं — first और last, जो list के starting और ending elements को represent करते हैं।
public class LinkedList<E> {
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
}
Working of Doubly LinkedList
जब भी हम LinkedList में कोई नया element जोड़ते हैं, तो एक नया node create होता है और उसके links adjust किए जाते हैं ताकि list सही sequence में बनी रहे।
How elements are connected
- हर node अपने next और previous node से जुड़ा होता है।
- पहले node का previous pointer
nullहोता है। - आखिरी node का next pointer
nullहोता है। - इस linking की वजह से insertion और deletion बहुत तेज़ी से होता है।
Illustration (Conceptually)
मान लीजिए हमारी list है — 10 → 20 → 30 तो internal linking कुछ इस तरह दिखेगी:
| Previous | Data | Next |
|---|---|---|
| null | 10 | 20 |
| 10 | 20 | 30 |
| 20 | 30 | null |
Constructors of LinkedList
LinkedList()— एक empty list बनाता है।LinkedList(Collection<? extends E> c)— किसी existing collection से elements जोड़कर list बनाता है।
Important Methods of LinkedList
LinkedList class कई सारे methods provide करती है जो data को manage करने में मदद करते हैं।
| Method | Description |
|---|---|
add(E e) | List के end में element जोड़ता है। |
addFirst(E e) | List के start में element जोड़ता है। |
addLast(E e) | List के end में element जोड़ता है। |
remove() | पहला element हटाता है। |
removeFirst() | पहला element remove करता है। |
removeLast() | आखिरी element remove करता है। |
getFirst() | पहला element return करता है। |
getLast() | आखिरी element return करता है। |
clear() | सारे elements delete कर देता है। |
size() | List की current size बताता है। |
Example of LinkedList in Java
अब एक simple example देखते हैं जिससे आपको LinkedList की working practically समझ आएगी।
import java.util.LinkedList;
public class Example {
public static void main(String[] args) {
LinkedList<String> names = new LinkedList<>();
names.add("Rahul");
names.add("Amit");
names.addFirst("Sneha");
names.addLast("Priya");
System.out.println("LinkedList: " + names);
names.removeFirst();
names.removeLast();
System.out.println("After Removal: " + names);
}
}
Output:
LinkedList: [Sneha, Rahul, Amit, Priya]
After Removal: [Rahul, Amit]
Advantages of LinkedList
- Insertion और Deletion operations बहुत fast हैं क्योंकि shifting नहीं करनी पड़ती।
- Memory utilization बेहतर होती है क्योंकि size dynamic होता है।
- Elements को forward और backward दोनों directions में traverse किया जा सकता है।
Disadvantages of LinkedList
- Random access possible नहीं है, हर element तक पहुंचने के लिए traversal करना पड़ता है।
- Extra memory consumption होती है क्योंकि हर node में दो pointers रहते हैं।
- Searching operation slow होता है।
Difference Between ArrayList and LinkedList
| Feature | ArrayList | LinkedList |
|---|---|---|
| Memory | Continuous memory में store होती है। | Nodes अलग-अलग memory में store होते हैं। |
| Access Time | Fast (Direct access by index) | Slow (Sequential access) |
| Insertion/Deletion | Slow (Shifting required) | Fast (Pointers adjust होते हैं) |
| Use Case | Read-heavy operations | Insert/Delete-heavy operations |
| Implementation | Resizable Array | Doubly Linked List |
Internal Working of Add and Remove Methods
Add Operation
जब हम add(E e) call करते हैं, तो LinkedList internally नया node बनाता है और उसे last node से connect करता है।
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
}
Remove Operation
Remove करते समय previous और next nodes के pointers adjust किए जाते हैं ताकि middle node safely हट जाए।
E unlink(Node<E> x) {
final E element = x.data;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null)
first = next;
else
prev.next = next;
if (next == null)
last = prev;
else
next.prev = prev;
x.data = null;
size--;
return element;
}
Time Complexity Analysis
| Operation | Time Complexity |
|---|---|
| addFirst(), addLast() | O(1) |
| removeFirst(), removeLast() | O(1) |
| get(index) | O(n) |
| add(index, element) | O(n) |
| remove(index) | O(n) |
Use Cases of LinkedList
- जब frequent insertion और deletion operations की जरूरत हो।
- जब list का size बार-बार change होता हो।
- Stack या Queue implementation में।
- Undo/Redo feature या Navigation systems में।
Real-World Analogy
LinkedList को आप एक train की तरह समझ सकते हैं — जहाँ हर bogie एक node है और coupling (link) previous और next bogie को connect करती है। अगर एक bogie हटाना या जोड़ना है, तो बीच की पूरी train को shift नहीं करना पड़ता, बस connections adjust करने होते हैं।
LinkedList in Java Collections Framework
LinkedList class List और Deque दोनों interfaces को implement करती है। इसलिए इसे Stack और Queue दोनों की तरह use किया जा सकता है।
LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);
list.addFirst(5);
list.addLast(25);
System.out.println(list); // Output: [5, 10, 20, 25]
इस flexibility की वजह से LinkedList Java Collections में एक powerful class मानी जाती है।
Key Points to Remember
- LinkedList doubly linked structure पर आधारित है।
- Insertion और deletion fast लेकिन searching slow होती है।
- यह dynamic size को support करती है।
- यह List, Deque और Queue तीनों तरह से काम कर सकती है।
- Memory overhead pointers की वजह से थोड़ा ज़्यादा होता है।
Exam Notes
- Primary Concept: LinkedList = Doubly Linked Structure
- Important Methods: add(), remove(), get(), clear(), size()
- Time Complexity: add/remove O(1), access O(n)
- Implements: List, Deque, Cloneable, Serializable
- Use Cases: Stack, Queue, Undo/Redo systems
- Difference: ArrayList = Fast access, LinkedList = Fast insertion
