Implementation
1"""
2Doubly Linked List - Linear Data Structure
3
4A doubly linked list is a linear data structure where each element
5(node) contains a value and references to both the next and previous
6nodes in the sequence. The list maintains references to both the
7first node (head) and the last node (tail), allowing bidirectional
8traversal and O(1) operations at both ends.
9
10Time Complexity:
11 - Access by index: O(n)
12 - Search: O(n)
13 - Add at head: O(1)
14 - Add at tail: O(1) - direct tail access
15 - Add at position: O(n)
16 - Remove at head: O(1)
17 - Remove at tail: O(1) - direct tail access
18 - Remove at position: O(n)
19
20Space Complexity: O(n) where n is number of elements
21"""
22
23
24class DllNode:
25 """A single node in the doubly linked list."""
26
27 def __init__(self, val):
28 self.val = val
29 self.next = None
30 self.prev = None
31
32
33class DllList:
34 """
35 Doubly Linked List implementation.
36
37 Provides operations for adding, removing, searching, and
38 traversing elements in a bidirectional linked structure.
39 """
40
41 def __init__(self, val=None):
42 """Initialize the list, optionally with a starting value."""
43 if val is not None:
44 self.head = DllNode(val)
45 self.tail = self.head
46 self.len = 1
47 else:
48 self.head = None
49 self.tail = None
50 self.len = 0
51
52 def __len__(self):
53 """Return the number of nodes in the list."""
54 return self.len
55
56 def __str__(self):
57 """String representation: head <-> ... <-> tail."""
58 values = [str(el) for el in self]
59 return " <-> ".join(values)
60
61 def __repr__(self):
62 return str(self)
63
64 def __iter__(self):
65 """Iterate over all values in the list."""
66 cur = self.head
67 while cur:
68 yield cur.val
69 cur = cur.next
70
71 def __bool__(self):
72 """Return True if the list is not empty."""
73 return self.len > 0
74
75 def get_at(self, position) -> DllNode:
76 """
77 Get the node at the specified position.
78 Raises IndexError if position is invalid.
79 """
80 if position >= self.len or position < 0:
81 raise IndexError("Position is invalid.")
82 node = self.head
83 for _ in range(position):
84 node = node.next
85 return node
86
87 def add_left(self, val):
88 """Add a new node with the given value at the head. O(1)"""
89 new_node = DllNode(val)
90 if not self:
91 self.head = new_node
92 self.tail = new_node
93 else:
94 new_node.next = self.head
95 self.head.prev = new_node
96 self.head = new_node
97 self.len += 1
98
99 def add_right(self, val):
100 """Add a new node with the given value at the tail. O(1)"""
101 new_node = DllNode(val)
102 if not self:
103 self.head = new_node
104 self.tail = new_node
105 else:
106 new_node.prev = self.tail
107 self.tail.next = new_node
108 self.tail = new_node
109 self.len += 1
110
111 def add_at(self, val, position):
112 """
113 Insert a new node at the specified position.
114 Raises IndexError if position is out of bounds.
115 """
116 if position > len(self) or position < 0:
117 raise IndexError("Invalid position to insert a value at.")
118 if position == 0:
119 return self.add_left(val)
120 if position == len(self):
121 return self.add_right(val)
122 before = self.get_at(position - 1)
123 after = before.next
124 new_node = DllNode(val)
125 before.next = new_node
126 new_node.prev = before
127 new_node.next = after
128 after.prev = new_node
129 self.len += 1
130
131 def remove_left(self):
132 """
133 Remove and discard the head node. O(1)
134 Raises IndexError if list is empty.
135 """
136 if not self:
137 raise IndexError("List is empty.")
138 if self.len == 1:
139 self.head = None
140 self.tail = None
141 else:
142 self.head = self.head.next
143 self.head.prev = None
144 self.len -= 1
145
146 def remove_right(self):
147 """
148 Remove and discard the tail node. O(1)
149 Raises IndexError if list is empty.
150 """
151 if not self:
152 raise IndexError("List is empty.")
153 if self.len == 1:
154 self.head = None
155 self.tail = None
156 else:
157 self.tail = self.tail.prev
158 self.tail.next = None
159 self.len -= 1
160
161 def remove_at(self, position):
162 """
163 Remove the node at the specified position.
164 Raises IndexError if list is empty or position is invalid.
165 """
166 if not self:
167 raise IndexError("List is empty.")
168 if position < 0 or position >= self.len:
169 raise IndexError("Position is invalid.")
170 if position == 0:
171 return self.remove_left()
172 if position == self.len - 1:
173 return self.remove_right()
174 to_remove = self.get_at(position)
175 before = to_remove.prev
176 after = to_remove.next
177 before.next = after
178 after.prev = before
179 to_remove.prev = None
180 to_remove.next = None
181 self.len -= 1
182
183 def traverse(self):
184 """Return a list of all values in the list."""
185 cur = self.head
186 arr = []
187 while cur:
188 arr.append(cur.val)
189 cur = cur.next
190 return arr
191
192 def search_for(self, val):
193 """
194 Search for a value in the list.
195 Returns the position if found, -1 otherwise.
196 """
197 cur = self.head
198 pos = 0
199 while cur:
200 if cur.val == val:
201 return pos
202 pos += 1
203 cur = cur.next
204 return -1
205
206 def reverse_list(self):
207 """Reverse the linked list in place."""
208 cur = self.head
209 self.head, self.tail = self.tail, self.head
210 while cur:
211 cur.prev, cur.next = cur.next, cur.prev
212 cur = cur.prev # Move to next (which is now prev)
213
214
215# Example usage:
216if __name__ == "__main__":
217 # Create a new list
218 dll = DllList()
219
220 # Add elements at tail
221 dll.add_right(10)
222 dll.add_right(20)
223 dll.add_right(30)
224 print(dll) # 10 <-> 20 <-> 30
225
226 # Add to head
227 dll.add_left(5)
228 print(dll) # 5 <-> 10 <-> 20 <-> 30
229
230 # Add at position
231 dll.add_at(15, 2)
232 print(dll) # 5 <-> 10 <-> 15 <-> 20 <-> 30
233
234 # Search for a value
235 pos = dll.search_for(20)
236 print(f"Found 20 at position: {pos}") # Found 20 at position: 3
237
238 # Get value at position
239 node = dll.get_at(2)
240 print(f"Value at position 2: {node.val}") # Value at position 2: 15
241
242 # Remove elements
243 dll.remove_left()
244 print(dll) # 10 <-> 15 <-> 20 <-> 30
245
246 dll.remove_right()
247 print(dll) # 10 <-> 15 <-> 20
248
249 # Reverse the list
250 dll.reverse_list()
251 print(dll) # 20 <-> 15 <-> 10
252