Python单链表数据结构详解与完整代码实现

单链表的核心概念

链表（Linked List）是一种线性数据结构，由一系列被称为结点（Node）的元素组成。每个结点包含两部分：数据域用于存储实际元素值，指针域用于记录下一个结点的内存地址。与数组不同，链表不需要连续的内存空间，第一个结点称为头结点，最后一个结点的指针域通常指向 None。这种结构使得动态插入和删除操作具有较低的固定成本。

Python 单链表完整实现代码

以下是基于面向对象思想的标准实现。代码已针对现代 Python 3 语法进行修正，补全了原稿中缺失的参数处理与边界检查逻辑，确保所有方法均可稳定调用。

# 定义链表中的单个节点
class Node(object):
    def __init__(self, val, next_node=None):
        self.data = val
        self.next = next_node

# 定义单链表类
class LinkList(object):
    def __init__(self):
        self.head = None

    def is_empty(self):
        """判断链表是否为空"""
        return self.head is None

    def get_length(self):
        """获取链表长度"""
        length = 0
        curr = self.head
        while curr is not None:
            length += 1
            curr = curr.next
        return length

    def init_list(self, data):
        """根据列表数据初始化链表"""
        if not data:
            return
        self.head = Node(data[0])
        p = self.head
        for item in data[1:]:
            node = Node(item)
            p.next = node
            p = p.next

    def append(self, item):
        """在链表尾部追加元素"""
        new_node = Node(item)
        if self.is_empty():
            self.head = new_node
        else:
            curr = self.head
            while curr.next is not None:
                curr = curr.next
            curr.next = new_node

    def get_item(self, index):
        """根据索引获取节点数据（支持正向索引）"""
        if self.is_empty() or index < 0 or index >= self.get_length():
            print('Index out of bounds or list is empty.')
            return None
        curr = self.head
        for i in range(index):
            curr = curr.next
        return curr.data

    def set_item(self, index, value):
        """根据索引修改节点数据"""
        if self.is_empty() or index < 0 or index >= self.get_length():
            print('Index out of bounds.')
            return
        curr = self.head
        for i in range(index):
            curr = curr.next
        curr.data = value

    def insert(self, index, item):
        """在指定位置插入新节点"""
        if index < 0 or index > self.get_length():
            print('Invalid index for insertion.')
            return
        new_node = Node(item)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            curr = self.head
            for i in range(index - 1):
                curr = curr.next
            new_node.next = curr.next
            curr.next = new_node

    def delete(self, index):
        """删除指定位置的节点"""
        if self.is_empty() or index < 0 or index >= self.get_length():
            print('Invalid index for deletion.')
            return
        if index == 0:
            self.head = self.head.next
        else:
            curr = self.head
            for i in range(index - 1):
                curr = curr.next
            curr.next = curr.next.next

    def index_of(self, value):
        """查找值首次出现的索引，未找到返回 -1"""
        curr = self.head
        index = 0
        while curr is not None:
            if curr.data == value:
                return index
            curr = curr.next
            index += 1
        return -1

    def clear(self):
        """清空链表"""
        self.head = None

# ================= 测试代码 =================
if __name__ == "__main__":
    link_list = LinkList()
    link_list.init_list([1, 2, 3, 4, 5])
    print("初始第4个元素:", link_list.get_item(4))
    link_list.append(6)
    print("追加后第5个元素:", link_list.get_item(5))

    link_list.insert(4, 40)
    print("在索引4插入40后，第3/4/5个元素:", link_list.get_item(3), link_list.get_item(4), link_list.get_item(5))
    
    link_list.delete(5)
    print("删除第5个元素后，第5个元素:", link_list.get_item(5))
    print("查找元素5的索引:", link_list.index_of(5))
    

核心功能说明

• init_list / append：负责数据的批量导入与尾部动态扩容，避免手动逐个拼接。
• get_item / set_item：通过遍历指针定位目标索引，实现只读访问与原地修改，符合常规序列操作习惯。
• insert / delete：核心难点在于维护前驱节点的 .next 引用。插入时先断链再连入，删除时直接跳过目标节点释放引用，时间复杂度均为 O(n)。
• index_of / clear：提供值匹配搜索与彻底回收内存的快速接口。

常见运行排错与注意事项

1. 语法版本兼容：原稿使用了 Python 2 的 print '...' 语句与硬编码 0 代替空指针。现代开发务必升级至 Python 3，将 print 改为函数调用，并将空指针统一规范为 None。
2. 索引越界保护：链表操作中极易触发 IndexError 或 AttributeError。实现时必须在方法入口加入 index < 0 或 index >= length 的判断，避免 curr.next 对 None 调用属性。
3. 内存泄漏防范：clear() 方法只需将头指针置为 None，Python 垃圾回收机制会自动断开后续链并释放节点内存，无需手动逐一销毁。

总结

单链表是理解复杂树形结构与图算法的基石。上述实现覆盖了工业级数据结构的常用交互模式，开发者可直接将其集成至项目模板中。以上就是Python单链表完整实现的详细内容，更多关于Python数据结构与算法的基础资料请关注本站其它相关文章！