Python 双向链表的实现
2021-03-29 06:27
标签：ini span pytho current index one object main 头部 概念：什么是双向链表 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。 所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
代码简单实现： Python 双向链表的实现 标签：ini span pytho current index one object main 头部 原文地址：https://www.cnblogs.com/zhaoxianxin/p/13612414.html
"""
author: zhao xian xin
不积跬步无以至千里
"""
#定义双向链表 每一个结点
class Node(object):
def __init__(self, item):
self.previous = None
self.item = item
self.next = None
# 定义链表
class TwoWayLinkList():
""" 链表基本属性 """
def __init__(self):
self.hearder = None
self.length = 0
""" 头部插入 """
def firstAdd(self, node):
if self.hearder == None:
self.hearder = node
else:
node.next = self.hearder
self.hearder.previous = node
self.hearder = node
self.length += 1
""" 尾部插入 """
def tailAdd(self, node):
if self.length == 0:
self.firstAdd(node)
else:
currentNode = self.hearder
for i in range(self.length - 1):
currentNode = currentNode.next
node.previous = currentNode
currentNode.next = node
self.length += 1
""" 根据指定索引 插入 对应结点 """
def indexInsert(self, index, node):
assert index != 0 or index "超出索引"
if index == 1:
self.firstAdd(node)
elif index == 2:
node.next = self.hearder.next
node.prevopus = self.hearder
self.hearder.next = node
self.length += 1
elif index > self.length:
self.tailAdd(node)
else:
currentNode = self.hearder
for i in range(1, index - 1):
currentNode = currentNode.next
node.prevopus = currentNode
node.next = currentNode.next
currentNode.next.previous = node
currentNode.next = node
self.length += 1
""" 根据指定位置 删除 结点"""
def delNode(self, index):
""" 判断删除的索引是否在标准范围之中 """
assert index != 0 or index "超出索引"
if index == 1:
self.hearder = self.hearder.next
self.hearder.previous = None
elif index == 2:
self.hearder.next = self.hearder.next.next
self.hearder.next.next.previous = self.hearder
else:
currentNode = self.hearder
for i in range(1, index - 1):
currentNode = currentNode.next
currentNode.next = currentNode.next.next
self.length -= 1
""" 遍历节点"""
def rangeNode(self):
assert self.length != 0 , "链表为空"
currentNode = self.hearder
for i in range(self.length):
element = currentNode.item
currentNode = currentNode.next
print(element, end=" ")
""" 结点之间的排序 不许改变指针位置， 只需改变链表中元素位置 """
def sortNode(self):
pass
""" 快速排序 """
for i in range(self.length):
currentNode = self.hearder
for j in range(0, self.length - i - 1):
if currentNode.item > currentNode.next.item:
mid = currentNode.item
currentNode.item = currentNode.next.item
currentNode.next.item = mid
""" 别忘记 交换节点 """
currentNode = currentNode.next
if __name__ == "__main__":
node = Node(2)
t = TwoWayLinkList()
t.firstAdd(node)
print(t.rangeNode())
""" 尾部 插入元素 """
t.tailAdd(Node(1))
t.tailAdd(Node(4))
print(t.rangeNode())
""" 头部插入位置 """
t.firstAdd(Node(3))
print(t.rangeNode())
""" 根据索引插入对应的位置 """
t.indexInsert(6, Node(5))
print(t.rangeNode())
""" 根据指定位置 删除节点 """
t.delNode(4)
print(t.rangeNode())
""" 节点之间的 排序 """
t.sortNode()
print("======排序======")
print(t.rangeNode())
上一篇：Python - 虚拟环境
下一篇：jmeter跨线程调用参数