dsa.singlylinkedlist

  1""" Module containing singly linked list class. """
  2
  3class Node:
  4    """ 
  5    A singly linked list node implementation.
  6    """
  7    def __init__(self, value):
  8        """ 
  9        A singly linked list node.
 10        Args:
 11            value: The value of the node.
 12        """
 13        #: value of the node
 14        self.value = value
 15        #: reference to the next node
 16        self.next = None
 17
 18class LinkedList:
 19    """ 
 20    A singly linked list implementation.
 21    """
 22    def __init__(self, head: Node=None, tail: Node=None, count: int=0):
 23        """ 
 24        Initialize a singly linked list.
 25        
 26        if only the head node is specified, tail is set to the head node and count is automatically set to 0
 27        if both head and tail nodes are specified, count should be specified as well
 28        
 29        Args:
 30            head: The reference to the head node.
 31            tail: The reference to the tail node.
 32            count: The number of nodes in the linked list.
 33
 34        """        
 35        self.head = head
 36        if head and tail is None:
 37            self.tail = head
 38            self.count = 1
 39        else:
 40            self.tail = tail
 41            self.count = count
 42
 43    @classmethod
 44    def from_list(cls, mylist=None):
 45        """
 46        Create a linked list from a list.
 47
 48        Args:
 49            mylist: A list or container to convert from.
 50        
 51        Returns:
 52            A  linked list containing the items from mylist.
 53        """
 54        ll = cls()
 55        for value in mylist:
 56            ll.append(value)
 57
 58        return ll
 59    
 60    def to_list(self) -> list:
 61        """
 62        Create a list with contents of the linked list.
 63
 64        Returns:
 65            List with contents of linked list.
 66        """
 67        mylist = []
 68        current = self.head
 69        while current:
 70            mylist.append(current.value)
 71            current = current.next
 72        return mylist
 73
 74    def print(self):
 75        """
 76        Print the contents of the linked list.
 77        """
 78        current = self.head
 79        while current:
 80            print(current.value, end=" ")
 81            current = current.next
 82        print()
 83
 84            
 85    def __repr__(self):
 86        """
 87        Return a string representation of the linked list.
 88
 89        Returns:
 90            A string representation of the linked list.
 91        """
 92        s = ""
 93        current = self.head
 94        while current:
 95            s += str(current.value) + " "
 96            current = current.next
 97
 98        return f"[ {s}] Count: {self.count}"
 99    
100    def __getitem__(self, index: int) -> Node:
101        """ 
102        Return value at a specified index. Raise IndexError if index is out of bounds.
103        
104        Args:
105            index: Index of value.
106
107        Raises:
108            IndexError: If index is out of bounds.
109
110        Returns:
111            The value at the specified index.
112        """        
113        i = 0
114        current = self.head
115        while current:
116            if i == index:
117                return current.value
118            current = current.next
119            i += 1
120        raise IndexError("Index Out of Bounds")
121
122    def __len__(self) -> int:
123        """
124        Return the number of elements in the linked list.
125        """
126        return self.count
127    
128    def is_empty(self) -> bool:
129        """
130        Check if the linked list is empty.
131        """
132        return self.count == 0
133        
134    def search(self, value) -> int:
135        """
136        Search for a value in the linked list.
137
138        Args:
139            value: The value to search for.
140
141        Returns:
142            Return index of found value.
143        
144        Raises:
145            Exception: If value is not found.
146        """
147        i = 0
148        current = self.head
149        while current:
150            if current.value == value:
151                return i
152            i += 1
153            current = current.next
154        raise Exception("Value not found")
155    
156    def insert(self, index: int, value):
157        """
158        Insert a value at a specified index. Raise exception if index is out of bounds.
159
160        Args:
161            index (int): The index to insert a value.
162            value: The value to append.
163
164        Returns:
165            None
166
167        Raises:
168            IndexError: If index is out of bounds.
169        """
170        i = 0
171        
172        # insert front
173        if index == 0:
174            self.prepend(value)
175            return
176        elif index == self.count: # insert at end
177            self.append(value)
178            return
179        elif index > self.count:
180            raise IndexError("Index Out of Bounds")
181        
182        # find node to insert after
183        current = self.head
184        while index < i or current:
185            i += 1
186            if i == index:
187                break
188            current = current.next
189        
190        if index > i:
191            raise IndexError("Index Out of Bounds")
192
193        new_node = Node(value)
194        tmp = current.next
195        current.next = new_node
196        new_node.next = tmp
197        self.count += 1
198
199    def prepend(self, value):
200        """
201        Place a value at the beginning of the linked list.
202
203        Args:
204            value: A value to append.
205
206        Returns:
207            None
208        """
209        new_node = Node(value)
210        new_node.next = self.head
211        self.head = new_node
212        self.count += 1
213        
214    def append(self, value):
215        """
216        Place a value at the end of the linked list.
217
218        Args:
219            value: A value to append.
220
221        Returns:
222            None
223        
224        Raises:
225            IndexError: If linked list is empty or index is not found.
226        """
227        if self.head is None:
228            self.head = Node(value)
229            if self.count == 0:
230                self.tail = self.head
231            self.count += 1
232            return
233
234        # go to the end of the list
235        new_node = Node(value)
236        self.tail.next = new_node
237        self.tail = new_node
238        
239        self.count += 1
240
241    def delete(self, index: int):
242        """
243        Delete a node at a specified index. Raise IndexError if linked list is empty or if index is not found.
244
245        Args:
246            index: Index of element to be deleted.
247        
248        Returns:
249            None
250            
251        Raises:
252            IndexError: If linked list is empty or index is not found.
253        """
254        if index == 0:
255            self.delete_head()
256            return
257        elif index + 1 == self.count:
258            self.delete_tail()
259            return
260
261        i = 0
262        current = self.head
263        prev = None
264        while current:
265            if index == i:
266                if prev is not None:
267                    prev.next = current.next
268                else:
269                    self.head = current.next
270                self.count -= 1
271                return
272            i += 1
273            prev = current
274            current = current.next
275        raise IndexError("Index not found")
276
277    def delete_head(self):
278        """
279        Delete the head node in the linked list. Raise IndexError if linked list is empty.
280
281        Returns:
282            None
283
284        Raises:
285            IndexError: If linked list is empty.
286        """
287        if self.head is None:
288            raise IndexError("LinkedList is Empty")
289        self.head = self.head.next
290        self.count -= 1
291
292    def delete_tail(self):
293        """
294        Delete the last node in the linked list. Raise IndexError if linked list is empty.
295
296        Returns:
297            None
298            
299        Raises:
300            IndexError: If linked list is empty.
301        """
302        if self.head is None:
303            raise IndexError("LinkedList is Empty")
304        
305        if self.head.next is None:
306            self.head = None
307            self.count -= 1
308            return
309        
310        current = self.head
311        while current.next.next:
312            current = current.next
313        
314        current.next = None
315        self.tail = current
316        self.count -= 1
317    
318if __name__ == "__main__":
319    ll = LinkedList.from_list(range(10))
320    ll = LinkedList()
321
322    for _ in range(15):
323        ll.append(_)
324    assert (ll.head.value == 0)
325    assert (ll.tail.value == 14)
326    assert (ll.count == 15)
327
328    print(ll.to_list())
329    ll.insert(1, -1)
330    print(ll.to_list())
331    assert (ll[1] == -1)
332#    self.assertEqual(ll.count, 16)
333    ll.insert(0, -2)
334#    ll.prepend(-2)
335    print(ll.to_list())
336    assert (ll[0] == -2)