linkedlist python implementation

linkedlist.py

#!python

class Node(object):

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

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


class LinkedList(object):

    def __init__(self, iterable=None):
        """Initialize this linked list and append the given items, if any"""
        """Best case Omega(1)"""
        """Worst case O(n)"""
        self.head = None
        self.tail = None
        self.size = 0
        if iterable:
            for item in iterable:
                self.append(item)

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

    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."""
        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
        return result  # Constant time to return a list

    def __getitem__(self, arg):
        """Get the item at the index, or raise KeyError if not an int"""
        """Best case Omega(1)"""
        """Worst case O(n)"""
        if type(arg) is not int:
            raise TypeError

        # If argument is over list size, raise ValueError
        if arg >= self.length() or arg < -self.length():
            raise IndexError

        # Use modulus operator, so index can use negatives
        counter = arg % self.length()
        currentIndex = 0

        if counter == self.length():
            return self.last()

        current = self.head
        while current is not None:
            if counter == currentIndex:
                return current.data
            currentIndex += 1
            current = current.next
    def as_list(self):
        """Return a list of all items in this linked list"""
        items = []
        current = self.head
        while current is not None:
            items.append(current.data)
            current = current.next
        return items


    def get_at_index(self, index):
        """ Gets data at an index"""
        at_index = self._at_index(index)

        if at_index is None:
            return None

        return at_index.data
    def is_empty(self):
        """Return True if this linked list is empty, or False otherwise"""
        """Best case Omega(1)"""
        """Worst case O(1)"""
        return self.head is None

    def length(self):
        """Return the length of this linked list"""
        """Best case Omega(1)"""
        """Worst case O(1)"""
        return self.size

    def append(self, item):
        """Insert the given item at the tail of this linked list"""
        new_node = Node(item)
        # Check if list is empty
        if self.head is None:
            self.head = new_node
        # Otherwise insert after tail node
        else:
            self.tail.next = new_node
        # Update tail node
        self.tail = new_node
        # Update length
        self.size += 1

    def prepend(self, item):
        """Insert the given item at the head of this linked list"""
        """Best case Omega(1)"""
        """Worst case O(1)"""
        new_node = Node(item)
        # Insert before head node
        new_node.next = self.head
        # Update head node
        self.head = new_node
        # Check if list was empty
        if self.tail is None:
            self.tail = new_node
        # Update length
        self.size += 1

    def delete(self, item):
        """Delete the given item from this linked list, or raise ValueError"""
        """Best case Omega(1)"""
        """Worst case O(n)"""
        current = self.head
        previous = None
        found = False
        # Find the given item
        while not found and current is not None:
            if current.data == item:
                found = True
            else:
                previous = current
                current = current.next
        # Delete if found
        if found:
            if current is not self.head and current is not self.tail:
                previous.next = current.next
                current.next = None
            if current is self.head:
                self.head = current.next
            if current is self.tail:
                if previous is not None:
                    previous.next = None
                self.tail = previous
            # Update length
            self.size -= 1
        else:
            # Otherwise raise an error to tell the user that delete has failed
            raise ValueError('Item not found: {}'.format(item))


    def size(self):
        """ Gets the size of the Linked List
        AVERAGE: O(1)
        """
        return self.count

    def delete_at_index(self, index):
        """Delete the item at the given index from this linked list, or raise ValueError"""

        if type(index) is not int:
            raise TypeError

        # If argument is over list size, raise ValueError
        if index >= self.length() or index < -self.length():
            raise IndexError

        # Use modulus operator, so index can use negatives
        counter = index % self.length()
        currentIndex = 0

        current = self.head
        previous = None
        found = False

        # Find the given item
        while not found and current is not None:
            if currentIndex == counter:
                found = True
            else:
                previous = current
                current = current.next
                currentIndex += 1
        if found:
            if current is not self.head and current is not self.tail:
                previous.next = current.next
                current.next = None
            if current is self.head:
                self.head = current.next
            if current is self.tail:
                if previous is not None:
                    previous.next = None
                self.tail = previous
            # Update length
            self.size -= 1
        else:
            raise ValueError('Item not found: {}'.format(item))

    def iterable(self):
        data = []

        current = self.head
        while current is not None:
            data.append(current.data)

            current = current.next

        return data

    def _find_node(self, data):
        current = self.head

        while current is not None:
            if current.data == data:
                return current

            current = current.next

    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: ??? under what conditions? 
        Worst case running time: ??? under what conditions? [TODO]"""
        if not (0 <= index < self.size):
            raise ValueError('List index out of range: {}'.format(index))

        counter = self.head
        for i in range(index):
            counter = counter.next
        return counter.data

    def insert(self, index, data):
        """ Inserts data at a specific index
        BEST: O(1)
        WORST: O(n)
        """
        if index == 0:
            self.prepend(data)
            return

        at_index = self._at_index(index - 1)

        if at_index is None:
            raise IndexError

        if at_index.next is None:
            self.append(data)
            return

        new_node = Node(data)

        new_node.next = at_index.next
        at_index.next = new_node

    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: ??? under what conditions? [TODO]
        Worst case running time: ??? under what conditions? [TODO]"""
        # 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))
        if index == 0:
            self.prepend(item)
        elif index == self.size:
            self.append(item)
        else:
            new_node = Node(item)
            node = self.head
            previous = None
            for i in range(index):
                previous = node
                node = node.next

            previous.next = new_node
            new_node.next = node
            self.size += 1

    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: ??? under what conditions? [TODO]
        Worst case running time: ??? under what conditions? [TODO]"""
        if old_item == new_item:
            return
        node = self.head
        while node is not None:
            if node.data == old_item:
                node.data = new_item
                return
            node = node.next
        raise ValueError('Item not found: {}'.format(old_item))

    def find(self, condition):
        """Return an item in this linked list satisfying the given condition"""
        """Best case Omega(1)"""
        """Worst case O(n)"""
        current = self.head  # Start at the head node
        while current is not None:
            if condition(current.data):
                return current.data
            current = current.next  # Skip to the next node
        return None



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('testing: 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()))

    print("testing: Linked List replace ___________________")
    ll = LinkedList(['A', 'B', 'C'])
    ll.replace('A', 'D')
    print(ll)

    ll = LinkedList(['A', 'B', 'C'])
    print(ll)
    print("testing: insert_at_index ___________________")
    print('size: {}'.format(ll.size))
    ll.insert_at_index(0, 'AA')
    print(ll)
    print("testing: insert_at_index 0, 'AA'___________________")
    ll.insert_at_index(2, 'BB')
    print("testing: insert_at_index 2, 'BB'___________________")
    print(ll)

if __name__ == '__main__':
    test_linked_list()