Chapter 4DSA (Data Structures & Algorithms)~1 min read
Linked List
Dynamic Data Structure
Linked List मध्ये elements (nodes) memory मध्ये scattered असतात, एकमेकांशी pointers ने connected. Array पेक्षा insert/delete O(1) आहे (beginning/end), पण access O(n) आहे.
Marathi Analogy
Linked List म्हणजे treasure hunt — पहिला clue तुम्हाला दुसऱ्याचं location सांगतो, तो तुम्हाला तिसऱ्याचं सांगतो. प्रत्येक clue एक node आहे आणि location पुढचा pointer!
Singly Linked List implementation
python
class Node:
def __init__(self, data):
self.data = data
self.next = None # पुढच्या node चा pointer
class LinkedList:
def __init__(self):
self.head = None # पहिला node
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next: # शेवटपर्यंत जा
current = current.next
current.next = new_node # शेवटी add करा
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head # नवीन node → पहिला
self.head = new_node # head update
def print_list(self):
current = self.head
while current:
print(current.data, end=" → ")
current = current.next
print("None")
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
ll.print_list() # 0 → 1 → 2 → 3 → NoneReverse a Linked List — classic interview problem
python
def reverse(self):
prev = None
current = self.head
while current:
next_node = current.next # next save करा
current.next = prev # reverse pointer
prev = current # prev पुढे
current = next_node # current पुढे
self.head = prev✅ Key Points — लक्षात ठेवा
- ▸Node = data + next pointer
- ▸head = पहिला node
- ▸Traversal: O(n), Insert at head: O(1)
- ▸Reverse linked list — must know interview problem
- ▸Fast & slow pointers — cycle detection
0/10 chapters पूर्ण