Python单链表基础实现与核心操作

Python 单链表基础实现与核心操作

第1步：定义节点结构

单链表的基础是节点类，用于存储实际数据以及指向后继节点的指针。在 Python 中通过自定义类来实现：

class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None

第2步：构建链表管理类与方法封装

链表管理类负责维护整体结构状态，默认持有头节点 `head` 与尾节点引用 `end`，便于高效执行尾部插入。核心方法按功能划分如下：

• 添加节点：通过更新当前尾节点的 `next` 指针并刷新尾引用完成追加。
• 查询长度：从头节点开始遍历计数，直到 `next` 为 `None` 为止。
• 查找与修改：根据目标索引定位节点，支持读取或替换数据域，返回旧值便于回滚操作。
• 安全删除：跳过指定索引的前驱节点指针指向其后继节点，直接断开被删节点的引用链。
• 整表打印：逐节点拼接字符串并按顺序输出，直观展示链路状态。

class NodeList(object):
    def __init__(self, node):
        self.head = node
        self.end = self.head

    def add_node(self, node):
        self.end.next = node
        self.end = self.end.next

    def length(self):
        count = 1
        node = self.head
        while node.next is not None:
            count += 1
            node = node.next
        return count

    def delete_node(self, index):
        if index < 0 or index >= self.length():
            raise IndexError('index out of bounds')
        i = 0
        node = self.head
        while i < index - 1:
            node = node.next
            i += 1
        tmp_node = node.next
        node.next = tmp_node.next
        return tmp_node.data

    def show(self):
        node = self.head
        parts = []
        while node is not None:
            parts.append(str(node.data))
            node = node.next
        print('->'.join(parts))

    def change(self, index, data):
        if index < 0 or index >= self.length():
            raise IndexError('index out of bounds')
        i = 0
        node = self.head
        while i != index:
            node = node.next
            i += 1
        old_data = node.data
        node.data = data
        return old_data

    def find(self, index):
        if index < 0 or index >= self.length():
            raise IndexError('index out of bounds')
        i = 0
        node = self.head
        while i != index:
            node = node.next
            i += 1
        return node.data

第3步：编写测试用例并执行验证

创建多个节点实例后，初始化链表并依次执行插入操作。随后调用长度统计、索引查找、数值替换及格式化打印方法，验证各项逻辑是否正确衔接：

# 实例化节点
n1 = Node(0)
n2 = Node(1)
n3 = Node(2)
n4 = Node(3)
n5 = Node(4)

# 构建链表
node_list = NodeList(n1)
node_list.add_node(n2)
node_list.add_node(n3)
node_list.add_node(n4)
node_list.add_node(n5)

# 功能验证
print('链表总长度:', node_list.length())
print('查找索引 3 的值:', node_list.find(3))
print('修改索引 0 为 88，原值:', node_list.change(0, 88))
node_list.show()

以上就是 Python 单链表基础实现与核心操作的详细内容，更多关于 Python 数据结构与算法的项目实战资料请关注本站其它相关文章！