如何用Python实现一个链表？-Python教程-PHP中文网

如何用Python实现一个链表？

裘德小鎮的故事

发布： 2025-05-04 22:30:02

原创

523人浏览过

在python中实现单向链表需要定义node和linkedlist类。1.定义node类表示节点，包含data和next属性。2.定义linkedlist类，包含append方法在末尾添加节点，display方法展示链表。3.实现插入和删除操作，insert_at_beginning方法在头部插入，delete方法删除指定节点。4.优化性能时，可使用双向链表，增加prev指针，提高删除效率。

如何用Python实现一个链表？

在Python中实现一个链表是一项基础且有趣的任务，下面我将详细讲解如何实现一个单向链表，并分享一些我在实际项目中遇到的经验和思考。

实现一个链表的基本思路

实现一个链表，首先需要定义两个主要的类：Node和LinkedList。Node类表示链表中的每个节点，而LinkedList类则管理整个链表结构。

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
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        return ' -> '.join(elements)

登录后复制

这个实现中，我们定义了append方法来在链表末尾添加新节点，以及display方法来展示链表的内容。

立即学习“Python免费学习笔记（深入）”；

深入理解链表的操作

在实际项目中，我发现链表的插入和删除操作是非常常见的需求。让我们来看看如何实现这些操作。

class LinkedList:
    # ... (之前的代码)

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

登录后复制

插入操作可以在链表的头部进行，这通常比在尾部插入要快，因为不需要遍历整个链表。删除操作则需要遍历链表以找到要删除的节点。

bee餐饮点餐外卖小程序

bee餐饮点餐外卖小程序是针对餐饮行业推出的一套完整的餐饮解决方案，实现了用户在线点餐下单、外卖、叫号排队、支付、配送等功能，完美的使餐饮行业更高效便捷！功能演示：1、桌号管理登录后台，左侧菜单 “桌号管理”，添加并管理你的桌号信息，添加以后在列表你将可以看到 ID 和密钥，这两个数据用来生成桌子的二维码2、生成桌子二维码例如上面的ID为 308，密钥为 d3PiIY，那么现在去左侧菜单微信设置

查看详情

性能考虑和优化

链表的一个主要优势是动态大小，但它的一个缺点是随机访问的效率低下。在某些场景下，我们可能需要优化链表的性能，比如在频繁插入和删除操作中使用双向链表。

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return
        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node

    def delete(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            if self.head:
                self.head.prev = None
            else:
                self.tail = None
            return
        current = self.head
        while current:
            if current.data == data:
                if current.next:
                    current.next.prev = current.prev
                else:
                    self.tail = current.prev
                if current.prev:
                    current.prev.next = current.next
                return
            current = current.next

登录后复制

双向链表的实现增加了prev指针，使得删除操作变得更加高效，因为我们可以直接访问前一个节点。