double_linked_list.py

from collections.abc import Sequence


class DoubleLinkedList(Sequence):
    """Simple implementation of a doubly linked list."""
    
    _length = 0
     
    _head = None
    
    _tail = None
        
    class Node(object):
        """Represents an individual node in a DoubleLinkedList"""
        
        def __init__(self, value, next, previous):
            self.value = value
            self.next = next
            self.previous = previous
            
    def __getitem__(self, key):
        """O(n) access to data item given its key (or index)."""
        if key >= self._length:
            raise IndexError("Index out of bounds.")
        else:
            current_node = self._head
            for i in range(key):
                current_node = current_node.next
            return current_node.value
        
    def __len__(self):
        """
        O(1) access to the length of the DoubleLinkedList.
        
        Notes
        -----
        Access to the length of the DoubleLinkedList is O(1) because we
        increment the value of the private_length attribute on every insertion
        and decrement the value of _length on every deletion.
        
        """
        return self._length
       
    def __str__(self):
        """Human readable string representation of a DoubleLinkedList"""
        out = ""
        current_node = self._head
        while current_node is not None:
            out += str(current_node.value) + " <-> "
            current_node = current_node.next
        out += "None"
        return out
       
    def _find_node(self, value):
        """
        O(n) traversal of the DoubleLinkedList to find the node containing a
        particular value of data.
        
        """
        node = None
        current_node = self._head
        while current_node is not None:
            if current_node.value == value:
                node = current_node
                break
            else:
                current_node = current_node.next
        return node

    def prepend(self, value):
        """
        O(1) insertion of data onto the head of the LinkedList.
        
        Notes
        -----
        Inserting a new value into the DoubleLinkedList increments the
        private _length property. This side effect allows us to compute
        the length of a linked list is O(1).

        """
        if self._head is None:
            self._head = self.Node(value, None, None)
            self._tail = self._head
        else:
            self._head = self.Node(value, self._head, None)
        self._length += 1  # SIDE EFFECT!
        
    def append(self, value):
        """
        O(1) insertion of data onto the tail of the DoubleLinkedList.
        
        Notes
        -----
        Inserting a new value into the DoubleLinkedList increments the
        private _length property. This side effect allows us to compute
        the length of a linked list is O(1).

        """
        if self._tail is None:
            self._tail = self.Node(value, None, None)
            self._head = self._tail
        else:
            new_node = self.Node(value, None, self._tail)
            self._tail.next = new_node
            self._tail = new_node
        self._length += 1  # SIDE EFFECT!

    def remove(self, value):
        """
        O(n) removal of some data from the DoubleLinkedList.
        
        Notes
        -----
        Removing an existing value from the DoubleLinkedList decrements
        the private _length property. This side effect allows us to compute
        the length of a linked list is O(1).

        """
        if value == self._head.value:
            self.remove_head()
        else:
            deleted_node = self._find_node(value)
            if deleted_node is not None:
                predecessor = deleted_node.previous
                successor = deleted_node.next    
                predecessor.next = successor
                if successor is not None:
                    successor.previous = predecessor
                else:
                    pass
                self._length -= 1  # SIDE EFFECT!
            else:
                raise ValueError("Data item is not in the DoubleLinkedList!")
                
    def remove_head(self):
        """O(1) removal of the head of a DoubleLinkedList."""
        if self._head is not None:
            self._head = self._head.next
            self._head.previous = None
            self._length -= 1  # SIDE EFFECT!
            
    def remove_tail(self):
        """O(1) removal of the tail of a DoubleLinkedList."""
        if self._tail is not None:
            self._tail.previous.next = None
            self._tail = self._tail.previous
            self._length -= 1  # SIDE EFFECT!