每一个节点包含值和指向下一个节点的指针。当前节点指向下一个节点是一个对象,直接打印是一串不容易识别的序列号,因此把下一个节点的值装入到当前节点,易于阅读和调试。
import random
VALUE = 'value'
NEXT = 'next'
class Node:
def __init__(self, value):
self.value = value
self.next = None
def __str__(self):
next_v = None
if self.next is not None:
next_v = self.next.value
return str({VALUE: self.value, NEXT: next_v})
# 加入到LinkList的节点
class LinkList(object):
def __init__(self):
self.head = None
def append(self, value):
node = Node(value)
node.next = None
if self.head is None:
self.head = node
else:
cur = self.head
while True:
if cur.next is None:
break
else:
cur = cur.next
cur.next = node
# 根据一个值查找该节点
def find(self, v):
node = Node
cur = self.head
while cur is not None:
if cur.value == v:
node = cur
break
cur = cur.next
return node
# 在指定的链表位置pos处插入节点node
def insert(self, pos, node):
if pos == 0:
node.next = self.head
self.head = node
else:
pos_node = self.get_node_by_pos(pos)
pos_pre_node = self.get_node_by_pos(pos - 1)
pos_pre_node.next = node
node.next = pos_node
# 删除位于链表pos位置的节点
def delete_node(self, pos):
# 删除最头部节点
if pos == 0:
# 如果链表长度为1,直接将链表的head置为None
if self.size() == 1:
self.head = None
else:
next_node = self.get_node_by_pos(pos + 1)
self.head = next_node
return
# 删除最尾部节点
if pos == (self.size() - 1):
pre_node = self.get_node_by_pos(pos - 1)
pre_node.next = None
return
# 删除介于中间部位的节点(非最头和最尾节点)
pre_node = self.get_node_by_pos(pos - 1)
next_node = self.get_node_by_pos(pos + 1)
pre_node.next = next_node
def items(self):
nodes = []
cur = self.head
while cur is not None:
nodes.append(cur)
cur = cur.next
return nodes
def size(self):
count = 0
cur = self.head
while cur is not None:
count = count + 1
cur = cur.next
return count
# 返回链表对应序号位置的节点。
def get_node_by_pos(self, pos):
count = 0
node = None
cur = self.head
while cur is not None:
if count == pos:
node = cur
break
cur = cur.next
count = count + 1
return node
# 在列表中的随机位置插入一个值v
def random_insert(link, v):
print('--')
pos = random.randint(0, link.size() - 1)
print('插入pos =', pos)
link.insert(pos, Node(v))
def app():
link = LinkList()
for i in range(5):
link.append(random.randint(1, 10000))
print('-')
print('原始随机链表')
print_node(link)
random_insert(link, 'zhang')
print_node(link)
random_insert(link, 'phil')
print_node(link)
print('---')
print('删除 pos = 0')
link.delete_node(0)
print_node(link)
print('---')
print('删除 pos = 1')
link.delete_node(1)
print_node(link)
print('---')
print('删除 pos = ', link.size() - 1)
link.delete_node(link.size() - 1)
print_node(link)
def print_node(link):
for n in link.items():
print('节点', n)
print('长度', link.size())
if __name__ == '__main__':
app()
输出:
-
原始随机链表
节点 {'value': 8018, 'next': 4938}
节点 {'value': 4938, 'next': 3066}
节点 {'value': 3066, 'next': 579}
节点 {'value': 579, 'next': 5003}
节点 {'value': 5003, 'next': None}
长度 5
--
插入pos = 1
节点 {'value': 8018, 'next': 'zhang'}
节点 {'value': 'zhang', 'next': 4938}
节点 {'value': 4938, 'next': 3066}
节点 {'value': 3066, 'next': 579}
节点 {'value': 579, 'next': 5003}
节点 {'value': 5003, 'next': None}
长度 6
--
插入pos = 1
节点 {'value': 8018, 'next': 'phil'}
节点 {'value': 'phil', 'next': 'zhang'}
节点 {'value': 'zhang', 'next': 4938}
节点 {'value': 4938, 'next': 3066}
节点 {'value': 3066, 'next': 579}
节点 {'value': 579, 'next': 5003}
节点 {'value': 5003, 'next': None}
长度 7
---
删除 pos = 0
节点 {'value': 'phil', 'next': 'zhang'}
节点 {'value': 'zhang', 'next': 4938}
节点 {'value': 4938, 'next': 3066}
节点 {'value': 3066, 'next': 579}
节点 {'value': 579, 'next': 5003}
节点 {'value': 5003, 'next': None}
长度 6
---
删除 pos = 1
节点 {'value': 'phil', 'next': 4938}
节点 {'value': 4938, 'next': 3066}
节点 {'value': 3066, 'next': 579}
节点 {'value': 579, 'next': 5003}
节点 {'value': 5003, 'next': None}
长度 5
---
删除 pos = 4
节点 {'value': 'phil', 'next': 4938}
节点 {'value': 4938, 'next': 3066}
节点 {'value': 3066, 'next': 579}
节点 {'value': 579, 'next': None}
长度 4