python单向链表实例详解

下面是关于“Python单向链表实例详解”的完整攻略:

什么是单向链表?

单向链表(Singly Linked List)是一种常见的数据结构,它由多个节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。相比于数组,单向链表具有动态操作、空间灵活等优势,在实际应用中也很常见。

如何实现单向链表?

在 Python 中,我们可以用类来定义一个单向链表,每个节点用一个类实例来表示。以下是一个最简单的示例:

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

class LinkedList:
    def __init__(self):
        self.head = None

在这里,我们定义了一个 Node 类,包含数据域 data 和指针域 next;同时,我们定义了一个 LinkedList 类,初始时链表为空,头结点指针为空。

单向链表的基本操作

1. 添加元素

向链表中添加元素时,我们需要创建一个新的节点,然后将它插入到链表的末尾。以下是一个示例:

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

在这里,我们定义了一个 append 方法,用于将新元素添加到链表末尾。首先,我们创建一个新的节点 new_node,其数据域为 data;然后,我们检查链表是否为空,如果是,则将 new_node 设置为头结点;否则,用 last_node 变量指向链表的最后一个节点,然后将 new_node 插入到链表的末尾。

2. 遍历链表

遍历链表时,我们只需要从头节点开始依次访问每个节点即可。以下是一个示例:

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def traverse(self):
        if self.head is None:
            print("List is empty")
            return
        current_node = self.head
        while current_node:
            print(current_node.data, end=" ")
            current_node = current_node.next

在这里,我们定义了一个 traverse 方法,用于遍历链表并输出每个节点的数据域。首先,我们检查链表是否为空,如果是,则输出 “List is empty” ;否则,我们用 current_node 变量指向链表的头结点,然后依次访问每个节点并输出其数据域。

以下是一个示例输出:

linked_list = LinkedList()
linked_list.append("A")
linked_list.append("B")
linked_list.append("C")

linked_list.traverse()
# Output: A B C

可以看到,我们成功地创建并遍历了一个包含 3 个元素的链表。

示例应用

1. 单向链表中的常见问题:查找中间节点

对于链表中除了头尾节点以外的其他节点,我们可以用以下方法来查找其中间节点:

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def find_middle_node(self):
        if self.head is None:
            return None
        slow_pointer = self.head
        fast_pointer = self.head
        while fast_pointer and fast_pointer.next:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next
        return slow_pointer

在这里,我们定义了一个 find_middle_node 方法,用于查找链表的中间节点。首先,我们检查链表是否为空,如果是,则返回 None;否则,我们用 slow_pointer 和 fast_pointer 两个指针分别指向头结点,并进行以下操作:

  • 正常情况下,fast_pointer 走两步,slow_pointer 走一步,直到 fast_pointer 无法再走两步为止;
  • 最后,slow_pointer 指向的节点即为中间节点。

以下是一个示例输出:

linked_list = LinkedList()
linked_list.append("A")
linked_list.append("B")
linked_list.append("C")
linked_list.append("D")
linked_list.append("E")
linked_list.append("F")

middle_node = linked_list.find_middle_node()
print(middle_node.data)
# Output: D

2. 单向链表的反转

对于一个链表,我们可以用以下方法来反转它:

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def reverse(self):
        previous_node = None
        current_node = self.head
        while current_node:
            next_node = current_node.next
            current_node.next = previous_node
            previous_node = current_node
            current_node = next_node
        self.head = previous_node

在这里,我们定义了一个 reverse 方法,用于反转链表。首先,我们用 previous_node 变量指向 None,用 current_node 变量指向链表的头结点;然后,依次处理每个节点:

  • 将 current_node 的 next 指针指向 previous_node;
  • 将 previous_node 指向 current_node;
  • 将 current_node 指向 next_node。

最后,将 self.head 指向反转后的链表的第一个节点。

以下是一个示例输出:

linked_list = LinkedList()
linked_list.append("A")
linked_list.append("B")
linked_list.append("C")
linked_list.append("D")
linked_list.append("E")
linked_list.append("F")

