class doublelinked():
def __init__(self, *args):
self.__head = head = []
self.__head += [None, head, head]
self.__map = {}
for i in args:
self.append(i)
# 插入到表尾
def append(self, data):
head = self.__head
last = head[1]
node = [data, last, head]
head[1] = last[2] = self.__map[data] = node
return node
def prepend(self, data):
head = self.__head
last = head[2]
node = [data, head, last]
head[2] = last[1] = self.__map[data] = node
return node
def insertafter(self, node, data):
next = node[2]
n = [data, node, next]
node[2] = next[1] = self.__map[data] = n
return n
def remove(self, node):
data, prev, next = node
prev[2] = next
next[1] = prev
node[1] = node[2] = node
del self.__map[data]
def removebydata(self, data):
self.remove(self.__map[data])
def __iter__(self):
head = self.__head
curr = head[2]
while curr is not head:
yield curr
curr = curr[2]
def __getitem__(self, data):
return self.__map[data]
def __reversed__(self):
head = self.__head
curr = head[1]
while curr is not head:
yield curr
curr = curr[1]
def __str__(self):
return ", ".join([str(i[0]) for i in self])
dl = doublelinked('a','b')
dl.append('c')
dl.append('d')
dl.append('e')
dl.append('f')
print(dl)
print ("------------------")
dl.removebydata('b')
print(dl)
采用一个固定有三个元素的list对象作为表结点机构,list对象的第一个元素是value,第二个元素是指向前一个表结点的引用(指针),第三个元素是指向后一个表结点的引用(指针),链表的头结点不存放数据,它作为一个哨兵,作为判断链表是否为空、链表遍历结束的标志。