"""
双链表三种插入法实现并显示
"""
# 定义节点类
class DoubleLinkNode():
def __init__(self,data = None,prior = None, next = None):
self.data = data
self.prior = prior
self.next = next
class DoubleLinkList():
def __init__(self):
self.header = None
self.length = 0
"""头部插入"""
def InsertInHead(self,node):
if self.header == None:
self.header = node
else:
node.next = self.header
self.header.prior = node
self.header = node
self.length += 1
"""尾部插入"""
def InsertInTail(self,node):
cur = self.header
if self.header is None:
self.header = node
else:
while cur.next is not None: # 让cur指针移动到最右边的一个节点
cur = cur.next
cur.next = node #在尾部插入新节点
node.prior = cur # 新节点连接到上一个节点
self.length += 1
"""根据索引位置插入节点"""
def InsertByIndex(self,node,index):
assert index != 0 or index <= self.length, '超出索引'
if index <= 1: # 头部插入
self.InsertInHead(node)
elif index > self.length: #尾部插入
self.InsertInTail(node)
else: #两节点之间插入
cur = self.header
for i in range(1,index-1):
cur = cur.next
node.next = cur.next
cur.next.prior = node
cur.next = node
node.prior = cur
self.length += 1
"""判断链表是否为空"""
def IsEmpty(self):
if self.header is None:
return True
"""链表遍历显示"""
def Show(self):
cur = self.header
if self.IsEmpty():
print("空链表")
while cur:
if cur.next is not None:
print(cur.data,end='<->')
else:
print(cur.data)
cur = cur.next
"""双链表插入实例化"""
if __name__ == "__main__":
node = DoubleLinkNode(1) # 创建头节点 header:[None,2,None]
DLinkList = DoubleLinkList() #实例化链表操作对象
DLinkList.InsertInHead(node) #
DLinkList.Show()
"""头部插入一个节点"""
node2 = DoubleLinkNode(2)
node3 = DoubleLinkNode(3)
DLinkList.InsertInHead(node2)
DLinkList.InsertInHead(node3)
DLinkList.Show()
"""以循环的形式在头部插入节点"""
for data in range(4,7):
nodei = DoubleLinkNode(data)
DLinkList.InsertInHead(nodei)
DLinkList.Show()
""" 尾部插入一个节点"""
DLinkList1 = DoubleLinkList() # 实例化链表操作对象
node = DoubleLinkNode(0)
DLinkList1.InsertInTail(node)
DLinkList1.Show()
node2 = DoubleLinkNode(2)
node3 = DoubleLinkNode(3)
DLinkList1.InsertInTail(node2)
DLinkList1.InsertInTail(node3)
DLinkList1.Show()
"""以循环的形式在尾部插入"""
for data in range(4,7):
new_node = DoubleLinkNode(data)
DLinkList1.InsertInTail(new_node)
DLinkList1.Show()
"""任意位置插入节点"""
DLinkList1.InsertByIndex(DoubleLinkNode(1),1) #头部插入
DLinkList1.InsertByIndex(DoubleLinkNode(2), 1)#头部插入
DLinkList1.InsertByIndex(DoubleLinkNode(1), 9)#尾部插入
DLinkList1.InsertByIndex(DoubleLinkNode(1), 4)#两节点之间插入
DLinkList1.Show()
|
