Introduction to LinkedList: Flexible Node-Based Data Structure
Introduction to LinkedList: Flexible Node-Based Data Structure
अगर आप Java या किसी भी Object-Oriented Programming language को सीख रहे हैं, तो LinkedList एक बहुत ही important data structure है जिसे आपको अच्छे से समझना चाहिए। यह Dynamic Data Structure है जो memory को flexible तरीके से manage करता है। इस blog में हम step-by-step समझेंगे कि LinkedList क्या होती है, यह कैसे काम करती है, इसके types, working process, advantages, disadvantages और exam point of view से important notes क्या हैं।
What is LinkedList?
LinkedList एक linear data structure है जो nodes की chain के रूप में data को store करती है। हर node में दो parts होते हैं — एक data field और दूसरा pointer (या reference) जो next node के address को hold करता है।
Simple words में कहें तो, LinkedList connected nodes की एक series होती है जहाँ हर node अपने next node से link होती है। इसलिए इसे Node-Based Data Structure कहा जाता है।
Structure of a Node
हर node में दो fields होते हैं:
- Data: जहाँ actual value store होती है।
- Next: जो next node के address को hold करता है।
class Node {
int data;
Node next;
}
Types of LinkedList
LinkedList के कई प्रकार होते हैं जो उनकी linking pattern पर depend करते हैं। चलिए एक-एक करके समझते हैं:
1. Singly Linked List
इस list में हर node अपने next node की तरफ point करता है। आखिरी node का next pointer null होता है।
Head → [Data | Next] → [Data | Next] → [Data | null]
2. Doubly Linked List
इसमें हर node के पास दो pointers होते हैं — एक previous node की तरफ और दूसरा next node की तरफ। इससे traversal दोनों directions में किया जा सकता है।
null ← [Prev | Data | Next] ↔ [Prev | Data | Next] → null
3. Circular Linked List
इसमें last node null की बजाय first node की तरफ point करता है, जिससे list circular बन जाती है।
Head → [Data | Next] → [Data | Next] → [Data | Head]
4. Doubly Circular Linked List
यह doubly और circular दोनों features को combine करती है। इसका last node first node की तरफ point करता है और first node का previous pointer last node की तरफ।
Internal Working of LinkedList
LinkedList में हर node dynamic memory allocation से create होती है। जब भी आप नया data insert करते हैं, एक नया node create होता है और previous node के next pointer को उस पर point किया जाता है।
यहाँ एक simple insertion का process देखें:
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
अब LinkedList इस तरह दिखेगी:
10 → 20 → 30 → null
Memory Management in LinkedList
Array की तरह LinkedList में continuous memory allocation नहीं होता। हर node अलग-अलग जगह पर memory में allocate होती है और pointers के माध्यम से connect होती है। इसलिए इसे Dynamic Memory Allocation कहा जाता है।
| Array | LinkedList |
|---|---|
| Fixed size memory | Dynamic memory |
| Continuous blocks | Non-continuous blocks |
| Easy indexing | Sequential access only |
Operations on LinkedList
LinkedList पर कई basic operations perform किए जाते हैं। चलिए उन्हें समझते हैं।
1. Insertion
LinkedList में node को तीन जगह insert किया जा सकता है:
- At the beginning
- In the middle
- At the end
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
2. Deletion
Node को remove करने के लिए हमें previous node के pointer को update करना पड़ता है।
public void deleteNode(int key) {
Node temp = head, prev = null;
if (temp != null && temp.data == key) {
head = temp.next;
return;
}
while (temp != null && temp.data != key) {
prev = temp;
temp = temp.next;
}
if (temp == null) return;
prev.next = temp.next;
}
3. Traversal
Traversal का मतलब होता है हर node को visit करना और उसका data print करना।
public void printList() {
Node n = head;
while (n != null) {
System.out.print(n.data + " ");
n = n.next;
}
}
4. Searching
LinkedList में searching sequentially होती है क्योंकि direct indexing संभव नहीं होती।
boolean search(Node head, int key) {
Node current = head;
while (current != null) {
if (current.data == key)
return true;
current = current.next;
}
return false;
}
Advantages of LinkedList
- Dynamic size — memory के अनुसार बढ़ या घट सकती है।
- Insertion और Deletion fast होती है (no shifting required)।
- Memory utilization efficient होती है।
Disadvantages of LinkedList
- Random access possible नहीं होता (sequential traversal required)।
- Extra memory pointers के लिए चाहिए।
- Reverse traversal singly linked list में कठिन होता है।
Time and Space Complexity
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insertion | O(1) | O(n) |
| Deletion | O(1) | O(n) |
| Search | O(n) | O(1) |
| Traversal | O(n) | O(1) |
Real-World Applications
LinkedList का उपयोग कई जगह किया जाता है जहाँ dynamic data management की जरूरत होती है:
- Music या playlist management (next/previous song navigation)
- Undo/Redo feature in editors
- Memory allocation systems
- Graph और adjacency list implementation
Difference between ArrayList and LinkedList
| Feature | ArrayList | LinkedList |
|---|---|---|
| Data Structure Type | Dynamic Array | Node-based List |
| Insertion/Deletion | Slow (shifting required) | Fast (no shifting) |
| Random Access | Yes (index-based) | No (sequential) |
| Memory Overhead | Less | More (pointers) |
Exam-Oriented Notes
- Definition: LinkedList एक dynamic linear data structure है जो nodes से बनता है।
- Node parts: Data + Pointer
- Types: Singly, Doubly, Circular, Doubly Circular
- Advantages: Dynamic memory, fast insertion/deletion
- Disadvantages: No random access, extra memory for pointers
- Complexity: Insertion/Deletion O(1), Search O(n)
- Use Cases: Stack, Queue, Graph, Undo-Redo
- Important Class (Java): java.util.LinkedList
- Implements: List, Deque, Queue interfaces
- Exam Tip: LinkedList = Nodes + Pointers → Flexible Memory
