一、链表-实现-判空-长度-遍历-增加结点:
- 链表的实现、判断是否为空、长度、遍历
- 头部增加新结点
- 尾部增加结点
- 指定位置增加结点
- 删除结点
- 查找节点是否存在
# 链表节点实现
class SingleNode(object):
def __init__(self, item):
# item：存放元素
self.item = item
# next:标识下一个结点
self.next = None
# 单链表的实现
class SingleLinkList(object):
def __init__(self, node=None):
# head：首节点
self.head = node
# 判断链表是否为空
def is_empty(self):
if self.head is None:
return True
else:
return False
# 获取链表长度 length()
def length(self):
# 游标记录当前所在的位置
cur = self.head
# 记录链表的长度
count = 0
while cur is not None:
cur = cur.next
count += 1
return count
# 遍历链表 travel()
def travel(self):
# 游标记录当前所在的位置
cur = self.head
while cur is not None:
print(cur.item)
cur = cur.next
# 头部增加结点add()
def add(self, item):
# 新节点存储新数据
node = SingleNode(item)
node.next = self.head
self.head = node
# 尾部增加结点append()
def append(self, item):
# 新节点存储新数据
node = SingleNode(item)
# 判断是否是空链表
if self.is_empty():
self.head = node
else:
cur = self.head
# 找到尾结点
while cur.next is not None:
cur = cur.next
cur.next = node
# 指定位置增加结点：insert(pos, item)
def insert(self, pos, item):
# 头部增肌新结点
if pos <= 0:
self.add(item)
elif pos >= self.length():
self.append(item)
else:
# 游标
cur = self.head
# 计数
count = 0
# 新结点
node = SingleNode(item)
# 1、找到插入位置的前一个结点
while count < pos - 1:
cur = cur.next
count += 1
# 2、完成插入新结点
node.next = cur.next
cur.next = node
# 删除结点 remove(item)
def remove(self, item):
# 游标
cur = self.head
# 辅助游标
pre = None
while cur is not None:
# 找到了要删除的元素
if cur.item == item:
# 要删除的元素在头部
if cur == self.head:
self.head = cur.next
else:
pre.next = cur.next
return
# 没有找到要删除的元素
else:
pre = cur
cur = cur.next
# 查找节点是否存在
def search(self, item):
# 游标
cur = self.head
while cur is not None:
# 找到了指定结点
if cur.item == item:
return True
cur = cur.next
return False
if __name__ == '__main__':
# 节点
node1 = SingleNode(10)
print(node1.item)
print(node1.next)
# 链表
link1 = SingleLinkList()
print(link1.head)
link2 = SingleLinkList(node1)
print(link2.head.item)
# 判空
print(link1.is_empty())
print(link2.is_empty())
# 长度
print(link1.length())
print(link2.length())
# 遍历
link2.travel()
# 头部增加结点
print("头部添加结点后")
link2.add(9)
link2.travel()
# 尾部增加结点
print("尾部添加结点后")
link2.append(11)
link2.travel()
# 指定位置增加结点
print("指定位置增加结点")
link2.insert(2, 0)
link2.travel()
# 删除结点
print("删除结点")
link2.remove(9)
link2.travel()
# 查找结点是否存在
print("查找结点是否存在")
print(link2.search(11))
print(link2.search(12))
运行结果：
运行结果.png
