Spaces:
Sleeping
Sleeping
File size: 4,811 Bytes
4a3f117 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 | LINKED LISTS
============
A linked list stores elements in nodes. Each node holds data and a pointer to the next node.
Unlike arrays, nodes are not stored in contiguous memory.
Advantages: O(1) insert/delete at head, dynamic size.
Disadvantages: O(n) access by index, extra memory for pointers.
--- Node Definition ---
class Node:
def __init__(self, data):
self.data = data
self.next = None
--- Singly Linked List ---
Each node points to the next. Last node points to None.
class LinkedList:
def __init__(self):
self.head = None
def insert_at_head(self, data):
node = Node(data)
node.next = self.head
self.head = node
def insert_at_tail(self, data):
node = Node(data)
if not self.head:
self.head = node
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = node
def delete(self, data):
if not self.head:
return
if self.head.data == data:
self.head = self.head.next
return
curr = self.head
while curr.next and curr.next.data != data:
curr = curr.next
if curr.next:
curr.next = curr.next.next
def search(self, data):
curr = self.head
while curr:
if curr.data == data:
return True
curr = curr.next
return False
def print_list(self):
curr = self.head
result = []
while curr:
result.append(curr.data)
curr = curr.next
print(result)
ll = LinkedList()
ll.insert_at_tail(1)
ll.insert_at_tail(2)
ll.insert_at_tail(3)
ll.insert_at_head(0)
ll.print_list() # [0, 1, 2, 3]
ll.delete(2)
ll.print_list() # [0, 1, 3]
--- Reverse a Linked List ---
Time: O(n). Space: O(1).
def reverse(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev # new head
--- Detect Cycle (Floyd's Algorithm) ---
Use slow and fast pointers. If they meet, there is a cycle.
Time: O(n). Space: O(1).
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
--- Find Middle of Linked List ---
Time: O(n). Space: O(1).
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # slow is at middle
--- Merge Two Sorted Linked Lists ---
Time: O(n + m). Space: O(1).
def merge_sorted(l1, l2):
dummy = Node(0)
curr = dummy
while l1 and l2:
if l1.data <= l2.data:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
--- Remove Nth Node From End ---
Use two pointers separated by n steps.
Time: O(n). Space: O(1).
def remove_nth_from_end(head, n):
dummy = Node(0)
dummy.next = head
fast = slow = dummy
for _ in range(n + 1):
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
--- Check if Palindrome ---
Time: O(n). Space: O(1).
def is_palindrome(head):
# Find middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev = None
curr = slow
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Compare halves
left, right = head, prev
while right:
if left.data != right.data:
return False
left = left.next
right = right.next
return True
--- Doubly Linked List ---
Each node has a pointer to both next and previous nodes.
class DNode:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert_at_head(self, data):
node = DNode(data)
if self.head:
self.head.prev = node
node.next = self.head
self.head = node
def delete(self, node):
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prev
--- Circular Linked List ---
Last node points back to head forming a circle.
def is_circular(head):
if not head:
return False
curr = head.next
while curr and curr != head:
curr = curr.next
return curr == head
|