# 定义节点类：
class Node:
# 初始化
def __init__(self, data):
self.data = data
self.next = None # 下一个节点为None
# 获取当前位置（当前指针指向）的数据
def getData(self):
return self.data
# 在当前位置（当前指针指向）写入数据
def setData(self, data):
self.data = data
# 获取下一位置（指针下一个指向）的数据
def getNext(self):
return self.next
# 在下一位置（指针下一个指向）写入数据：
def setNext(self, next_node):
self.next = next_node # next_node为下一个节点的意思
# 定义无序列表类（链表）：
class UnorderList:
# 初始化
def __init__(self):
self.head = None # 头部没有指向任何节点
# 检查链表是否为空
def isEmpty(self):
return self.head == None # 头部没有指向任何节点（即空链表）
# 往无序列表的左端添加元素
def add(self, data):
tmp = Node(data) # 创建一个名为tmp的节点
tmp.setNext(self.head) # 将tmp节点与已有的链表结构head节点链接起来（即tmp节点下一个指向为head节点，让新增元素与原链表进行拼接）
self.head = tmp # 此时新的头节点变成了（tmp节点+旧头节点）
# 查看链表的长度
def length(self):
count = 0 # 用于计算访问了多少个节点？
current = self.head # 令当前节点为头节点
# 开始访问节点，当前节点不为空时：
while current != None:
current = current.getNext() # 当前节点往后窜一位
count += 1 # 访问数+1
return count # 返回访问数
# 查找链表中的元素
def search(self, data):
beFound = False # 初始化时设定该元素还未找到
current = self.head # 令当前节点为头节点
while current != None:
currentData = current.getData() # 获取当前节点上的内容
if currentData == data: # 当前获取的内容与所要寻找的内容相同时
beFound = True # 该元素找到了
current = current.getNext() # 当前节点往后挪一位
return beFound
# 移除链表中的元素
def remove(self, data):
previous = None # 初始化前一节点为空
current = self.head # 令当前节点为头节点
beFound = False # 初始化时设定该元素还未找到
# 开始访问节点，当前节点不为空时：
while current != None:
# 如果当前节点的内容与所需移除的内容相同时：
if current.getData() == data:
beFound = True # 该元素找到了
break # 退出while循环
else:
previous = current # 令前一节点为当前节点
current = current.getNext() # 当前节点往后挪一位
# 删除最左端元素时执行下面一行代码
if previous == None:
self.head = current.getNext() # 令头节点指向当前节点的下一节点（移除后拼接）
else:
# 删除超出链表范围的元素时执行下面一行代码
if current == None:
raise Exception('ValueError: list.remove(x): x not in list')
# 删除非最左端元素时执行下面一行代码
else:
previous.setNext(current.getNext()) # 令前一节点与“当前节点的下一个指向”链接（即让目标元素脱轨，其他元素拼接）
# 清空链表
def clear(self):
self.head = None # 令头节点不指向任何节点
# 往链表右端添加元素
def append(self, data):
tmp = Node(data) # 创建一个名为tmp的节点
# 如果链表为空
if self.head == None:
self.head = tmp # 令头节点指向tmp节点
# 如果链表不为空
else:
current = self.head # 令当前节点指向头节点
# 当前节点的下一节点不为空时
while current.getNext() != None:
current = current.getNext() # 当前节点往后挪一位
# 当前节点的下一节点为空时（到达最右端）
else:
current.setNext(tmp) # 令当前节点与tmp节点链接（即当前节点下一个指向为tmp节点，让原链表与新增元素进行拼接）
# 在链表任意位置插入元素
# 当 position<0 或 position>length-1 时，分别在左右端插入元素（未实现）
def insert(self, position, data):
assert(position <= self.length()) # 当所选位置超出链表范围时报错
tmp = Node(data) # 创建一个名为tmp的节点
current_position = 0 # 当前节点的位置为0
previous = None # 令前一节点为空
current = self.head # 令当前节点为头节点
# 当前节点的位置小于目标位置时
while current_position < position:
previous = current # 令前一节点为当前节点
current = current.getNext() # 当前节点往后挪一位
current_position += 1 # 当前节点的位置+1
# 在非最左端插入元素时执行下面两行代码
if previous != None:
previous.setNext(tmp) # 令前一节点与tmp节点链接（即前一节点下一个指向为tmp节点，让前一节点与tmp节点拼接）
tmp.setNext(current) # 令tmp节点与当前节点链接（即tmp节点下一个指向为当前节点，让tmp节点与当前节点拼接）
# 在最左端插入元素时执行下面两行代码
else:
tmp.setNext(current) # 令tmp节点与当前节点链接（即tmp节点下一个指向为当前节点，让tmp节点与当前节点拼接）
self.head = tmp # 此时新的头节点变成了（tmp节点+旧头节点）
# 在链表中寻找下标
def index(self, data):
assert(self.isEmpty() == False) # 当链表为空时报错
current_position = 0 # 当前节点的位置为0
current = self.head # 令当前节点为头节点
# 当前节点不为空时：
while current != None:
# 如果当前数据与目标数据相等
if current.getData() == data:
break # 退出while循环
current = current.getNext() # 当前节点往后挪一位
current_position += 1 # 当前节点的位置+1
# 如果当前节点为空时（达到最右端）：
if current == None:
raise Exception('ValueError: list.remove(x): x not in list')
return current_position # 返回当前节点位置
# 不传入参数时，默认删除链表中最右端元素
# 传入参数时，删除链表中对应位置上的元素
def pop(self, position=None):
# 情况一：如果不传入参数
if position == None:
assert (self.isEmpty() == False) # 当链表为空时报错
previous = None # 令前一节点为空
current = self.head # 令当前节点为头节点
# 当下一节点不为空时：
while current.getNext() != None:
previous = current # 令前一节点等于当前节点
current = current.getNext() # 当前节点往后挪一位
# 如果链表中只有一个元素
if previous == None:
self.head = None # 链表不指向任何元素（链表变空）
# 如果链表中元素不止一个
else:
previous.setNext(None) # 令前一节点与None链接（即前一节点下一个指向为None，让前一节点与None拼接）
# 情况二：如果传入参数
elif position != None:
assert (self.isEmpty() == False and 0 <= position < self.length()) # 当链表为空和所选位置超出链表范围时报错
current_position = 0 # 当前节点的位置为0
previous = None # 初始化前一节点为空
current = self.head # 令当前节点为头节点
# 当前节点的位置小于等于目标位置时：
while current_position <= position:
current_data = current.getData() # 获取当前节点数据
previous = current # 令前一节点为当前节点
# 如果当前位置与目标位置相同时
if current_position == position:
break # 退出while循环
# 如果当前位置与目标位置不相同时
else:
current = current.getNext() # 当前节点往后挪一位
current_position += 1 # 当前节点的位置+1
# 当链表中元素不止一个时执行下面一行代码
if previous != None:
previous.setNext(current.getNext()) # 令前一节点与当前节点的下一指向链接（即前一节点下一个指向为“当前节点的下一指向”，让前一节点与“当前节点的下一指向”拼接）
# 当链表中只有一个元素时执行下面一行代码
else:
self.head = None # 令头节点不指向任何元素
return current_data # 当传入参数时才有返回值
# 打印链表中的内容
def __repr__(self):
start = '[' # 设置链表的固定开头
end = ']' # 设置链表的固定结尾
current = self.head # 令当前节点为头节点
# 当前节点不为空时：
while current != None:
start += str(current.getData()) + ', ' # 往start中加入“当前节点数据和‘, ’”
current = current.getNext() # 当前节点往后挪一位
# 如果start的长度大于1
if len(start) > 1:
start = start[:-2] + end # 字符串拼接
# 如果start的长度小于等于1
else:
start = start + end # 字符串拼接
return start # 返回start（列表的样子）
# 返回下标对应的值
def __getitem__(self, index):
assert(index >= 0 and index < self.length()) # 当index超出链表范围时报错
current = self.head # 令当前节点为头节点
# 当下标不为0时：
while index != 0:
current = current.getNext() # 当前节点往后挪一位
index -= 1 # 下标-1
return current.getData() # 返回当前节点的数据
# 设置给定下标的值
def __setitem__(self, index, value):
assert(index >= 0 and index < self.length()) # 当index超出链表范围时报错
current = self.head # 令当前节点为头节点
# 当下标不为0时：
while index != 0:
current = current.getNext() # 当前节点往后挪一位
index -= 1 # 下标-1
current.setData(value) # 令当前节点与value链接（即当前节点下一个指向为value，让当前节点与value拼接）
# 定义有序列表类：
class OrderList(UnorderList):
# 初始化
def __init__(self):
super().__init__() # 继承无序列表
# isEmpty()、length()、remove()等的实现和父类（UnorderList类）一样
# 查找元素
def search(self, data):
beFound = False # 还未找到
current = self.head # 令当前节点为头节点
while current != None:
currentData = current.getData() # 获取节点上的内容
if currentData == data: # 当前获取的内容与所要寻找的内容相同时
beFound = True
break
elif currentData > data: # 遇到其值大于目标元素的节点时
beFound = False
break
current = current.getNext() # 当前节点往后窜一位
return beFound
# 在左边添加元素
def add(self, data):
current = self.head # 令当前节点为头节点
previous = None
stop = False
# 当前节点不为空且？
while current != None and not stop:
if current.getData() > data:
stop = True
else:
previous =current
current = current.getNext()
tmp = Node(data) # 创建一个名为tmp的节点
if previous != None:
tmp.setNext(current)
previous.setNext(tmp)
else:
tmp.setNext(self.head)
self.head = tmp
