Python单向链表完整实现与基础操作解析

单向链表的节点设计与基本结构

单向链表是一种基础的线性数据结构，其核心特征是每个节点仅包含指向下一个元素的引用（指针）。在Python这类动态语言中，我们可以直接使用面向对象的思想来封装节点。每个实例通常由数据字段和指针字段两部分组成：数据字段用于承载业务信息（如本例中的姓名与分数），而指针字段默认初始化为 None，表示当前节点尚未链接至任何后继元素。链表的起点被称为头指针，它至关重要，因为一旦丢失起始位置的引用，整个链表将无法访问。

第1步：定义节点类并完成初始化

目的：建立链表的数据载体。
入口：自定义Python类。
动作：编写 __init__ 方法，声明数据属性与指向下一节点的 next 引用。
参数与状态：实例化时各属性默认为空值或 None，确保对象创建后处于游离状态，等待被串联入链表。

class Player:
    """节点类"""
    def __init__(self):
        """初始化姓名，分数，指针"""
        self.name = ''
        self.score = 0
        self.next = None

第2步：实现链表遍历与定位逻辑

目的：沿指针链条查找目标节点，支持精确获取某个位置的引用。
入口：定义遍历函数并接收头节点及目标序号。
动作：利用 while 循环移动临时指针。当循环计数匹配目标序号时停止；若中途遇到 next 为空则提前退出防止越界。
参数与状态：传入待查序号与是否打印标志。成功执行后返回目标节点的引用，该引用将作为后续插入或删除操作的锚点。

def ergodic(head, num=None, is_print=False):
    """遍历函数，num是遍历到哪一个位置序号，is_print是否触发打印方法"""
    ptr = head
    count = 0
    while True:
        if num == count:
            break
        if ptr.next:
            count += 1
            ptr = ptr.next
            if is_print:
                print('No.'+str(count), ptr.name, ptr.score, '--->', ptr.next.name if ptr.next else None)
        else:
            break
    return ptr  # 返回遍历完成后的最后一个节点

第3步：执行节点的追加与任意位置插入

目的：扩展链表容量或在序列中间填充数据。
入口：控制台交互输入或调用封装好的逻辑分支。
动作：
1. 新增追加：调用 ergodic 找到当前尾部节点，创建新实例填入数据后，将尾节点的 next 指向新对象。
2. 指定插入：计算目标位置的前置节点索引，保存前置节点的原始后继地址，将新对象的 next 指向原后继，再更新前置节点的 next 指向新对象。
参数与状态：输入正整数序号标识位置。完成后链表长度增加，指定位置可见新增的数据记录。

# 核心插入逻辑示例
ptr = ergodic(head, num-1)  # 获取需要插入位置的前一个节点
insert_data = Player()
insert_data.name = input("姓名：")
insert_data.score = input("分数：")
insert_data.next = ptr.next
ptr.next = insert_data

第4步：完成节点移除与链表顺序反转

目的：清理无效数据或重构数据存储方向。
入口：对应功能的控制指令或函数调用。
动作：
1. 删除节点：定位到待删节点的前置节点，跳过当前节点直接连接其后继（即 ptr.next = ptr.next.next），解除关联后即可释放内存。
2. 反转链表：采用迭代法逐节点翻转指针方向。保存下一节点后切断当前指向，将当前节点指向前驱。循环直至末尾，最终返回新的头节点引用并重新绑定至原头部。
参数与状态：输入合法序号触发删除；触发反转后整条链表的 next 指向完全颠倒，原首尾对调。

def invert(x):  # x是链表的第一个节点(即head的指针的指向)
    """反转链表"""
    y = x.next  # y是x原来的next
    if y is None:  # y等于None表示当前链表只有一个节点
        return x
    x.next = None  # 将第一个节点的next指向None(因为反转了)
    while True:  # 循环反转后面的所有节点
        r = y.next
        y.next = x
        if r is None:  # r是None说明y已经是原本链表的最后一个节点了
            return y  # 返回y，这个y是反转后的链表的第一个节点
        x = y
        y = r

完整交互测试与运行效果验证

为方便验证上述逻辑，可将各项操作整合为统一的命令行菜单驱动循环。需要注意的是，本例采用了“哑节点（Dummy Node）”设计，即 head 仅作为占位起点，真正的业务数据从 head.next 开始存取。这种设计能有效避免空指针异常，简化边界条件判断。

head = Player()

while True:
    select = input("(1).新增  (2).查看  (3).插入  (4).删除  (5).反转  (6).离开\n输入：")
    if select == "1":  # 新增节点
        ptr = ergodic(head)
        next_data = Player()
        next_data.name = input("姓名：")
        next_data.score = input("分数：")
        next_data.next = None
        ptr.next = next_data
    elif select == "2":  # 遍历查看
        print("所有数据显示如下：")
        ergodic(head, is_print=True)
    elif select == '3':  # 插入节点
        try:
            num = int(input("请输入需要插入的节点位置序号："))
            if num < 1:
                print("输入必须为大于0的正整数")
                continue
        except ValueError:
            print("输入有误")
            continue
        ptr = ergodic(head, num-1)
        insert_data = Player()
        insert_data.name = input("姓名：")
        insert_data.score = input("分数：")
        insert_data.next = ptr.next
        ptr.next = insert_data
    elif select == '4':  # 删除节点
        try:
            num = int(input("请输入需要删除的节点位置序号："))
            if num < 1:
                print("输入必须为大于0的正整数")
                continue
        except ValueError:
            print("输入有误")
            continue
        ptr = ergodic(head, num - 1)
        ptr.next = ptr.next.next
    elif select == '5':  # 反转链表
        new_first = invert(head.next)
        head.next = new_first
        print('成功反转')
    elif select == '6':
        print("成功离开")
        break
    else:
        print("输入错误，请重试")

以上就是Python实现单向链表的详细内容，更多关于Python数据结构与算法入门的资料请关注本站其它相关文章！