Python案例中的链表如何实现？

wen python案例 2026-06-16 115

本文目录导读：

Python案例中的链表如何实现？

单链表的实现
双链表的实现
常见链表算法示例
实际应用案例
注意事项

我来详细解释Python中链表的实现,包括单链表和双链表的基本操作。

单链表的实现

节点类定义

class ListNode:
    """链表节点类"""
    def __init__(self, val=0, next=None):
        self.val = val        # 节点值
        self.next = next      # 指向下一个节点
class LinkedList:
    """单链表类"""
    def __init__(self):
        self.head = None      # 头节点
        self.size = 0         # 链表长度

基本操作实现

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    def is_empty(self):
        """判断链表是否为空"""
        return self.head is None
    def get_length(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
    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
    def add_at_index(self, index, val):
        """在指定位置添加节点"""
        if index < 0 or index > self.size:
            return False
        if index == 0:
            self.add_at_head(val)
            return True
        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:
            return None
        current = self.head
        for _ in range(index):
            current = current.next
        return current.val
    def find(self, val):
        """查找值第一次出现的位置"""
        current = self.head
        index = 0
        while current:
            if current.val == val:
                return index
            current = current.next
            index += 1
        return -1
    def print_list(self):
        """打印链表"""
        current = self.head
        result = []
        while current:
            result.append(str(current.val))
            current = current.next
        print(" -> ".join(result))

使用示例

# 创建链表
ll = LinkedList()
# 添加元素
ll.add_at_head(1)      # 1
ll.add_at_tail(3)      # 1 -> 3
ll.add_at_index(1, 2)  # 1 -> 2 -> 3
# 打印链表
ll.print_list()  # 输出: 1 -> 2 -> 3
# 获取元素
print(ll.get(1))  # 输出: 2
# 查找元素位置
print(ll.find(3))  # 输出: 2
# 删除元素
ll.delete_at_index(1)  # 1 -> 3
ll.print_list()  # 输出: 1 -> 3

双链表的实现

class DoubleListNode:
    """双链表节点类"""
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next
class DoublyLinkedList:
    """双链表类"""
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    def add_at_head(self, val):
        """在头部添加节点"""
        new_node = DoubleListNode(val)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.size += 1
    def add_at_tail(self, val):
        """在尾部添加节点"""
        new_node = DoubleListNode(val)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
    def delete_node(self, node):
        """删除指定节点"""
        if not node:
            return
        # 处理前驱节点
        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
    def print_forward(self):
        """从前向后打印"""
        current = self.head
        result = []
        while current:
            result.append(str(current.val))
            current = current.next
        print(" -> ".join(result))
    def print_backward(self):
        """从后向前打印"""
        current = self.tail
        result = []
        while current:
            result.append(str(current.val))
            current = current.prev
        print(" <- ".join(result))
    def is_empty(self):
        return self.head is None

常见链表算法示例

反转链表

def reverse_linked_list(head: ListNode) -> ListNode:
    """反转单链表"""
    prev = None
    current = head
    while current:
        next_temp = current.next  # 保存下一个节点
        current.next = prev       # 指向前一个节点
        prev = current            # 移动prev
        current = next_temp       # 移动current
    return prev  # prev是新的头节点
# 使用示例
def test_reverse():
    ll = LinkedList()
    for i in range(1, 6):
        ll.add_at_tail(i)
    print("原链表:", end=" ")
    ll.print_list()  # 1 -> 2 -> 3 -> 4 -> 5
    # 反转链表
    ll.head = reverse_linked_list(ll.head)
    print("反转后:", end=" ")
    ll.print_list()  # 5 -> 4 -> 3 -> 2 -> 1

检测环

def has_cycle(head: ListNode) -> bool:
    """检测链表是否有环（快慢指针法）"""
    if not head or not head.next:
        return False
    slow = head
    fast = head.next
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    return True
# 创建有环链表
def create_cycle_list():
    """创建一个有环的链表 1->2->3->4->5->3"""
    head = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node5 = ListNode(5)
    head.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    node5.next = node3  # 创建环
    return head
# 测试
head = create_cycle_list()
print(has_cycle(head))  # 输出: True

合并两个有序链表

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    """合并两个有序链表"""
    dummy = ListNode(0)  # 虚拟头节点
    current = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    # 连接剩余部分
    current.next = l1 if l1 else l2
    return dummy.next
# 使用示例
def test_merge():
    # 创建有序链表1: 1->3->5
    l1 = LinkedList()
    l1.add_at_tail(1)
    l1.add_at_tail(3)
    l1.add_at_tail(5)
    # 创建有序链表2: 2->4->6
    l2 = LinkedList()
    l2.add_at_tail(2)
    l2.add_at_tail(4)
    l2.add_at_tail(6)
    # 合并
    merged_head = merge_two_lists(l1.head, l2.head)
    # 打印合并结果
    result = LinkedList()
    result.head = merged_head
    print("合并后:", end=" ")
    result.print_list()  # 1 -> 2 -> 3 -> 4 -> 5 -> 6

实际应用案例

class LRUCache:
    """LRU缓存（使用双向链表+哈希表）"""
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> node
        self.head = DoubleListNode(0, 0)  # 虚拟头节点
        self.tail = DoubleListNode(0, 0)  # 虚拟尾节点
        self.head.next = self.tail
        self.tail.prev = self.head
    def _remove_node(self, node):
        """移除节点"""
        node.prev.next = node.next
        node.next.prev = node.prev
    def _add_to_head(self, node):
        """将节点添加到头部"""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
    def get(self, key: int) -> int:
        """获取缓存值"""
        if key in self.cache:
            node = self.cache[key]
            self._remove_node(node)
            self._add_to_head(node)
            return node.val
        return -1
    def put(self, key: int, value: int) -> None:
        """放入缓存"""
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove_node(node)
            self._add_to_head(node)
        else:
            if len(self.cache) >= self.capacity:
                # 移除最久未使用的节点
                lru_node = self.tail.prev
                self._remove_node(lru_node)
                del self.cache[lru_node.key]
            new_node = DoubleListNode(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)
# 使用LRU缓存
lru = LRUCache(2)
lru.put(1, 1)  # 缓存：{1=1}
lru.put(2, 2)  # 缓存：{1=1, 2=2}
print(lru.get(1))  # 输出: 1
lru.put(3, 3)      # 移除key 2，缓存：{1=1, 3=3}
print(lru.get(2))  # 输出: -1