ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > Python > python如何实现双向链表？

python如何实现双向链表？

原创 Python 作者：mingtian66 时间：2024-11-08 12:21:15 0 删除 编辑

在Python中实现一个双向链表（Doubly Linked List）需要定义一个包含前向和后向指针的节点类。以下是一个基本的实现，包括双向链表的插入和删除操作。
1. 定义节点类

节点类 Node 包含数据字段 data 和指向前一个节点 prev 以及后一个节点 next 的指针。
2. 定义双向链表类

双向链表类 DoublyLinkedList 包含对头节点的引用，可以实现插入、删除和遍历等方法。
实现代码

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None  # 指向前一个节点
        self.next = None  # 指向后一个节点

class DoublyLinkedList:
    def __init__(self):
        self.head = None  # 初始化头节点为空

    def insert_at_head(self, data):
        """在链表头部插入节点"""
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def insert_at_tail(self, data):
        """在链表尾部插入节点"""
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            temp = self.head
            while temp.next:
                temp = temp.next
            temp.next = new_node
            new_node.prev = temp

    def delete_node(self, key):
        """删除指定数据的节点"""
        temp = self.head
        while temp:
            if temp.data == key:
                if temp.prev:
                    temp.prev.next = temp.next
                if temp.next:
                    temp.next.prev = temp.prev
                if temp == self.head:
                    self.head = temp.next
                temp = None
                return
            temp = temp.next
        print("节点未找到")

    def display_forward(self):
        """正向遍历显示链表"""
        temp = self.head
        while temp:
            print(temp.data, end=" ")
            temp = temp.next
        print()

    def display_backward(self):
        """反向遍历显示链表"""
        temp = self.head
        if temp is None:
            return
        while temp.next:
            temp = temp.next
        while temp:
            print(temp.data, end=" ")
            temp = temp.prev
        print()

使用示例

dll = DoublyLinkedList()
dll.insert_at_head(1)
dll.insert_at_head(2)
dll.insert_at_tail(3)
dll.insert_at_tail(4)

print("正向遍历:")
dll.display_forward()  # 输出: 2 1 3 4

print("反向遍历:")
dll.display_backward()  # 输出: 4 3 1 2

dll.delete_node(3)
print("删除节点后正向遍历:")
dll.display_forward()  # 输出: 2 1 4

说明

    insert_at_head 在链表头部插入节点。
    insert_at_tail 在链表尾部插入节点。
    delete_node 删除包含指定数据的节点。
    display_forward 和 display_backward 分别实现链表的正向和反向遍历。

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/70040412/viewspace-3047460/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： 什么是依赖注入？如何在 Java 中实现？
下一篇： 如何用 Python 实现一个跳表？
请登录后发表评论 登录
全部评论
mingtian66

注册时间：2024-08-07

  • 博文量
    589
  • 访问量
    603030

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593