🧵 धडा 03 — Linked lists: खजिन्याचा शोध

📍 तुम्ही इथे आहात: 12 पैकी धडा 03 · पुढे: lesson-04-stacks-queues

📦 या ब्रँचमध्ये काय आहे

धडे 01–03. arrays नेमके ज्या operation मध्ये हरतात ते जिंकणारा structure — आणि प्रत्येक मुलाखतकार विचारतो ते जागच्या जागी उलटे करणे (in-place reversal).

dsa/structures.py — Node, LinkedList सह push_front, find (steps मोजतो), reverse
dsa/demo.py — linked

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

या वेळी lockers नाहीत — एक खजिन्याचा शोध. प्रत्येक चिठ्ठीत एक नाव असते आणि ती सांगते पुढची चिठ्ठी कुठे आहे. चौथ्या चिठ्ठीपर्यंत पोहोचायला पहिल्या तीन वाचाव्याच लागतात; "चिठ्ठी क्रमांक 17" असे काही नसते. पण सुरुवातीला चिठ्ठी जोडणे लगेच होते: ती लिहा, तिला जुन्या पहिल्या चिठ्ठीकडे दाखवा, झाले — कोणीही सरकत नाही.

🗺️ आकृती

flowchart LR
  H["head"] --> A["Aishwarya · next"] --> S["Katrina · next"] --> K["Dipika · next"] --> M["Meera · next"] --> N["None"]

❓ काय

node = value + पुढच्या node कडे pointer. list म्हणजे फक्त पहिला node (head). Doubly linked: दोन्ही दिशांना pointers.
खर्च: सुरुवातीला push/pop O(1); आधीच हातात असलेल्या node जवळ insert/delete O(1); i-वा node गाठणे O(n); search O(n); प्रत्येक element मागे एका pointer ची memory; cache ला न आवडणारे (nodes कुठेही राहतात).
जागच्या जागी उलटे करा: तीन नावे (prev, cur, next) घेऊन चाला, प्रत्येक बाण उलटा फिरवा: O(n) वेळ, O(1) जास्तीची जागा.
Python मध्ये built-in linked list नाही; collections.deque ही doubly linked block list आहे आणि queues साठी तीच वापरतात.

🤔 का

queues, LRU caches, adjacency lists आणि memory allocators linked lists वापरूनच बनवलेले असतात, आणि तीन pointers डोक्यात धरून ठेवता येतात का याची reversal ही क्लासिक परीक्षा आहे. linked list कधी वापरू नये (Python मध्ये जवळजवळ नेहमीच) हे माहीत असणे हा दुसरा अर्धा भाग.

🔧 कसे (या repo मध्ये)

push_front Node(value, self.head) तयार करतो; find किती चिठ्ठ्यांमागे गेला ते मोजतो; reverse म्हणजे तीन-pointer loop, सहा ओळी.

🧪 करून पाहा

python3 dsa/demo.py linked
python3 - <<'EOF'
import sys; sys.path.insert(0, "dsa"); from structures import LinkedList
ll = LinkedList()
for x in range(5, 0, -1): ll.push_front(x)
print(ll.to_list(), "find 4 in", ll.find(4), "steps")
ll.reverse(); print(ll.to_list())
# a deque does the same job at work:
from collections import deque; d = deque([1, 2, 3]); d.appendleft(0); d.pop(); print(d)
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

['Aishwarya', 'Katrina', 'Dipika', 'Meera', 'Rohan'], 2 चिठ्ठ्यांनंतर find 'Katrina', सगळ्या 5 पार केल्यावर find 'Zoya' = -1, आणि उलटी केलेली list. तुमची स्वतःची list [1, 2, 3, 4, 5] print करते, 4 हे 4 steps मध्ये शोधते, मग उलटी होते.

🏁 तुम्ही आत्ताच काय सिद्ध केले

तुम्ही फक्त nodes आणि pointers पासून list बनवली, O(1) insertion आणि O(n) search पाहिले, आणि जास्तीच्या memory शिवाय ती उलटी केली.

⚠️ नेहमीच्या चुका

