Python单链表实现

了解如何在 Python 中实现单链表。探索动态内存分配、节点操作、插入、遍历和删除。

在编辑器中尝试

概述

链表是一种线性数据结构，其中元素不存储在连续的内存位置中。相反，每个元素（称为节点）都是一个单独的对象，其中包含对序列中下一个节点的引用。

与传统数组相比，链表的主要优点是其动态调整大小以及能够在开始时以恒定的 O(1) 时间插入或删除元素。然而，通过索引访问元素需要线性遍历，这需要 O(n) 时间。

在Python中，我们通过定义一个Node类来存储数据和引用指针，以及一个LinkedList类来管理头节点、头部或尾部的插入和删除来实现链表。

代码和执行输出

Python 中的单链表实现，展示节点创建、追加和列表遍历。

linked_list.py

在编辑器中尝试

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        
    def delete(self, key):
        curr = self.head
        if curr and curr.data == key:
            self.head = curr.next
            curr = None
            return
        prev = None
        while curr and curr.data != key:
            prev = curr
            curr = curr.next
        if not curr:
            return
        prev.next = curr.next
        curr = None
        
    def display(self):
        elements = []
        curr = self.head
        while curr:
            elements.append(str(curr.data))
            curr = curr.next
        print(" -> ".join(elements) + " -> None")

# Instantiate and build the linked list
llist = LinkedList()
llist.append("Node A")
llist.append("Node B")
llist.append("Node C")
print("Initial Linked List:")
llist.display()

print("Deleting 'Node B':")
llist.delete("Node B")
llist.display()

端子输出

Initial Linked List:
Node A -> Node B -> Node C -> None
Deleting 'Node B':
Node A -> Node C -> None

逐步实施

在文本编辑器中实现撤消重做功能
构建复杂的数据结构，例如图、堆栈和队列
管理插入和删除频率超过查找操作的列表

常见问题解答

单链表和双链表有什么区别？

在单向链表中，每个节点仅指向下一个节点。在双向链表中，每个节点都包含对下一个和前一个节点的引用，允许双向遍历，但需要额外的内存。

为什么Python没有内置的LinkedList类？

Python 数组（列表）被实现为动态数组。由于 Python 的内存管理和CPython优化，标准列表对于大多数任务来说都非常快速和高效，减少了对内置链表的实际需求。