链表分为单链表、双链表、循环单链表和循环双链表。
本文以单链表为例，用python创建一个单链表数据结构，同时定义链表节点的增加、删除、查询和打印操作。
一、创建节点类
创建一个名为Node的节点类，节点类里面包含2个属性和1个方法。
节点类的属性
分别为data数据域属性和next指针域属性。
节点类的方法
has_value()方法，判断节点的值是否等于某个值。
# 创建节点类class Node: def __init__(self, data): self.data = data self.next = None return def has_value(self, value): if self.data == value: return True else: return False二、创建单链表类
创建一个名为singlelink的单链表类，其中包含3个属性和7个方法。
单链表类的属性
头结点head、尾节点tail和链表长度length。
单链表类的方法
（1）__init__()：初始化方法。
（2）isempty()：判断链表是否为空。
（3）add_node()：在链表尾部添加一个节点。
（4）insert_node()：在链表中的某个位置（从1开始）插入一个节点。
（5）delete_node_byid()：通过位置（从1开始），在链表中删除对应的节点。
（6）find_node()：查找某个值在链表中所在的位置（从1开始）。
（7）print_link()：按顺序打印链表的值。
注意：insert_node()、delete_node_byid()和find_node()方法中的位置指从1开始计数，并非按python中列表索引值从0开始。
（一）__init__()
# 创建一个单链表类class singlelink: # 初始化方法 def __init__(self): self.head = None self.tail = None self.length = 0 return（二）isempty()
# 判断链表是否为空 def isempty(self): if self.length == 0: return True else: return False（三）add_node()
# 向链表尾部添加一个节点 def add_node(self, item): if not isinstance(item, Node): # 判断item是否是Node类型 item = Node(item) # 创建新节点 if self.head is None: self.head = item self.tail = item else: self.tail.next = item self.tail = item self.length += 1 return（四）insert_node()
# 在链表中插入一个结点 def insert_node(self, index, data): if self.isempty(): print('this link is empty') return if index < 1 or index > self.length + 1: # 插入序号不能大于长度或小于0 print('error: out of index') return item = Node(data) if index == 1: item.next = self.head self.head = item self.length += 1 return j = 1 node = self.head prev = self.head while node.next and j < index: prev = node node = node.next j += 1 if j == index: # 在链表中间添加元素 item.next = node prev.next = item self.length += 1 return if node.next is None: # 在链表尾部添加元素 self.add_node(item)（五）delete_node_byid()
# 通过索引，在链表中删除节点 def delete_node_byid(self, item_id): if self.isempty(): print('this link is empty, Unable to delete') return if item_id < 1 or item_id > self.length: print('error：out of index，Unable to delete') id = 1 current_node = self.head previous_node = None while current_node is not None: if id == item_id: if previous_node is not None: previous_node.next = current_node.next return else: self.head = current_node.next # 删除头结点的情况 return previous_node = current_node current_node = current_node.next id += 1 self.length -= 1 return（六）find_node()
# 通过数值，在链表中找到节点(返回该节点的所有位置) def find_node(self, value): current_node = self.head node_id = 1 result = [] while current_node is not None: if current_node.has_value(value): result.append(node_id) current_node = current_node.next node_id += 1 return result（七）print_link()
def print_link(self): currrent_node = self.head while currrent_node is not None: print(currrent_node.data) currrent_node = currrent_node.next return创建单链表，并进行增加、删除、查询等操作
# 创建三个节点Node1 = Node('a')Node2 = Node('b')Node3 = Node('c')# 定义一个空链表link = singlelink()# 判断是否是空链表print(link.isempty())# 尾部添加结点for node in [Node1, Node2, Node3]: link.add_node(node)# 在链表中插入位置link.insert_node(2, 'e')link.insert_node(4, 'f')link.insert_node(4, 'f')link.insert_node(8, 'h') # 无法插入# 打印链表link.print_link()print('*****************')# 删除元素link.delete_node_byid(2)link.print_link()print('*****************')# 查找元素node_ids = link.find_node('f') # 查询元素5的位置if len(node_ids) == 0: print('链表中无此元素')else: print(node_ids)来源地址：https://blog.csdn.net/2301_76884567/article/details/129573988
