链表是什么?
用三个小朋友打比方,分别是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))