Python实现链表详解

老师好，我是刘同学

397人浏览 · 2026-03-10 14:50:56

老师好，我是刘同学 · 2026-03-10 14:50:56 发布

链表数据结构详解及Python实现

1. 链表基础概念

1.1 什么是链表

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针链接在一起。

1.2 链表的特点

特点	说明	优势	劣势
动态内存分配	节点在需要时动态创建	内存利用率高	需要额外的指针空间
非连续存储	节点在内存中分散存储	插入删除效率高	访问效率较低
指针链接	通过指针维护节点关系	灵活性好	实现复杂度较高

2. 链表的类型对比

# 链表类型分类
class LinkedListTypes:
    """
    单向链表：每个节点只包含指向下一个节点的指针
    双向链表：每个节点包含指向前后两个节点的指针
    循环链表：尾节点指向头节点形成环状结构
    """
    pass

3. Python链表完整实现

3.1 节点类定义

class ListNode:
    """链表节点类"""
    def __init__(self, val=0, next=None):
        self.val = val    # 节点存储的数据
        self.next = next  # 指向下一个节点的指针
    
    def __str__(self):
        """重写字符串表示方法"""
        return f"ListNode({self.val})"

# 双向链表节点
class DoublyListNode:
    """双向链表节点类"""
    def __init__(self, val=0, prev=None, next=None):
        self.val = val    # 节点存储的数据
        self.prev = prev  # 指向前一个节点的指针
        self.next = next  # 指向下一个节点的指针

3.2 单向链表实现

class SinglyLinkedList:
    """单向链表实现"""
    
    def __init__(self):
        """初始化空链表"""
        self.head = None  # 头节点
        self.size = 0     # 链表长度
    
    def is_empty(self):
        """检查链表是否为空"""
        return self.head is None
    
    def get_size(self):
        """获取链表长度"""
        return self.size
    
    def add_at_head(self, val):
        """在链表头部添加节点"""
        new_node = ListNode(val)
        new_node.next = self.head  # 新节点指向原头节点
        self.head = new_node       # 更新头节点为新节点
        self.size += 1
        return True
    
    def add_at_tail(self, val):
        """在链表尾部添加节点"""
        new_node = ListNode(val)
        
        # 如果链表为空，新节点成为头节点
        if self.is_empty():
            self.head = new_node
        else:
            # 遍历找到尾节点
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node  # 原尾节点指向新节点
        
        self.size += 1
        return True
    
    def add_at_index(self, index, val):
        """在指定位置插入节点"""
        if index < 0 or index > self.size:
            return False
        
        if index == 0:
            return self.add_at_head(val)
        
        new_node = ListNode(val)
        current = self.head
        
        # 找到插入位置的前一个节点
        for _ in range(index - 1):
            current = current.next
        
        # 插入新节点
        new_node.next = current.next
        current.next = new_node
        self.size += 1
        return True
    
    def delete_at_index(self, index):
        """删除指定位置的节点"""
        if index < 0 or index >= self.size or self.is_empty():
            return False
        
        if index == 0:
            # 删除头节点
            self.head = self.head.next
        else:
            current = self.head
            # 找到要删除节点的前一个节点
            for _ in range(index - 1):
                current = current.next
            # 跳过要删除的节点
            current.next = current.next.next
        
        self.size -= 1
        return True
    
    def get(self, index):
        """获取指定位置的节点值"""
        if index < 0 or index >= self.size or self.is_empty():
            return -1
        
        current = self.head
        for _ in range(index):
            current = current.next
        return current.val
    
    def display(self):
        """显示链表所有元素"""
        elements = []
        current = self.head
        while current:
            elements.append(current.val)
            current = current.next
        print(" -> ".join(map(str, elements)))

3.3 双向链表实现

class DoublyLinkedList:
    """双向链表实现"""
    
    def __init__(self):
        """初始化双向链表"""
        self.head = None  # 头节点
        self.tail = None  # 尾节点
        self.size = 0
    
    def add_at_head(self, val):
        """在头部添加节点"""
        new_node = DoublyListNode(val)
        
        if self.head is None:
            # 空链表情况
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        
        self.size += 1
        return True
    
    def add_at_tail(self, val):
        """在尾部添加节点"""
        new_node = DoublyListNode(val)
        
        if self.tail is None:
            # 空链表情况
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        
        self.size += 1
        return True
    
    def delete_node(self, node):
        """删除指定节点"""
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        
        self.size -= 1

