Python实现单向链表详解

共计 1430 个字符，预计需要花费 4 分钟才能阅读完成。

单向链表每个节点都是由两部分组成：数据字段和指针，指针指向下一个元素在内存中的位置。

单向链表的第一个节点节点是链表头指针，而最后一个节点的指针设为 None，不指向任何元素。（链表头指针相当重要！！！）

使用 Python 实现单向链表，我们可以使用一个节点类来封装节点，每创建一个节点就生成一个节点类的实例。

这里主要实现了单向链表节点的遍历、添加、插入、删除，反转。

代码如下：

class Player:
    """节点类"""
    def __init__(self):
        """初始化姓名，分数，指针"""
        self.name = ''
        self.score = 0
        self.next = None
  
  
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  # 返回遍历完成后的最后一个节点
  
  
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
  
  
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)  # 遍历链表，将打印参数设为 True
         
    elif select == '3':  # 向链表中任意位置插入节点，位置以序号表示，即第一个节点序号为 1，第二个节点序号为 2，以此类推
        try:
            num = int(input("请输入需要插入的节点位置序号："))  # 输入序号必须是大于 0 的正整数，如果输入大于最后一个节点的序号则插入到最后一个节点之后
            if num 
 部分运行结果：



 阿里云 2 核 2G 服务器 3M 带宽 61 元 1 年，有高配 
 腾讯云新客低至 82 元 / 年，老客户 99 元 / 年 
 代金券：在阿里云专用满减优惠券