首页 > 编程语言 >链表（Linked List）-Python实现-使用类和使用函数

链表（Linked List）-Python实现-使用类和使用函数

时间：2024-07-19 19:25:33浏览次数：17  
标签：node current head Python List next 链表 节点

链表

链表（Linked List）

链表是一种常见的数据结构，它由一系列节点（Node）组成，每个节点包含数据和指向下一个节点的引用（指针）。链表的主要优点是插入和删除操作的时间复杂度为O(1)，但访问特定元素的时间复杂度为O(n)。

单链表（Singly Linked List）

单链表是最简单的链表形式，每个节点只有一个指向下一个节点的引用。

节点类（Node Class）

首先，我们需要定义一个节点类，每个节点包含数据和指向下一个节点的引用。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
链表类（Linked List Class）

接下来，我们定义一个链表类，包含链表的头节点和一些基本操作。

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

    def is_empty(self):
        return self.head is None

    def append(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

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

    def delete(self, key):
        current = self.head
        previous = None
        while current and current.data != key:
            previous = current
            current = current.next
        if current is None:
            return
        if previous is None:
            self.head = current.next
        else:
            previous.next = current.next

    def search(self, key):
        current = self.head
        while current and current.data != key:
            current = current.next
        return current is not None

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")
使用链表类

我们可以创建一个链表实例并进行一些操作。

# 创建链表实例
llist = LinkedList()

# 添加元素
llist.append(1)
llist.append(2)
llist.append(3)

# 显示链表
llist.display()  # 输出: 1 -> 2 -> 3 -> None

# 在头部添加元素
llist.prepend(0)
llist.display()  # 输出: 0 -> 1 -> 2 -> 3 -> None

# 删除元素
llist.delete(2)
llist.display()  # 输出: 0 -> 1 -> 3 -> None

# 搜索元素
print(llist.search(1))  # 输出: True
print(llist.search(2))  # 输出: False

不用类的方法实现链表

虽然使用类的方法实现链表更加面向对象和模块化，但我们也可以不使用类的方法来实现链表。这种方法通常用于简单的脚本或小规模的数据处理。

实现单链表

我们可以使用函数和字典来实现链表。

def create_node(data):
    return {"data": data, "next": None}

def append_node(head, data):
    new_node = create_node(data)
    if head is None:
        return new_node
    current = head
    while current["next"]:
        current = current["next"]
    current["next"] = new_node
    return head

def prepend_node(head, data):
    new_node = create_node(data)
    new_node["next"] = head
    return new_node

def delete_node(head, key):
    current = head
    previous = None
    while current and current["data"] != key:
        previous = current
        current = current["next"]
    if current is None:
        return head
    if previous is None:
        head = current["next"]
    else:
        previous["next"] = current["next"]
    return head

def search_node(head, key):
    current = head
    while current and current["data"] != key:
        current = current["next"]
    return current is not None

def display_list(head):
    current = head
    while current:
        print(current["data"], end=" -> ")
        current = current["next"]
    print("None")
使用函数实现链表

我们可以使用这些函数来创建和操作链表。

# 创建链表
head = None

# 添加元素
head = append_node(head, 1)
head = append_node(head, 2)
head = append_node(head, 3)

# 显示链表
display_list(head)  # 输出: 1 -> 2 -> 3 -> None

# 在头部添加元素
head = prepend_node(head, 0)
display_list(head)  # 输出: 0 -> 1 -> 2 -> 3 -> None

# 删除元素
head = delete_node(head, 2)
display_list(head)  # 输出: 0 -> 1 -> 3 -> None

# 搜索元素
print(search_node(head, 1))  # 输出: True
print(search_node(head, 2))  # 输出: False

具体讲解

类的方法实现链表

Node类
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
  • __init__方法：这是Node类的构造方法，用于初始化节点的数据和指向下一个节点的引用。
LinkedList类
class LinkedList:
    def __init__(self):
        self.head = None
  • __init__方法：这是LinkedList类的构造方法，用于初始化链表的头节点。
    def is_empty(self):
        return self.head is None
  • is_empty方法：这个方法用于检查链表是否为空。如果头节点为None，则链表为空。
    def append(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
  • append方法：这个方法用于在链表的末尾添加一个新节点。如果链表为空，则新节点成为头节点；否则，遍历链表直到找到最后一个节点，然后将新节点添加到其后面。
    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
  • prepend方法：这个方法用于在链表的头部添加一个新节点。新节点的next指针指向当前的头节点，然后新节点成为新的头节点。
    def delete(self, key):
        current = self.head
        previous = None
        while current and current.data != key:
            previous = current
            current = current.next
        if current is None:
            return
        if previous is None:
            self.head = current.next
        else:
            previous.next = current.next
  • delete方法：这个方法用于删除链表中第一个值为key的节点。遍历链表，找到值为key的节点，然后将其从链表中移除。如果节点是头节点，则更新头节点；否则，更新前一个节点的next指针。
    def search(self, key):
        current = self.head
        while current and current.data != key:
            current = current.next
        return current is not None
  • search方法：这个方法用于检查链表中是否存在值为key的节点。遍历链表，找到值为key的节点，如果找到则返回True，否则返回False。
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")
  • display方法：这个方法用于显示链表中的所有节点。遍历链表，打印每个节点的数据，最后打印"None"表示链表结束。

不用类的方法实现链表

创建节点
def create_node(data):
    return {"data": data, "next": None}
  • create_node函数：这个函数用于创建一个新节点，返回一个包含数据和next指针的字典。
添加节点
def append_node(head, data):
    new_node = create_node(data)
    if head is None:
        return new_node
    current = head
    while current["next"]:
        current = current["next"]
    current["next"] = new_node
    return head
  • append_node函数：这个函数用于在链表的末尾添加一个新节点。如果链表为空，则新节点成为头节点；否则，遍历链表直到找到最后一个节点，然后将新节点添加到其后面。
def prepend_node(head, data):
    new_node = create_node(data)
    new_node["next"] = head
    return new_node
  • prepend_node函数：这个函数用于在链表的头部添加一个新节点。新节点的next指针指向当前的头节点，然后新节点成为新的头节点。
删除节点
def delete_node(head, key):
    current = head
    previous = None
    while current and current["data"] != key:
        previous = current
        current = current["next"]
    if current is None:
        return head
    if previous is None:
        head = current["next"]
    else:
        previous["next"] = current["next"]
    return head
  • delete_node函数：这个函数用于删除链表中第一个值为key的节点。遍历链表，找到值为key的节点，然后将其从链表中移除。如果节点是头节点，则更新头节点；否则，更新前一个节点的next指针。
搜索节点
def search_node(head, key):
    current = head
    while current and current["data"] != key:
        current = current["next"]
    return current is not None
  • search_node函数：这个函数用于检查链表中是否存在值为key的节点。遍历链表，找到值为key的节点，如果找到则返回True，否则返回False。
显示链表
def display_list(head):
    current = head
    while current:
        print(current["data"], end=" -> ")
        current = current["next"]
    print("None")
  • display_list函数：这个函数用于显示链表中的所有节点。遍历链表，打印每个节点的数据，最后打印"None"表示链表结束。

通过这些方法和函数，我们可以实现链表的基本操作，包括添加、删除、搜索和显示节点。

总结

链表是一种重要的数据结构，适用于需要频繁插入和删除操作的场景。通过类的方法实现链表可以使代码更加模块化和面向对象，而不用类的方法实现链表则更加简单和直接。选择哪种方法取决于具体的应用场景和个人偏好。

标签：node,current,head,Python,List,next,链表,节点
From： https://blog.csdn.net/xycxycooo/article/details/140500854

相关文章

  • Python-request库的详细解析
    引言在现代网络应用中，与服务器进行通信是一个非常基础且重要的功能。Python的requests库是一个非常强大且易于使用的HTTP库，它允许我们发送HTTP请求，与Web服务进行交互。本文将详细介绍requests库的使用，包括其基本概念、常用功能以及一些高级用法。安装requests库在使用req......
  • python实现爆破wifi密码
    importpywifiimporttimefrompywifiimportconst#WiFi扫描模块defwifi_scan():#初始化wifiwifi=pywifi.PyWiFi()#使用第一个无线网卡interface=wifi.interfaces()[0]#开始扫描interface.scan()foriinrange(4):t......
  • python+flask计算机毕业设计企业固定资产档案管理系统（程序+开题+论文）
    本系统（程序+源码+数据库+调试部署+开发环境）带论文文档1万字以上，文末可获取，系统界面在最后面。系统程序文件列表开题报告内容研究背景随着企业规模的不断扩大和业务的日益复杂化，固定资产作为企业重要的经济资源，其管理效率直接影响到企业的运营成本和资产利用率。传统的手工......
  • python+flask计算机毕业设计汽车零件维修管理信息平台（程序+开题+论文）
    本系统（程序+源码+数据库+调试部署+开发环境）带论文文档1万字以上，文末可获取，系统界面在最后面。系统程序文件列表开题报告内容研究背景随着汽车工业的飞速发展，汽车保有量持续增长，汽车零部件维修与管理成为汽车行业不可忽视的重要环节。传统的手工记录与管理模式已难以满足现......
  • python爬虫实现简单的代理ip池
    python爬虫实现简单的代理ip池我们在普通的爬虫过程中经常遇到一些网站对ip进行封锁的下面演示一下普通的爬虫程序使用requests.get爬取数据这段代码是爬取豆瓣排行榜的数据，使用f12来查看请求的url和数据格式代码defrequestData():#爬取数据的urlurl:s......
  • 链表。。。
    模板题AcWing826.单链表实现一个单链表，链表初始为空，支持三种操作：向链表头插入一个数；删除第k个插入的数后面的数；在第k个插入的数后插入一个数。现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。注意:题目中第k个插入的数并不是指当前链表的第......
  • 02线性表 - 链表
    这里是只讲干货不讲废话的炽念，这个系列的文章是为了我自己以后复习数据结构而写，所以可能会用一种我自己能够听懂的方式来描述，不会像书本上那么枯燥和无聊，且全系列的代码均是可运行的代码，关键地方会给出注释^_^全文1W+字版本：C++17编译器：Clion2023.3.24暂时只给出代码，不会涉......
  • 【代码随想录训练营第42期 Day3打卡 LeetCode 203.移除链表元素，707.设计链表，206.反转
    一、做题感受今天是打卡的第三天，前两天题目主要考察数组相关知识，现在已经来到了链表的学习。题目共有三道，都是以考察单链表为主，整体来说难度不大，但是思路很灵活，尤其是反转链表的考察，双指针的新用法。今天做题总体感觉不错，能有自己的思考和理解。二、链表相关知识1.常见链表......
  • 基于Python星载气溶胶数据处理与反演分析
    在当前全球气候变化和环境污染问题日益突出的背景下，气溶胶研究显得尤为重要。气溶胶在大气中由直径范围在0.01微米至10微米固体和液体颗粒构成，直接或间接影响地球辐射平衡、气候变化和空气质量。尤其在“碳中和”目标的驱动下，研究气溶胶对“碳中和”的气候影响及其环境效应，不仅......
  • [附开题]flask框架的基于web的线上考试管理系统的设计与实现n1qn5（python+源码）
    本系统（程序+源码+数据库+调试部署+开发环境）带论文文档1万字以上，文末可获取，系统界面在最后面。系统程序文件列表开题报告内容研究背景随着互联网技术的飞速发展，教育领域正经历着深刻的变革。传统的线下考试模式逐渐显露出其局限性，如组织成本高、效率低下、资源分配不均等问......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99