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