Learn�DSA�Linked Lists

Lesson 1 � Beginner

Linked Lists: Nodes ka Chain

Arrays ke baad sabse important data structure hai Linked List. Ye dynamic hai, efficient insertion/deletion deta hai, aur interview mein bahut zyada poocha jaata hai. Chalo step by step samajhte hain ki linked list hota kya hai aur kyun zaroori hai.

? 22 min✓ Beginner✓ Python basics

Linked List kyun chahiye?

WHAT

Linked list ek linear data structure hai jisme elements (nodes) kisi ek sequence mein hote hain but unki memory allocation contiguous nahi hoti. Har node ek jagah hota hai aur usme next node ka pointer hota hai. Jaise ek treasure hunt � har clue tumhe agle clue ki jagah batata hai.

WHEN

Arrays mein insertion/deletion beginning mein O(n) hota hai kyunki sab elements shift karne padte hain. Linked list mein ye O(1) hota hai kyunki sirf pointers change karne hote hain. Jab frequently insert/delete hoti hai � use linked list.

WHERE

Stack, Queue, Hash Map chaining, Graph adjacency list, LRU Cache � sab linked list pe based hain. Operating systems ki process scheduling bhi linked list use karti hai.

Mental Model: Imagine karo ek train. Har bogie (node) mein data hai (passengers) aur har bogie ko pata hai agla bogie kahan hai (pointer). Engine (head) se shuru karte ho, aur last bogie (tail) ka next kisi ko point nahi karta (None). Tum kisi bhi beech ka bogie hata sakte ho � bas usse pehle wale ko agle se jod do. 
# Linked list ka visual representation
# [10|?] ? [20|?] ? [30|?] ✓ None

# Har box ek Node hai:
# +--------------+
# � data = 10 �
# � next ? 20 �
# +--------------+

# First node = head (entry point)
# Last node = tail (next = None)

Singly vs Doubly Linked List

Do types ke linked lists hain � Singly aur Doubly. Difference samajhna important hai kyunki interview mein dono ke trade-offs poochhe jaate hain.

# Singly Linked List � har node sirf next ka pointer rakhta hai
# [10|?] ? [20|?] ? [30|?] ✓ None
# Ek direction mein travel kar sakte ho � aage

# Doubly Linked List � har node prev aur next dono ka pointer rakhta hai
# None ? [?|10|?] ? [?|20|?] ? [?|30|?] ✓ None
# Dono directions mein travel kar sakte ho � aage aur peeche

Singly ka Faayda

Kam memory use hoti hai � sirf ek pointer extra. Simple traversal ke liye kaafi hai. Stacks aur queues mein ye use hota hai.

Doubly ka Faayda

Peeche ja sakte ho (O(1) previous access). Deletion O(1) hoti hai kisi bhi node ki agar pointer ho. DLL zyada flexible hai but extra memory leta hai.

Kab use karein?

Interview mein aksar singly poochhte hain. Doubly tab use karo jab reverse traversal chahiye � jaise browser history, LRU Cache, ya playlist navigation.

Interview Tip: Default mein singly linked list assume karo jab tak specifically "doubly" na bole. Singly mein space kam lagti hai aur most problems singly pe solve ho jaati hain.

Node Structure samjho

Linked list ka fundamental building block hai Node. Har node mein do cheezein hoti hain � data aur next pointer. Chalo Python mein node banana seekhte hain.

# Node class banana � linked list ka building block
class Node:
 def __init__(self, data):
 self.data = data
 self.next = None # Initially kisi ko point nahi karta

# Ek node banao
first = Node(10)
print(first.data) # 10
print(first.next) # None (abhi kisi ko point nahi karta)

# Doosra node banao
second = Node(20)
third = Node(30)

# Nodes ko link karo � ye magic hai!
first.next = second # first ab second ko point karta hai
second.next = third # second ab third ko point karta hai

# Ab chain hai: 10 ? 20 ? 30 ✓ None

Ye simple hai � bas ek class jo data aur next pointer rakhta hai. Real power tab aati hai jab tum ye nodes ko chain mein connect karte ho. Tumhara "linked list" basically ek node (head) hai jo baaki sab ko point karta hai.

# Linked list traverse karna � head se shuru karke last tak jaao
def traverse(head):
 current = head
 while current is not None:
 print(current.data, end=" ? ")
 current = current.next
 print("None")

# Use karo
traverse(first) # Output: 10 ? 20 ? 30 ✓ None
Key Point: Head sirf ek node hai � first node. Agar head None hai toh linked list empty hai. Har traversal head se shuru hota hai aur None pe khatam hota hai. Ye pattern har linked list problem mein use hoga.

Head, Tail, aur Size

Ek linked list mein kuch important concepts hain jo tumhe yaad rakhne chahiye � head (start), tail (end), aur size (kitne nodes hain).

# Linked list ka basic operations
class LinkedList:
 def __init__(self):
 self.head = None
 self.size = 0
 
 def is_empty(self):
 return self.head is None
 
 def get_size(self):
 return self.size

# Create karo
ll = LinkedList()
print(ll.is_empty()) # True � abhi kuch nahi hai
print(ll.get_size()) # 0

# Nodes add karo (aage ka lesson mein detail mein seekhenge)
ll.head = Node(10)
ll.head.next = Node(20)
ll.size = 2

print(ll.is_empty()) # False � ab kuch hai
print(ll.get_size()) # 2

Head kya hai?

Head linked list ka entry point hai. Bina head ke tum linked list access nahi kar sakte. Head None hai toh list empty hai.

Tail kya hai?

Tail last node hai jiska next = None hota hai. Kuch implementations mein tail pointer bhi rakhte hain O(1) insertion ke liye end mein.

Size kyun chahiye?

Bina traverse kiye size pata karne ke liye. Size field rakhna optional hai � tum loop se bhi count kar sakte ho, but size field O(1) mein size deta hai.

Arrays vs Linked Lists Comparison:
Array: Random access O(1), Insert beginning O(n), Insert end O(1) amortized, Memory contiguous
Linked List: Random access O(n), Insert beginning O(1), Insert end O(1) with tail pointer, Memory non-contiguous (pointers extra)

Try it: code khud likho




Exercise




Question: Given array [5, 10, 15, 20] se ek linked list banao aur print karo. Function likho jo head return kare. Answer mein output likho.











Question: Function likho jo linked list mein total nodes count kare. [10, 20, 30, 40, 50] ke liye answer do.









Common mistakes




Lesson complete?
Linked lists basics samajh aa gaye✓ Ab Insert, Delete, aur Reverse operations seekhte hain � ye linked list ki real power hai.