|
定义了节点的类:class Node(object):
def __init__(self, elem):
self.elem = elem
self.next = None
self.prev = None
定义了双向链表及函数:
class DoubleLinkList(object):
'''双链表'''
def __init__(self, node = None):
self.__head = node
def length(self):
'''求长度'''
#创建游标,从头数到尾,记录当前访问到哪个位置,用来移动,遍历节点
cur = self.__head
#count记录数量
count = 0
while cur != None :
count += 1
cur = cur.next
return count
def travel(self):
'''遍历'''
cur = self.__head
while cur != None:
print(cur.elem, end = " ") #将换行变为空格输出
cur = cur.next
print('\n')
def add(self,item):
'''链表头部添加元素,头插法'''
node = Node(item)
node.next = self.__head
self.__head = node
node.next.prev = node
def append(self,item): #注意此处的item不是节点,而是具体的元素
'''尾部插入节点,尾插法'''
node = Node(item)
cur = self.__head
if self.is_empty():
self.__head = node
else:
while cur.next != None:
cur = cur.next
cur.next = node
node.prev = node
def insert(self,pos,item):
'''指定位置添加节点
:param pose 从0开始索引
'''
if pos <= 0:
self.add(item)
elif pos > (self.length() - 1):
self.append(item)
else:
# 在中间某一个位置添加元素
# 角标为的位置添加元素, 遍历的时候需要获取1位置的前端节点
index = 0
cur = self.__head
while index < pos:
index = index + 1
cur = cur.next
# 循环退出之后 cur 指向的就是前端节点
node = Node(item)
node.next = cur
node.prev = cur.prev
cur.prev.next = node
cur.prev = node
然后在主函数里进行测试:
if __name__ == "__main__":
dll = DoubleLinkList()
dll.append(1)
dll.append(4)
dll.append(5)
dll.travel()
dll.add(2)
dll.travel()
print(dll.length())
dll.insert(3,9)
dll.travel()
运行之后就会在屏幕里不断输出,不知道什么原因,求请大神指导,非常感谢!!
|
|