链表是什么?

用三个小朋友打比方,分别是A,B,C;现在B的左手拉着A的右手, 右手拉着C的左手; 如下

A <==>B<==>C

根据上面的类推, 如果有5个小朋友的话,就是下面这种情况:

A <==>B<==>C<==>D<==>E

可以看出, 除了A和E, 中间的任意一个人都能够直接找到他的左边和右边的人, 他们可以不站在一排, 但是他们的手还是拉在一起的, 所以链表是有序的, 但是数据是离散的.

代码

class Item(object):
    def __init__(self, val, perv=None, next=None):
        self.val = val
        self.perv = perv
        self.next = next

    def __str__(self):
        return '<Item {}>'.format(self.val)

    __repr__ = __str__


class LinkList(object):
    def __init__(self):
        self.header = None
        self.tail = None
        self._len = 0

    def append(self, val):
        node = Item(val)
        if self.tail is None:
            self.header = node
            self.tail = node
        else:
            node.perv, self.tail.next, self.tail = self.tail, node, node
        self._len += 1

    def _get_index_item(self, index):
        return reversed(self) if index < 0 else self, abs(index) - 1 if index < 0 else index

    def insert(self, index, val):
        items, index = self._get_index_item(index)
        for i, item in enumerate(items):
            if i == index:
                node = Item(val)
                perv = item.perv
                perv.next = node
                node.perv, node.next = perv, item
                item.perv = node
                self._len += 1
                break
        else:
            self.append(val)

    def remove(self, index):
        item = self[index]
        perv, next = item.perv, item.next
        perv.next, next.perv = next, perv
        del item
        self._len -= 1

    def __len__(self):
        return self._len

    def __getitem__(self, index):
        items = reversed(self) if index < 0 else self
        index = abs(index) - 1 if index < 0 else index
        for i, val in enumerate(items):
            if i == index:
                return val
        else:
            raise IndexError('Index range error')

    def __setitem__(self, index, value):
        self[index].val = value

    def _iter(self, revers=False):
        current = self.tail if revers else self.header
        while current:
            yield current
            current = current.perv if revers else current.next

    def __iter__(self):
        return self._iter()

    def __reversed__(self):
        return self._iter(True)


if __name__ == '__main__':
    a = LinkList()
    a.append(1)
    a.append(2)
    a.append(3)
    for _ in a:
        print(_)
    print(list(reversed(a)))
    print(a[-2])
    a[2] = 100
    print(a[2])
    a.insert(10, 999)
    a.insert(-1, 152)
    print(list(a))
    print(len(a))
    a.remove(1)
    print(list(a))