dsa.doublylinkedlist

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