उलटी करताना list चा उरलेला भाग गमावणे (next overwrite करण्याआधी save करा).
प्रत्येक insert शेवटीच होत असताना "insert O(1) आहे म्हणून" linked list निवडणे.
हाताने बनवलेल्या list वर len() O(n) असतो हे विसरणे, जोपर्यंत तुम्ही सोबत मोजत नाही.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: तुमच्या database समोरचा LRU cache म्हणजे hash map आणि doubly linked list; OS scheduler ची run queue आणि memory allocator मधली free-list या linked lists आहेत. तुम्ही त्या लिहिण्यापेक्षा वाचाल जास्त.

⏭️ पुढे

धडा 04 — stacks आणि queues: ट्रेची चळत आणि जेवणाची रांग, आणि list.pop(0) हा सापळा का आहे.

🧵 Lesson 03 — Linked lists: the treasure hunt

📍 You are here: Lesson 03 of 12 · Next: lesson-04-stacks-queues

📦 What's in this branch

Lessons 01–03. The structure that wins exactly the operation arrays lose — and the in-place reversal every interviewer asks for.

dsa/structures.py — Node, LinkedList with push_front, find (counts steps), reverse
dsa/demo.py — linked

🧒 Explain like I'm 5

No lockers this time — a treasure hunt. Each note holds a name and says where the next note is. To reach the fourth note you must read the first three; there is no "note number 17". But adding a note at the start is instant: write it, point it at the old first note, done — nobody shifts.

🗺️ Diagram

flowchart LR
  H["head"] --> A["Aishwarya · next"] --> S["Katrina · next"] --> K["Dipika · next"] --> M["Meera · next"] --> N["None"]

❓ What

A node = value + pointer to the next node. The list is just the first node (head). Doubly linked: pointers both ways.
Costs: push/pop at the front O(1); insert/delete at a node you already hold O(1); reach the i-th node O(n); search O(n); a pointer per element of memory; cache-unfriendly (nodes live anywhere).
Reverse in place: walk with three names (prev, cur, next), turn each arrow around: O(n) time, O(1) extra room.
Python has no built-in linked list; collections.deque is a doubly linked block list and is what you use for queues.

🤔 Why

Linked lists are how queues, LRU caches, adjacency lists and memory allocators are built, and the reversal is the classic test of whether you can hold three pointers in your head. Knowing when not to use one (almost always, in Python) is the other half.

🔧 How (in this repo)

push_front creates Node(value, self.head); find counts how many notes it followed; reverse is the three-pointer loop, six lines.

🧪 Try it

python3 dsa/demo.py linked
python3 - <<'EOF'
import sys; sys.path.insert(0, "dsa"); from structures import LinkedList
ll = LinkedList()
for x in range(5, 0, -1): ll.push_front(x)
print(ll.to_list(), "find 4 in", ll.find(4), "steps")
ll.reverse(); print(ll.to_list())
# a deque does the same job at work:
from collections import deque; d = deque([1, 2, 3]); d.appendleft(0); d.pop(); print(d)
EOF

✅ Verify — what you should see

['Aishwarya', 'Katrina', 'Dipika', 'Meera', 'Rohan'], find 'Katrina' after 2 notes, find 'Zoya' = -1 after walking all 5, and the reversed list. Your own list prints [1, 2, 3, 4, 5], finds 4 in 4 steps, then reverses.

🏁 What you just proved

You built a list from nothing but nodes and pointers, watched O(1) insertion and O(n) search, and reversed it without extra memory.

⚠️ Common mistakes

Losing the rest of the list while reversing (save next before you overwrite it).
Choosing a linked list "because insert is O(1)" when every insert is at the end.
Forgetting that len() on a hand-made list is O(n) unless you count as you go.

🏭 Why this matters in production: the LRU cache in front of your database is a hash map plus a doubly linked list; the OS scheduler's run queue and the free-list in a memory allocator are linked lists. You will read them more than write them.

⏭️ Next

Lesson 04 — stacks & queues: the tray pile and the lunch line, and why list.pop(0) is a trap.

← Previousarrays Next →stacks queues

This page is the lesson's README from the lesson-03-linked-lists branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.