4. 链表操作的时间复杂度分析

操作	单向链表	双向链表	数组
访问元素	O(n)	O(n)	O(1)
头部插入	O(1)	O(1)	O(n)
尾部插入	O(n)	O(1)	O(1)
中间插入	O(n)	O(n)	O(n)
头部删除	O(1)	O(1)	O(n)
尾部删除	O(n)	O(1)	O(1)
搜索元素	O(n)	O(n)	O(n)

5. 链表的实际应用场景

5.1 实现栈和队列

class LinkedStack:
    """使用链表实现栈"""
    
    def __init__(self):
        self.linked_list = SinglyLinkedList()
    
    def push(self, val):
        """入栈操作"""
        return self.linked_list.add_at_head(val)
    
    def pop(self):
        """出栈操作"""
        if self.linked_list.is_empty():
            return None
        val = self.linked_list.get(0)
        self.linked_list.delete_at_index(0)
        return val
    
    def peek(self):
        """查看栈顶元素"""
        if self.linked_list.is_empty():
            return None
        return self.linked_list.get(0)

class LinkedQueue:
    """使用链表实现队列"""
    
    def __init__(self):
        self.linked_list = SinglyLinkedList()
    
    def enqueue(self, val):
        """入队操作"""
        return self.linked_list.add_at_tail(val)
    
    def dequeue(self):
        """出队操作"""
        if self.linked_list.is_empty():
            return None
        val = self.linked_list.get(0)
        self.linked_list.delete_at_index(0)
        return val

5.2 LRU缓存实现

class LRUCache:
    """LRU缓存实现（最近最少使用）"""
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        # 使用双向链表维护访问顺序
        self.head = DoublyListNode(0)
        self.tail = DoublyListNode(0)
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _add_node(self, node):
        """在头部添加节点"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node):
        """移除节点"""
        prev = node.prev
        next_node = node.next
        prev.next = next_node
        next_node.prev = prev
    
    def _move_to_head(self, node):
        """将节点移到头部"""
        self._remove_node(node)
        self._add_node(node)
    
    def _pop_tail(self):
        """弹出尾部节点"""
        res = self.tail.prev
        self._remove_node(res)
        return res
    
    def get(self, key: int) -> int:
        """获取缓存值"""
        node = self.cache.get(key, None)
        if not node:
            return -1
        # 移动到头部表示最近使用
        self._move_to_head(node)
        return node.val
    
    def put(self, key: int, value: int) -> None:
        """添加缓存"""
        node = self.cache.get(key)
        
        if not node:
            new_node = DoublyListNode(value)
            self.cache[key] = new_node
            self._add_node(new_node)
            
            if len(self.cache) > self.capacity:
                # 删除最久未使用的节点
                tail = self._pop_tail()
                del self.cache[tail.val]
        else:
            # 更新值并移动到头部
            node.val = value
            self._move_to_head(node)

6. 链表与数组的对比选择

6.1 适用场景分析

选择链表的场景：

需要频繁在任意位置插入和删除元素
无法预知数据量大小，需要动态扩展
内存碎片化严重，连续内存分配困难
实现栈、队列、LRU缓存等特定数据结构

选择数组的场景：

需要频繁随机访问元素
数据量相对固定或可预知
对内存访问性能要求极高
需要进行二分查找等算法

6.2 性能优化技巧

class OptimizedLinkedList(SinglyLinkedList):
    """优化版单向链表"""
    
    def __init__(self):
        super().__init__()
        self.tail = None  # 添加尾指针优化尾部操作
    
    def add_at_tail_optimized(self, val):
        """优化尾部添加操作"""
        new_node = ListNode(val)
        
        if self.is_empty():
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        
        self.size += 1
        return True
    
    def get_middle_node(self):
        """使用快慢指针找到中间节点"""
        if self.is_empty():
            return None
        
        slow = fast = self.head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        return slow

链表作为一种基础且重要的数据结构，在Python中虽然不像列表那样内置支持，但其灵活的内存管理和高效的元素操作使其在很多场景下具有不可替代的优势。通过合理的实现和优化，链表能够很好地解决特定类型的问题。