print("Original list:")
linked_list.traverse()
# Output: A B C D E F

linked_list.reverse()

print("Reversed list:")
linked_list.traverse()
# Output: F E D C B A

可以看到,我们成功地反转了一个链表。

阅读剩余 77%

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:python单向链表实例详解 - Python技术站

(0)
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • React Server Component混合式渲染问题详解

    针对“React Server Component混合式渲染问题详解”的完整攻略,我将按照以下几个方面进行详细讲解: React Server Component(RSC)是什么? RSC背景和优势 RSC的混合式渲染 两个示例说明 结论和总结 1. React Server Component(RSC)是什么? React Server Component…

    other 2023年6月26日
    00
  • RxJava取消订阅的各种方式的实现

    RxJava提供了多种方式取消订阅,本文将结合代码示例详细讲解以下几种方式的实现: 使用Disposable.dispose()取消订阅 在RxJava中,多数操作符的subscribe()方法会返回一个“Disposable”对象,这个对象代表了Observable和Observer之间的订阅关系。借助Disposable.dispose()方法,可以取消…

    other 2023年6月27日
    00
  • js中生成map对象的方法

    以下是使用标准的Markdown格式文本,详细讲解在JavaScript中生成Map对象的方法的完整攻略: JavaScript中生成Map对象的方法 方法一:使用Map构造函数和数组 // 创建一个空的Map对象 let map = new Map(); // 添加键值对到Map对象 map.set(‘key1’, ‘value1’); map.set(‘…

    other 2023年10月15日
    00
  • linux轻量级 Web 服务器第1/2页

    Linux轻量级Web服务器攻略 本攻略旨在为初学者提供Linux轻量级Web服务器的基本操作和安装方法。在本攻略中,我们将会涉及以下主题: 轻量级Web服务器的定义和作用 安装和配置Apache 理解Apache的常见配置文件 使用Apache来部署简单的网站 检测Apache的服务状态和日志 1. 轻量级Web服务器的定义和作用 什么是轻量级Web服务器…

    other 2023年6月27日
    00
  • django 模型中的计算字段实例

    下面我给您详细讲解“Django 模型中的计算字段实例”的完整攻略。 什么是计算字段 计算字段在 Django 中称为【属性】属性。它是通过模型中定义的方法来计算的,而不是从数据库中检索。此外,在当您需要计算某个表的特定字段时,可以使用计算字段来完成。 假设我们有一个名为 Book 的模型,该模型具有标题、作者、出版社和价格等属性。 然后,我们还需要计算折扣…

    other 2023年6月26日
    00
  • linux如何部署nginx

    Linux如何部署nginx 在Linux服务器上部署nginx可以快速搭建一个高性能的web服务器,本文将介绍如何在Linux上安装和配置nginx。 步骤一:安装nginx 使用命令行工具登录到Linux服务器; 安装nginx,命令如下: sudo apt update sudo apt install nginx 等待安装完成,安装成功后启动ngin…

    其他 2023年3月28日
    00
  • signalR制作微信墙 开源

    signalR制作微信墙 开源的完整攻略 本文将为您提供signalR制作微信墙开源的完整攻略,包括介绍、方法和两个示例说明。 介绍 SignalR是一个开源的实时Web应用程序框架,可以使用C#或JavaScript编写。微信墙是一种互动性强的活动形式,可以通过SignalR实现实时展示微信消息。 方法 signalR制作微信墙的方法如下: 创建Signa…

    other 2023年5月6日
    00
  • 微信小程序 Tab页切换更新数据

    productList: [], cartData: [] }, updateCartData: function() { // 更新购物车数据的逻辑 // … }, onShow: function() { this.updateCartData(); // 更新购物车数据 // … }, // …})“` 在这个示例中,我们在onShow函…

    other 2023年7月29日
    00
合作推广
合作推广
分享本页
返回顶部