linkedlist.py

#!python

class Node(object):

    def __init__(self, data):
        """Initialize this node with the given data."""
        self.data = data
        self.next = None
        self.prev = None

    def __repr__(self):
        """Return a string representation of this node."""
        return 'Node({!r})'.format(self.data)


class LinkedList(object):

    def __init__(self, iterable=None):
        """Initialize this linked list and append the given items, if any."""
        self.head = None  # First node
        self.tail = None  # Last node
        self.size = 0  # Number of nodes
        # Append the given items
        if iterable is not None:
            for item in iterable:
                self.append(item)

    def __str__(self):
        """Return a formatted string representation of this linked list."""
        items = ['({!r})'.format(item) for item in self.items()]
        return '[{}]'.format(' -> '.join(items))

    def __repr__(self):
        """Return a string representation of this linked list."""
        return 'LinkedList({!r})'.format(self.items())

    def items(self):
        """Return a list of all items in this linked list.
        Best and worst case running time: Theta(n) for n items in the list
        because we always need to loop through all n nodes."""
        # Create an empty list of results
        result = []  # Constant time to create a new list
        # Start at the head node
        node = self.head  # Constant time to assign a variable reference
        # Loop until the node is None, which is one node too far past the tail
        while node is not None:  # Always n iterations because no early exit
            # Append this node's data to the results list
            result.append(node.data)  # Constant time to append to a list
            # Skip to the next node
            node = node.next  # Constant time to reassign a variable
        # Now result contains the data from all nodes
        return result  # Constant time to return a list

    def is_empty(self):
        """Return True if this linked list is empty, or False."""
        return self.head is None

    def length(self):
        """Return the length of this linked list by traversing its nodes.
        Best case running time: O(1) if the length is 0
        Worst case running time: O(N) if there are n entries"""
        # Node counter initialized to zero
        node_count = 0
        # Start at the head node
        node = self.head
        # Loop until the node is None, which is one node too far past the tail
        while node is not None:
            # Count one for this node
            node_count += 1
            # Skip to the next node
            node = node.next
        # Now node_count contains the number of nodes
        return node_count

    def get_at_index(self, index):
        """Return the item at the given index in this linked list, or
        raise ValueError if the given index is out of range of the list size.
        Best case running time: O(1) if the first node is the one being looked for
        Worst case running time: O(N) if the last node is the one being looked for"""
        # Check if the given index is out of range and if so raise an error
        if not (0 <= index < self.size):
            raise ValueError('List index out of range: {}'.format(index))

        # PSEUDO BRAINSTORM
        # Call on the attribute size and then traverse as many times in the linkedlist as specified in
        # index

        counter = 0
        current_node = self.head
    
        while counter != index:
            current_node = current_node.next
            counter += 1
        return current_node.data

    def insert_at_index(self, index, item):
        """Insert the given item at the given index in this linked list, or
        raise ValueError if the given index is out of range of the list size.
        Best case running time: O(1) item to be inserted is at index 0
        Worst case running time: O(n) item to be inserted is at index n"""
        # Check if the given index is out of range and if so raise an error
        if not (0 <= index <= self.size):
            raise ValueError('List index out of range: {}'.format(index))

        # Edge cases using append (item at index 0)/prepend (item at index -1) functions
        # Note: early return because prepend/append already had self.size += 1 in them
        if index == 0:
            return self.prepend(item)
        elif index == self.size:
            return self.append(item)
        
        # Where the actual code starts
        new_node = Node(item)
        prev_node = None
        current_node = self.head
        counter = 0

        # # Singly linked list
        # while counter != index:
        #     prev_node = current_node
        #     current_node = current_node.next
        #     counter += 1
        # prev_node = new_node.next
        # new_node.next = current_node
        
        # Doubly linked list
        while counter != index:
            current_node = current_node.next
            counter += 1
            print(current_node)
            print(current_node.prev)
        new_node.prev = current_node.prev
        new_node.next = current_node 
        current_node.prev.next = new_node
        current_node.prev = new_node
        self.size += 1

    def append(self, item):
        """Insert the given item at the tail of this linked list.
        Best case running time: O(1) have reference to a tail element
        Worst case running time: O(1) have reference to a tail element"""
        # Create a new node to hold the given item
        new_node = Node(item)
        # Check if this linked list is empty
        if self.is_empty():
            # Assign head to new node
            self.head = new_node
        else:
            # Otherwise insert new node after tail
            self.tail.next = new_node
            new_node.prev = self.tail
        # Update tail to new node regardless
        self.tail = new_node
        self.size += 1

    def prepend(self, item):
        """Insert the given item at the head of this linked list.
        Best case running time: O(1) have reference to a head element
        Worst case running time: O(1) have reference to a head element"""
        # Create a new node to hold the given item
        new_node = Node(item)
        # Check if this linked list is empty
        if self.is_empty():
            # Assign tail to new node
            self.tail = new_node
        else:
            # Otherwise insert new node before head
            new_node.next = self.head
            self.head.prev = new_node
        # Update head to new node regardless
        self.head = new_node
        self.size += 1

    def find(self, quality):
        """Return an item from this linked list satisfying the given quality.
        Best case running time: Omega(1) if item is near the head of the list.
        Worst case running time: O(n) if item is near the tail of the list or
        not present and we need to loop through all n nodes in the list."""
        # Start at the head node
        node = self.head  # Constant time to assign a variable reference
        # Loop until the node is None, which is one node too far past the tail
        while node is not None:  # Up to n iterations if we don't exit early
            # Check if this node's data satisfies the given quality function
            if quality(node.data):  # Constant time to call quality function
                # We found data satisfying the quality function, so exit early
                return node.data  # Constant time to return data
            # Skip to the next node
            node = node.next  # Constant time to reassign a variable
        # We never found data satisfying quality, but have to return something
        return None  # Constant time to return None

    def replace(self, old_item, new_item):
        """Replace the given old_item in this linked list with given new_item
        using the same node, or raise ValueError if old_item is not found.
        Best case running time: O(1) in any of the following scenarios: linkedlist is empty,
        data to be replaced is at the head or tail, or data to be replaced is the first item in linked list
        Worst case running time: O(N) item to be replaced is at the Nth position"""
        
        # PSEUDO BRAINSTORM
        # Iterate through nodes using .next . If node is equal to old_item, replace with new_item using .data
        # How to find size?
        # account for empty
        
        # Not necessary. These will already be O(1) operations
        # if self.is_empty():
        #     raise ValueError('Linked list is empty')
        # if self.head.data == old_item:
        #     self.head.data = new_item
        #     return self.head

        # Added for speed increase for certain scenarios
        if self.tail.data == old_item:
            self.tail.data = new_item
            return self.tail
        
        # Removed because it adds more time complexity. Replaced with catch-all at end
        # if self.find(lambda item: item == old_item) == None:
        #     raise ValueError('Data not found: {}'.format(old_item))

        current_node = self.head

        while current_node is not None:
            if current_node.data == old_item:
                current_node.data = new_item
                return current_node
            current_node = current_node.next
        # Used as a catch-all for scenarios where linked list is empty and data not in linked list
        raise ValueError('Data not found: {}'.format(old_item))

        # WHY THIS NO WORKIE!!??? How to get it to return the node rather than data in node?
        # while found == False:
        #     found_node = self.find(lambda item: item == old_item)
        #     found_node.data = new_item.data
        #     found = True

    def delete(self, item):
        """Delete the given item from this linked list, or raise ValueError.
        Best case running time: O(1) the node we're looking to delete is the first one
        Worst case running time: O(n) the node we're looking to delete is the nth one"""
        # Start at the head node
        node = self.head
        # Keep track of the node before the one containing the given item
        previous = None
        # Create a flag to track if we have found the given item
        found = False
        # Loop until we have found the given item or the node is None
        while not found and node is not None:
            # Check if the node's data matches the given item
            if node.data == item:
                # We found data matching the given item, so update found flag
                found = True
            else:
                # Skip to the next node
                previous = node
                node = node.next
        # Check if we found the given item or we never did and reached the tail
        if found:
            # Check if we found a node in the middle of this linked list
            if node is not self.head and node is not self.tail:
                # Update the previous node to skip around the found node
                previous.next = node.next
                # Unlink the found node from its next node
                node.next = None
            # Check if we found a node at the head
            if node is self.head:
                # Update head to the next node
                self.head = node.next
                # Unlink the found node from the next node
                node.next = None
            # Check if we found a node at the tail
            if node is self.tail:
                # Check if there is a node before the found node
                if previous is not None:
                    # Unlink the previous node from the found node
                    previous.next = None
                # Update tail to the previous node regardless
                self.tail = previous
            self.size -= 1
        else:
            # Otherwise raise an error to tell the user that delete has failed
            raise ValueError('Item not found: {}'.format(item))


def test_linked_list():
    ll = LinkedList()
    print(ll)

    print('Appending items:')
    ll.append('A')
    print(ll)
    ll.append('B')
    print(ll)
    ll.append('C')
    print(ll)
    print('head: {}'.format(ll.head))
    print('tail: {}'.format(ll.tail))
    print('size: {}'.format(ll.size))
    print('length: {}'.format(ll.length()))

    print('Getting items by index:')
    for index in range(ll.size):
        item = ll.get_at_index(index)
        print('get_at_index({}): {!r}'.format(index, item))

    print('Deleting items:')
    ll.delete('B')
    print(ll)
    ll.delete('C')
    print(ll)
    ll.delete('A')
    print(ll)
    print('head: {}'.format(ll.head))
    print('tail: {}'.format(ll.tail))
    print('size: {}'.format(ll.size))
    print('length: {}'.format(ll.length()))


if __name__ == '__main__':
    test_linked_list()