Python单向链表实现详解：从基础概念到核心方法
本文详细解析Python中单向链表的实现原理与核心方法。内容涵盖链表与数组的区别、节点定义，并逐步演示初始化、长度获取、追加、获取、设置、插入、删除及反转链表的具体代码逻辑，帮助开发者深入理解动态数据结构的运作机制。
本文主要探讨在Python环境下如何实现单向链表，具体细节如下所述。
什么是链表
正如名称所示，链表的核心特征在于“链”式连接。
链表属于一种动态数据结构，其特点在于使用一组任意的存储单元来存放数据元素。链表中的每个元素被称为“结点”，每个结点由数据域和指针域两部分组成。与数组不同，链表无需预先定义大小，且在硬件支持的情况下，理论上可以无限扩展。
链表与数组的不同点：
数组在创建时需要预先定义大小，难以适应数据的动态增减：若数据量小于预定义长度，会造成内存浪费；若超过预定义长度，则无法直接插入。而链表支持动态增删数据，可以灵活地增加节点。
数组适用于通过索引直接获取元素的操作（直接get索引即可），而链表获取元素较为繁琐，需要从头节点开始逐个查找。不过，链表在增删操作上更具优势，只需修改节点的指向即可；相比之下，数组的增删较为麻烦，例如在列表［1，2，3，4］的下标为1的位置插入-2，需要将后续元素［2，3，4］整体后移，并赋值ls[1]=-2。
数组空间通常从栈中分配，对程序员而言方便且快速，但自由度较小。链表空间则从堆中分配，虽然自由度大，但申请和管理过程相对复杂。
链表基本方法实现（Python）
1. 初始化链表
"""节点类"""
class Node(object):
def __init__(self, data):
self.data = data
self.nex = None
def __init__(self):
"""初始化链表"""
self.head = None
2. 获取链表长度
def __len__(self):
pre = self.head
length = 0
while pre:
length += 1
pre = pre.nex
return length
3. 追加节点
追加节点的操作相对简单：如果head节点不存在，则将当前节点设为head节点；否则，找到尾节点，将尾节点的next指向当前节点（若添加head和tail两个辅助节点，则无需递归寻找尾节点）。
"""追加节点"""
def append(self, data):
"""
1.head 为none :head-->node
2.tail.nex-->node
:param data:
:return:
"""
node = Node(data)
if self.head is None:
self.head = node
else:
pre = self.head
while pre.nex:
pre = pre.nex
pre.nex = node
4. 获取节点
获取节点的操作也较为容易，主要在于判断index值的正负。
def get(self, index):
"""
:param index:
:return:
"""
index = index if index >= 0 else len(self) + index
if len(self) < index or index < 0:
return None
pre = self.head
while index:
pre = pre.nex
index -= 1
return pre
5. 设置节点
只需找到当前节点并赋值即可。
"""设置节点"""
def set(self, index, data):
node = self.get(index)
if node:
node.data = data
return node
6. 插入节点
插入节点时，需要找到插入位置的前一个节点pre_node（索引index的正负会影响前一节点的确定，需进行判断），然后将pre_node.nex指向当前节点，同时将当前节点的nex指向pre_node.nex.nex。
"""插入节点"""
def insert(self, index, data):
"""
1.index 插入节点位置包括正负数
2.找到index-1-->pre_node的节点
3.pre_node.next-->node
node.next-->pre_node.next.next
4.head
:param index:
:param data:
:return:
"""
node = Node(data)
if abs(index + 1) > len(self):
return False
index = index if index >= 0 else len(self) + index + 1
if index == 0:
node.nex = self.head
self.head = node
else:
pre = self.get(index - 1)
if pre:
nex = pre.nex
pre.nex = node
node.nex = nex
else:
return False
return node
7. 删除节点
删除节点同样需要区分索引的正负。找到当前节点的前一个节点pre_node和后一个节点next_node，将pre_node.nex指向next_node即可。
"""删除某个元素"""
def delete(self, index):
f = index if index > 0 else abs(index + 1)
if len(self) <= f:
return False
pre = self.head
index = index if index >= 0 else len(self) + index
prep = None
while index:
prep = pre
pre = pre.nex
index -= 1
if not prep:
self.head = pre.nex
else:
prep.nex = pre.nex
return pre.data
8. 反转链表
反转链表的实现方式有多种，较为简单的方法是生成一个新的链表——可以使用数组存储所有节点，然后倒序生成新链表。在此采用另一种方式生成：反转链表即将node.nex指向pre_node，通过递归实现，最后将tail赋值为head。
"""反转链表"""
def __reversed__(self):
"""
1.pre-->next 转变为 next-->pre
2.pre 若是head 则把 pre.nex --> None
3.tail-->self.head
:return:
"""
def reverse(pre_node, node):
if pre_node is self.head:
pre_node.nex = None
if node:
next_node = node.nex
node.nex = pre_node
return reverse(node, next_node)
else:
self.head = pre_node
return reverse(self.head, self.head.nex)
9. 清空链表
只需将头节点赋为空即可。
"""清空链表""" def clear(self): self.head = None
总结
以上就是本文关于Python实现单向链表的详细内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
