链表的实现

链表的实现

BeiJiXS

2021 年 06 月 04 日

275 次浏览

暂无评论

2815字数

Python

## 链表是什么?

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

> A <==>B<==>C

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

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

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

## 代码

下面的代码并不完整, 高效;只能用于理解链表的基本形态
</div>

```python
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))

```

最后修改：2021 年 06 月 04 日