single linked list

single_linked_list.py

# -*- coding: utf-8 -*-

import sys

class _ListNode(object):
    def __init__(self, obj):
        self._obj = obj
        self._next = None

    def _append(self, obj):
        self._next = obj

    def __eq__(self, obj):
        return self._obj == obj

    def __repr__(self):
        return repr(self._obj)


class LinkedList(object):

    def __init__(self, sequence=None):
        self._len = 0
        self._last = None
        self._first = None
        if sequence:
            self.extend(sequence)

    def append(self, obj):
        item = _ListNode(obj)

        if not self._first:
            self._first = item
            self._last = item
            self._len += 1
            return

        self._last._append(item)
        self._last = item
        self._len += 1

    def _getnode_and_prev(self, index):

        if index < 0:  # inverse index list[-1] gets the last item
            item = self._len + index

        if index > self._len:
            raise IndexError("list index out of range")

        prev = None
        node = self._first

        i = 0

        while i < index:
            prev = node
            node = node._next
            i += 1

        return (prev, node)

    def _getnode(self, index):

        if index < 0:  # inverse index list[-1] gets the last item
            item = self._len + index

        if index == self._len - 1:
            return last

        if index > self._len:
            raise IndexError("list index out of range")

        node = self._first

        i = 0

        while i < index:
            node = node._next
            i += 1

        return node

    def __getitem__(self, index):
        return self._getnode(index)._obj

    def __setitem__(self, index, item):
        self._getnode(index)._obj = item

    def insert(self, index, value):
        node = _ListNode(obj)

        if index == 0:
            old_first = self._first
            self._first = node
            node._append(old_first)
            self._len += 1
            return

        if index == self._len:
            self.append(value)

        previous_node = self[index-1]
        next_node = previous_node._next
        previous_node._append(node)
        node._append(next_node)

    def extend(self, sequence):
        for item in sequence:
            self.append(item)

    def __iadd__(self, iterable):
        self.extend(iterable)

    def index(self, obj):
        for i in self:
            if i == obj:
                return i._obj

        raise ValueError("{} is not in list".format(obj))

    def __delitem__(self, index):
        self.pop(index)

    def pop(self, index=-1):
        prev, node = self._getnode_and_prev(index)

        self._len -= 1

        if prev and node is not self._last:
            prev._next = node._next
            return node._obj

        if node is self._last:
            self._last = prev
            return node._obj

        if node is self._first:
            self._first = node._next
            return node._obj

    def __iter__(self):

        node = self._first

        yield node._obj

        while node._next:
            node = node._next
            yield node._obj

    def __len__(self):
        return self._len

    def __repr__(self):
        return repr([i for i in self])

    def _index(self, value, start=0, stop=sys.maxint):
        if stop is not None:
            if stop < 0:
                stop = self._len  - stop
            elif stop > self._len:
                self.stop = self._len

        i = 0
        prev = None
        node = self._first

        while i < stop:
            prev = node
            node = node._next
            if i < start:
                i += 1
                continue
            if node._obj == value:
                return (i, prev, node)
        raise ValueError("{} is not i in list".format(repr(obj)))

    def index(self, value, start=0, stop=sys.maxint):
        i, node, prev = self._index(value, start, stop)
        return i

    def remove(self, value):
        i, node, prev = self._index(value)

        if prev is None:
            self._first = node._next
            return

        if node is self._last:
            self._last = prev
            return

        self.prev = self.node._next


    def __getslice__(self, start=0, end=sys.maxint, step=1):
        # list[i:j]
        if step < 0:
            raise AttributeError("single linked list cannot iterate backwards.")

        if end > self._len:
            end = self._len

        node = self._getnode(start)

        new_list = self.__class__()

        new_list.append(node._obj)
        while start <= end:
            start += step
            if node._next == None:
                break

            for i in range(step):
                node = node._next
            new_list.append(node._obj)

        return new_list

    def sort(self):
        raise NotImplementedError("cannot sort a single linked list.")