309 链表的实现2 #
- 链表删除任意结点
- 链表的实现
链表删除任意结点 #
删除结点时先根据给出的位置序号进行循环，直到到达指定结点，再删除对应结点
def removce_node_index(self, index):
current = self.header
count = 0
while current is not None:
if index == count:
print("找到指定结点!")
if index == 0:
self.header = current.next
else:
last.next = current.next
self.length -= 1
return self
count += 1
last = current
current = current.next
return self
def removce_node_index(self, index):
current = self.header
count = 0
while current is not None:
if index == count:
print("找到指定结点!")
if index == 0:
self.header = current.next
else:
last.next = current.next
self.length -= 1
return self
count += 1
last = current
current = current.next
return self
def removce_node_index(self, index):
current = self.header
count = 0
while current is not None:
if index == count:
print("找到指定结点!")
if index == 0:
self.header = current.next
else:
last.next = current.next
self.length -= 1
return self
count += 1
last = current
current = current.next
return self
链表的实现 #
链表实现了在任意位置增删结点的功能，并具有判空功能
掌握链表删除结点的方法
掌握链表类的写法
# 初始化一个节点
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.header = None
self.length = 0
# 判断链表是否为空,数值使用==比较，对象使用is来判断是否为None即可。
def is_empty(self):
if self.header is None:
return True
else:
return False
# 在链表头部添加结点
def add_node_from_head(self, node):
if self.header is None:
self.header = node
else:
node.next = self.header
self.header = node
self.length += 1
return self
# 在链表尾部添加结点
def add_node_from_behind(self, node):
current_node = self.header
if self.is_empty():
self.add_node_from_head(node)
else:
# 一直遍历到尾部结点
while current_node.next is not None:
current_node = current_node.next
current_node.next = node
self.length += 1
return self
def add_node_index(self, node, index):
if self.is_empty():
self.header = node
self.length = 1
return self
if index > self.length - 1 or index < 0:
print("超出范围,插入失败!")
return self
else:
current_node = self.header
count = 0
while True:
if current_node is not None:
# 最少有2个结点
if count == index:
print("...找到位置....")
if count == 0:
# 插入到头结点之前
node.next = current_node
self.header = node
else:
# 1. 新节点的next指向当前结点
# 2. 上一个节点的next指向新结点
node.next = current_node
last_node.next = node
self.length += 1
return self
else:
count += 1
last_node = current_node
current_node = current_node.next
else:
# 只有一个头结点
node.next = current_node
self.header = node
self.length += 1
return self
# 删除指定结点
def removce_node_index(self, index):
current = self.header
count = 0
while current is not None:
if index == count:
print("找到指定结点!")
if index == 0:
self.header = current.next
else:
last.next = current.next
self.length -= 1
return self
count += 1
last = current
current = current.next
return self
# 遍历链表
def traversing_list(self):
header_node = self.header
result = ",data:" + str(header_node.data)
while header_node.next is not None:
result = result + "-->" + "data:" + str(header_node.next.data)
temp = header_node
header_node = header_node.next
if temp == header_node:
return
print("链表为:", result, ",长度为:" + str(self.length))
if __name__ == '__main__':
print("初始化一个链表!")
header = Node(0)
linked_list = LinkedList()
linked_list.add_node_index(header, 0)
linked_list.traversing_list()
print("在头部添加结点!")
node0 = Node(1)
linked_list.add_node_from_head(node0)
linked_list.traversing_list()
print("在尾部添加结点!")
node1 = Node(2)
linked_list.add_node_from_behind(node1)
linked_list.traversing_list()
print("在index=1处添加结点!")
node2 = Node(3)
linked_list.add_node_index(node2, 1)
linked_list.traversing_list()
print("删除index=1的结点!")
linked_list.removce_node_index(1)
linked_list.traversing_list()
# 初始化一个节点
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.header = None
self.length = 0
# 判断链表是否为空,数值使用==比较，对象使用is来判断是否为None即可。
def is_empty(self):
if self.header is None:
return True
else:
return False
# 在链表头部添加结点
def add_node_from_head(self, node):
if self.header is None:
self.header = node
else:
node.next = self.header
self.header = node
self.length += 1
return self
# 在链表尾部添加结点
def add_node_from_behind(self, node):
current_node = self.header
if self.is_empty():
self.add_node_from_head(node)
else:
# 一直遍历到尾部结点
while current_node.next is not None:
current_node = current_node.next
current_node.next = node
self.length += 1
return self
def add_node_index(self, node, index):
if self.is_empty():
self.header = node
self.length = 1
return self
if index > self.length - 1 or index < 0:
print("超出范围,插入失败!")
return self
else:
current_node = self.header
count = 0
while True:
if current_node is not None:
# 最少有2个结点
if count == index:
print("...找到位置....")
if count == 0:
# 插入到头结点之前
node.next = current_node
self.header = node
else:
# 1. 新节点的next指向当前结点
# 2. 上一个节点的next指向新结点
node.next = current_node
last_node.next = node
self.length += 1
return self
else:
count += 1
last_node = current_node
current_node = current_node.next
else:
# 只有一个头结点
node.next = current_node
self.header = node
self.length += 1
return self
# 删除指定结点
def removce_node_index(self, index):
current = self.header
count = 0
while current is not None:
if index == count:
print("找到指定结点!")
if index == 0:
self.header = current.next
else:
last.next = current.next
self.length -= 1
return self
count += 1
last = current
current = current.next
return self
# 遍历链表
def traversing_list(self):
header_node = self.header
result = ",data:" + str(header_node.data)
while header_node.next is not None:
result = result + "-->" + "data:" + str(header_node.next.data)
temp = header_node
header_node = header_node.next
if temp == header_node:
return
print("链表为:", result, ",长度为:" + str(self.length))
if __name__ == '__main__':
print("初始化一个链表!")
header = Node(0)
linked_list = LinkedList()
linked_list.add_node_index(header, 0)
linked_list.traversing_list()
print("在头部添加结点!")
node0 = Node(1)
linked_list.add_node_from_head(node0)
linked_list.traversing_list()
print("在尾部添加结点!")
node1 = Node(2)
linked_list.add_node_from_behind(node1)
linked_list.traversing_list()
print("在index=1处添加结点!")
node2 = Node(3)
linked_list.add_node_index(node2, 1)
linked_list.traversing_list()
print("删除index=1的结点!")
linked_list.removce_node_index(1)
linked_list.traversing_list()
# 初始化一个节点
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.header = None
self.length = 0
# 判断链表是否为空,数值使用==比较，对象使用is来判断是否为None即可。
def is_empty(self):
if self.header is None:
return True
else:
return False
# 在链表头部添加结点
def add_node_from_head(self, node):
if self.header is None:
self.header = node
else:
node.next = self.header
self.header = node
self.length += 1
return self
# 在链表尾部添加结点
def add_node_from_behind(self, node):
current_node = self.header
if self.is_empty():
self.add_node_from_head(node)
else:
# 一直遍历到尾部结点
while current_node.next is not None:
current_node = current_node.next
current_node.next = node
self.length += 1
return self
def add_node_index(self, node, index):
if self.is_empty():
self.header = node
self.length = 1
return self
if index > self.length - 1 or index < 0:
print("超出范围,插入失败!")
return self
else:
current_node = self.header
count = 0
while True:
if current_node is not None:
# 最少有2个结点
if count == index:
print("...找到位置....")
if count == 0:
# 插入到头结点之前
node.next = current_node
self.header = node
else:
# 1. 新节点的next指向当前结点
# 2. 上一个节点的next指向新结点
node.next = current_node
last_node.next = node
self.length += 1
return self
else:
count += 1
last_node = current_node
current_node = current_node.next
else:
# 只有一个头结点
node.next = current_node
self.header = node
self.length += 1
return self
# 删除指定结点
def removce_node_index(self, index):
current = self.header
count = 0
while current is not None:
if index == count:
print("找到指定结点!")
if index == 0:
self.header = current.next
else:
last.next = current.next
self.length -= 1
return self
count += 1
last = current
current = current.next
return self
# 遍历链表
def traversing_list(self):
header_node = self.header
result = ",data:" + str(header_node.data)
while header_node.next is not None:
result = result + "-->" + "data:" + str(header_node.next.data)
temp = header_node
header_node = header_node.next
if temp == header_node:
return
print("链表为:", result, ",长度为:" + str(self.length))
if __name__ == '__main__':
print("初始化一个链表!")
header = Node(0)
linked_list = LinkedList()
linked_list.add_node_index(header, 0)
linked_list.traversing_list()
print("在头部添加结点!")
node0 = Node(1)
linked_list.add_node_from_head(node0)
linked_list.traversing_list()
print("在尾部添加结点!")
node1 = Node(2)
linked_list.add_node_from_behind(node1)
linked_list.traversing_list()
print("在index=1处添加结点!")
node2 = Node(3)
linked_list.add_node_index(node2, 1)
linked_list.traversing_list()
print("删除index=1的结点!")
linked_list.removce_node_index(1)
linked_list.traversing_list()
小结 #
习题 #
- 思考一下链表的缺点
- 详细描述一下链表添加结点和删除结点的细节，并绘制其过程
