What is a Linked List?

Linked List एक linear data structure है, जो Array से थोड़ी अलग होती है।

• Array में data items continuously एक के बाद एक memory locations में store होते हैं।
• लेकिन, Linked List में data items (जिन्हें Nodes कहते हैं) memory में scattered (कहीं भी) हो सकते हैं।

Linked List का main idea यह है कि हर data item (यानी Node) अपने साथ next data item का address (location) भी रखता है।

Node क्या है? (What is a Node?)

एक Linked List का हर element एक Node कहलाता है। हर Node के दो main parts होते हैं:

1. Data Field (डेटा फील्ड):
   • इसमें actual data store होता है (जैसे कोई number, name, etc.)।
2. Next Field (नेक्स्ट फील्ड) / Pointer:
   • इसमें next Node का address store होता है।
   • अगर यह last Node है, तो इसका Next Field हमेशा NULL (या None) होता है, जिसका मतलब है कि इसके बाद कोई और element नहीं है।

Linked List का Concept

• Start/Head (शुरुआत/हेड): List के first Node को Head कहा जाता है। हमें हमेशा Head का address पता होना चाहिए, क्योंकि यहीं से list की शुरुआत होती है।
• End/Tail (अंत/टेल): List के last Node का Next Field हमेशा NULL होता है।

याद रखें: Nodes एक दूसरे से pointers के through linked होते हैं।

Linked List के Types (Types of Linked List)

Linked Lists primarily तीन तरह की होती हैं:

1. Singly Linked List (सिंगली लिंक्ड लिस्ट)

• यह सबसे simple type है।
• हर Node में एक Data field और एक Next pointer होता है, जो आगे वाले node को point करता है।
• हम सिर्फ आगे की तरफ travel (traverse) कर सकते हैं।

2. Doubly Linked List (डबली लिंक्ड लिस्ट)

• इसमें हर Node में तीन parts होते हैं: Data, Next pointer, और Previous (Prev) pointer।
• Next pointer आगे वाले node को point करता है।
• Prev pointer पीछे वाले node को point करता है।
• इससे हम list में आगे और पीछे दोनों तरफ travel कर सकते हैं।

3. Circular Linked List (सर्कुलर लिंक्ड लिस्ट)

• यह Singly या Doubly दोनों तरह की हो सकती है।
• इसका special feature यह है कि Last Node का Next pointer NULL नहीं होता, बल्कि यह First Node (Head) को point करता है।
• इससे list एक circle या loop में बन जाती है।

Linked List के Operations (Linked List Operations)

Linked List पर common operations (कार्रवाई) ये हैं:

1. Insertion (डालना)

• List में एक नया Node add करना। यह शुरुआत (beginning), अंत (end), या बीच में (at a specific position) हो सकता है।

2. Deletion (हटाना)

• List से एक मौजूदा Node को remove करना। यह भी शुरुआत, अंत, या बीच में हो सकता है।

3. Traversal (ट्रेवर्सल)

• Head से शुरू करके, list के हर Node को एक बार visit करना। यह जानने के लिए कि list में क्या-क्या data है।

4. Search (खोज)

• List में एक specific data value वाले Node को ढूँढना।

Array और Linked List में अंतर (Array vs. Linked List)

Feature	Linked List	Array
Size (साईज)	Dynamic (जरूरत के हिसाब से बढ़ या घट सकता है)।	Static (fixed size), या कुछ languages में dynamic (पर implementation अलग)।
Memory Allocation	Run-time पर मिलती है (Dynamic Allocation)।	Compile-time या Run-time पर मिलती है।
Accessing (पहुँचना)	Sequential Access (शुरुआत से एक-एक करके आगे बढ़ना पड़ता है)।	Random Access (किसी भी index पर direct पहुँच सकते हैं)।
Insertion/Deletion	Fast (O(1)) अगर Node का address पता हो।	Slow (O(n)) क्योंकि elements को shift करना पड़ता है।
Memory Usage	Data के अलावा extra memory pointers के लिए लगती है।	Pointers के लिए extra memory नहीं लगती।

Linked List के फायदे (Advantages)

1. Dynamic Size (डायनामिक साइज़): जरूरत पड़ने पर आसानी से grow या shrink हो सकती है, memory waste नहीं होती।
2. Easy Insertion/Deletion (आसान इन्सर्शन/डिलीशन): Nodes को shift करने की जरूरत नहीं होती, बस pointers को change करना होता है, जो तेज़ (faster) है।

Linked List के नुकसान (Disadvantages)

1. Memory Overhead: Pointers को store करने के लिए extra memory लगती है।
2. No Random Access: आपको index के base पर सीधे किसी element तक पहुँचने की permission नहीं है, आपको हमेशा Head से start करके sequence में आगे बढ़ना होगा।