Linked Lists

link_lists.py

"""Python 3 implementation of a linked list and a circular link list."""
import collections


class LinkedNode(object):
    def __init__(self, value):
        self.next = None
        self.value = value


class LinkedList(collections.abc.Iterable):

    def __init__(self):
        self.start = None

    def insert(self, value, index=0):
        new_node = LinkedNode(value)
        if index == 0:
            # Special case for inserting a the beggingn of the list.
            new_node.next = self.start
            self.start = new_node
        else:
            for i, node in enumerate(self._iter_nodes(), 1):
                if i == index:
                    # Here we are getting the node before the insert
                    # location use for the insertion.
                    new_node.next = node.next
                    node.next = new_node
                    break
            else:
                raise IndexError(index)

    def append(self, value):
        """Append a value to the list.

        This is pretty inefficient as there is it loops through the
        list twice, once here to get the index and a second time when
        inserting.
        """
        i = 0
        for i, _ in enumerate(self._iter_nodes(), 1):
            pass
        self.insert(value, i)

    def pop(self, index=0):
        if not self.start:
            raise IndexError(index)
        if index == 0:
            value = self.start.value
            self.start = self.start.next
            return value
        for i, node in enumerate(self._iter_nodes(), 1):
            if i == index:
                # Getting the node before the one we want to delete.
                if not node.next:
                    # We are trying to delete the node just outside of
                    # the list, fail.
                    raise IndexError(index)
                value = node.next.value
                node.next = node.next.next
                return value
        else:
            raise IndexError(index)

    def _iter_nodes(self):
        node = self.start
        while True:
            if node is None:
                return
            yield node
            node = node.next

    def __iter__(self):
        for node in self._iter_nodes():
            yield node.value

    def __repr__(self):
        return '[{}]'.format(', '.join(repr(n) for n in self))


def test_linked_list():
    # Started on testing the implementation, but not finished yet.
    l = LinkedList()
    for v in range(10):
        l.insert(v)
    assert list(l) == [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    l.append(1)
    assert list(l) == [9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1]
    assert l.pop() == 9
    assert list(l) == [8, 7, 6, 5, 4, 3, 2, 1, 0, 1]
    assert l.pop(9) == 1


class CircularLinkedList(collections.abc.Iterable):

    """Circular linked list will append to the list in O(1) instead of
    the above implementation using O(2n).
    """

    def __init__(self):
        self.last = None

    def append(self, value):
        new_node = LinkedNode(value)
        self._insert_after(self.last, new_node)
        self.last = new_node

    def _insert_after(self, node, new_node):
        if not node:
            new_node.next = new_node
        else:
            new_node.next = node.next
            node.next = new_node

    def insert(self, value, index=0):
        new_node = LinkedNode(value)
        for i, node in enumerate(self._iter_nodes()):
            if i == index:
                self._insert_after(node, new_node)
        else:
            raise IndexError(index)
        if not self.last:
            # This is an empty list, set the last node as this new_node.
            self.last = new_node

    def pop(self, index=0):
        if not self.last:
            raise IndexError(index)
        if index == 0:
            node = self.last.next
            if node is self.last:
                self.last = None
            else:
                self.last.next = self.last.next.next
            return node.value
        for i, node in enumerate(self._iter_nodes(), 1):
            if i == index:
                if node is self.last:
                    # We are trying to pop the node outside of the
                    # list, if we do not check for this we will delete
                    # the first node from the list.
                    raise IndexError
                old_node = node.next
                node.next = node.next.next
                if self.last is old_node:
                    # If we delete the last node make sure we reset the
                    # last node to the one before it.
                    self.last = node
                return old_node.value
        else:
            raise IndexError(index)

    def _iter_nodes(self):
        node = self.last
        if not node:
            # Empty list.
            return
        # By getting the next node before yielding we always start with
        # the first node.
        while True:
            node = node.next
            yield node
            if node is self.last:
                # If we yielded the last node we are done.
                return

    def __iter__(self):
        for node in self._iter_nodes():
            yield node.value

    def __repr__(self):
        return '[{}]'.format(', '.join(repr(n) for n in self))