Single_linked_list.py

# 先实现定义自己的一个一个的节点
class Node(object):
 def __init__(self, data) -> None:
 # 一个节点的数据域
 self.data = data
 # 一个节点的指针域,其存储的是下一个节点的内存地址
 self.next = None


class SingleLinkedList:
 # 在进行实例化的时候我们该有一个初始节点的，通过这个初始节点来实现寻找我们的链表，这个就是头节点了
 def __init__(self) -> None:
 self.__head = None


 # 获取链表长度
 def __get_length_link(self) -> int:
 """
 获取链表长度
 :return:
 """
 p = self.__head
 count = 1
 while p.next is not None:
 p = p.next # 更新指向
 count += 1
 return count


 # 实现一个函数来保存数据
 def __save_data_in_list(self) -> list:
 """
 将链表元素组成一个列表返回
 :return:
 """
 data_list = []
 current = self.__head
 while current is not None:
 data_list.append(current.data)
 current = current.next
 return data_list


 # 添加单个节点操作
 def append_one_node(self, data) -> None:
 """
 一次性添加一个元素
 :param data: append element`s value
 :return: None
 """
 # 将元素转化为节点
 node = Node(data)
 # 判断头节点是否为空
 if self.__head is None:
 self.__head = node

 # 如果不为空，那就将节点挂载在有值的节点上面
 else:
 current = self.__head
 # 如果节点为空，那就直接实现节点的偏移
 while current.next:
 current = current.next
 current.next = node


 # 添加多个节点
 def append_many_node(self, list_data: list) -> None:
 """
 一次性插入多个元素
 :param list_data:
 :return:
 """
 # 直接遍历列表，实现循环添加单个节点
 for data in list_data:
 self.append_one_node(data)


 # 通过下标添加节点
 def append_node_by_index(self, index: int, data) -> None:
 """
 通过下标插入元素
 :param index:
 :param data:
 :return:
 """
 if index < 1:
 raise IndexError("Index must be greater than 0 \n")
 if index > self.__get_length_link():
 raise IndexError("index out of range!!!\n")

 current_node = self.__head
 node = Node(data)

 if index == 1:
 node.next = self.__head
 self.__head = node
 else:
 # 中间节点的插入
 current_index = 1 # 记录节点的下标
 # 实现偏移
 while current_node and current_index < index - 1:
 current_node = current_node.next
 current_index += 1
 # 插入新节点
 node.next = current_node.next
 current_node.next = node


 # 遍历显示所有的元素
 def show_link_data(self) -> None:
 """
 显示链表啊所有的元素
 :return:
 """
 if self.__head is None:
 print("链表为空")
 else:
 # 从头结点依次遍历整个链表元素
 current = self.__head
 while current is not None:
 print(current.data, end=" ")
 current = current.next
 print("\n")


 # 通过下标实现查找元素: 这里的使用列表实现的话，时间复杂度有是常数级别的查找元素
 def show_data_by_index(self, index: int) -> None:
 """
 通过下标显示元素
 :param index:
 :return:
 """
 # 或者说和随机插入元素的思路实现一样的，但是这里的话我是前面提前将数据添加入了一个列表中的
 if index > self.__get_length_link():
 raise IndexError("index out of range!!!")
 data_link_list = self.__save_data_in_list()
 print(f"第{index}个元素为: {data_link_list[index - 1]}\n")


 # 删除整个链表
 def clear_link(self) -> None:
 """
 清空链表
 :return:
 """
 self.__head = None


 # 根据下标删除元素
 def delete_link_by_index(self, index: int) -> None:
 """
 根据下标删除元素
 :param index:
 :return:
 """
 if index < 1:
 raise IndexError("Index must be greater than 0 \n")
 if index > self.__get_length_link():
 raise IndexError("index out of range!!!\n")

 if index == 1:
 self.__head = self.__head.next
 return

 current = self.__head
 current_index = 1
 while current and current_index < index - 1:
 current = current.next
 current_index += 1
 new_current = current.next
 current.next = current.next.next
 new_current.next = None


 # 根据值来进行删除元素
 def delete_link_by_value(self, value) -> None:
 """
 根据值来删除元素
 :param value:
 :return:
 """
 # 头节点直接改变头节点指向即可
 if self.__head.data == value:
 self.__head = self.__head.next
 return

 current = self.__head
 while current.next:
 if current.next.data == value:
 current.next = current.next.next
 return
 current = current.next
 if current.next is None:
 raise ValueError("value is not find")


 # 根据下标修改元素
 def set_link_by_index(self, index: int, data) -> None:
 """
 根据下标修改元素
 :param index:
 :param data:
 :return:
 """
 if index < 1:
 raise IndexError("Index must be greater than 0 \n")
 if index > self.__get_length_link():
 raise IndexError("index out of range!!!\n")

 if index == 1:
 self.__head.data = data
 return

 current = self.__head
 current_index = 1
 # 偏移指针
 while current and current_index < index:
 current_index += 1
 current = current.next
 current.data = data


 # 根据值来进行修改链表的值
 def set_link_by_value(self, value, data) -> None:
 """
 根据值来进行修改元素
 :param value: 指定需要用来查找的指标
 :param data: 需要进行替换的元素
 :return:
 """
 current = self.__head
 if current.data == value:
 current.data = data
 return

 while current.next:
 if current.next.data == value:
 current.next.data = data
 return
 current = current.next

 if current.next is None:
 raise ValueError("value is not find!!!")