Python数据结构与算法之列表(链表,linked list)简单实现

Python数据结构与算法之列表(链表,linkedlist)简单实现

在Python中,列表是一种非常常用的数据类型。除了Python内置的列表,还可以使用链表(linkedlist)来实现列表。链表是一种线性数据结构,由一系列节点组成,每个节点包数据和指向下一个节点的指针。在本文中,我们将详细介绍如何使用Python实现链表,并演示如何使用链实现列表。

链表的实现

在Python中,我们可以使用类来实现链表。每个节点可以表示为一个类的实例,包含数据和指向下一个节点的指针。链表本身也可以表示为一个类的实例,包含指向链表头部的指针。下面是一个简单的链表现:

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

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

上述代码中,我们定义了一个Node类表示链表的节点,包含数据和指向下一个节点的指针。我们还定义了一个LinkedList类表示链表本身,包含指向链表头部的指针。

链表的操作

链表支持许多操作,例如添加元素、删除元素、访问元素等。下面是一些常用的链表操作。

添加元素

要向链表中添加元素,我们可以使用append()函数或insert()函数。append()函数用于在链表末尾添加元素,而insert()函数用于在指定位置添加元素。例如:

# 向链表中添加元素
class:
    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 is not None:
            last_node = last_node.next
        last_node.next = new_node

    def insert(self, prev_node, data):
        if prev_node is None:
            print("Previous node is not in the list")
            return
        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node

上述代码中,我们定义了LinkedList类的append()函数和insert()函数。append()函数用于在表末尾添加元素,如果链表为空,则将新节点设置为链表头部。insert()函数用于在指定位置添加元素,如果指定的前一个节点不存在,则输出错误信息。

删除元素

要从链表中删除元素,我们可以使用remove()函数或pop()函数。remove()函数用于删除指定的元素,而pop()函数用于删除指定位置的元素。例如:

# 从链表中删除元素
class LinkedList:
    def __init__(self):
        self.head = None

    def remove(self, key):
        curr_node = self.head
        if curr_node is not None and curr_node.data == key:
            self.head = curr_node.next
            curr_node = None
            return
        prev_node = None
        while curr_node is not None and curr_node.data != key:
            prev_node = curr_node
            curr_node = curr_node.next
        if curr_node is None:
            return
        prev_node.next = curr_node.next
        curr_node = None

    def pop(self, pos=None):
        if self.head is None:
            return
        curr_node = self.head
        if pos == 0:
            self.head = curr_node.next
            curr_node = None
            return
        prev_node = None
        count = 0
        while curr_node is not None and count != pos:
            prev_node = curr_node
            curr_node = curr_node.next
            count += 1
        if curr_node is None:
            return
        prev_node.next = curr_node.next
        curr_node = None

上述代码中,我们定义了LinkedList类的remove()函数和pop()函数。remove()函数用于删除指定的元素,如果指定的元素不存在,则不进行何操作。pop()函数用于删除指定位置的元素,如果指定的位置不存在,则不进行任何操作。

访问元素

要访链表中的元素,我们可以使用get()函数。get()函数用于获取指定位置的元素。例如:

# 访问链表中的元素
class LinkedList:
    def __init__(self):
        self.head = None

    def get(self, pos):
        curr_node = self.head
        count = 0
        while curr_node is not None and count != pos:
            curr_node = curr_node.next
            count += 1
        if curr_node is None:
            return None
        return curr_node.data

上述代码中,我们定义了LinkedList类的get()函数。get()函数用于获取指定位置的元素,如果指定的位置不存在,则返回None。

示例说明

下面是两个示例,演示了如何使用链表实现列表。

示例1:创建、访问和修改列表

下面是一个示例,演了如何使用链表实现列表的创建、访问和修改:

# 创建、访问和修改列表
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 self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next is not None:
            last_node = last_node.next
        last_node.next = new_node

    def get(self, pos):
        curr_node = self.head
        count = 0
        while curr_node is not None and count != pos:
            curr_node = curr_node.next
            count += 1
        if curr_node is None:
            return None
        return curr_node.data

    def set(self, pos, data):
        curr_node = self.head
        count = 0
        while curr_node is not None and count != pos:
            curr_node = curr_node.next
            count += 1
        if curr_node is None:
            return
        curr_node.data = data

my_list = LinkedList()
my_list.append(1)
my_list.append(2)
my_list.append(3)

print(my_list.get(0))  # 输出:1
print(my_list.get(2))  # 输出:3

my_list.set(1, 4)
print(my_list.get(1))  # 输出:4

上述代码中,我们首先定义了Node类和LinkedList类,分别表示链表的节点和链表本身。然后,我们创建了一个包含3个元素的链表my_list,并使用get()函数访问了链表中的元素。接着,我们使用set()函数修改了链表中的元素,并使用get()函数验证了修改结果。

示例2:添加元素、删除元素和遍历表

下面是一个示例,演示了如何使用链表实现列表的添加元素、删除元素和遍历:

# 添加元素、删除元素和遍历链表
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 self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next is not None:
            last_node = last_node.next
        last_node.next = new_node

    def remove(self, key):
        curr_node = self.head
        if curr_node is not None and curr_node.data == key:
            self.head = curr_node.next
            curr_node = None
            return
        prev_node = None
        while curr_node is not None and curr_node.data != key:
            prev_node = curr_node
            curr_node = curr_node.next
        if curr_node is None:
            return
        prev_node.next = curr_node.next
        curr_node = None

    def traverse(self):
        curr_node = self.head
        while curr_node is not None:
            print(curr_node.data)
            curr_node = curr_node.next

my_list = LinkedList()
my_list.append(1)
my_list.append(2)
my_list.append(3)

my_list.traverse()  # 输出:1 2 3

my_list.remove(2)

my_list.traverse()  # 输出:1 3

上述代码中,我们首先定义了Node类和LinkedList类,分别表示链表的和链表本身。然后,我们创建了一个包含3个元素的链表my_list,并使用traverse()函数遍历了链表中的元素。接着,我们使用remove()函数删除了链表中的元素,并使用traverse()函数验证了删除结果。

总之,链表是一种常重要的数据结构,可以用于实现列表等数据类型。我们可以使用类来实现链表,使用append()函数和insert()函数向链表中添加元素,使用remove()函数和pop()函数从链表中删除元素,使用get()函数访问链表中的元素,使用traverse()函数遍历链表中的元素。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Python数据结构与算法之列表(链表,linked list)简单实现 - Python技术站

(0)
上一篇 2023年5月13日
下一篇 2023年5月13日

相关文章

  • Jmeter并发执行Python 脚本的完整流程

    下面是“Jmeter并发执行Python 脚本的完整流程”的完整攻略及示例说明: 1. 安装 JMeter 首先,要安装 JMeter,可以在官网下载最新版本的 JMeter 并进行安装。安装完成后,我们就可以使用 JMeter 来进行并发执行 Python 脚本了。 2. 新建测试计划 打开 JMeter,点击菜单中的“File”->“New”,然后…

    python 2023年6月3日
    00
  • Python常问的100个面试问题汇总(上篇)

    Python常问的100个面试问题汇总(上篇)攻略 Python是一种高级编程语言,应用广泛,因此在面试中经常会涉到Python相关的问题。本文将介绍Python常问的100面试问题汇总(上篇),包括Python基础、Python高级、Python Web开发、Python爬虫等方面的问题。 1.基础 1.1 Python中的可变数据类型和不可变数据类型有哪…

    python 2023年5月13日
    00
  • C#返回当前系统所有可用驱动器符号的方法

    要返回当前系统所有可用驱动器符号,可以使用C#的System.IO命名空间中的DriveInfo类。下面是获取当前系统所有可用驱动器符号的方法: 引用命名空间 首先在C#文件的顶部添加命名空间引用: using System.IO; 创建DriveInfo对象 DriveInfo类的构造函数需要传入一个字符串参数来指定要获取的驱动器符号。如果要获取系统中所有…

    python 2023年6月3日
    00
  • Python爬取京东商品信息评论存并进MySQL

    Python爬取京东商品信息评论存并进MySQL 本攻略将介绍如何使用Python爬取京东商品信息评论,并将其存储到MySQL数据库中。我们将使用Python的requests库和BeautifulSoup库来获取和解析京东商品信息评论,使用pymysql库来连接和操作MySQL数据库。 获取京东商品信息评论 我们可以使用Python的requests库来获…

    python 2023年5月15日
    00
  • Python正则表达式匹配日期与时间的方法

    正则表达式是一种强大的工具,可以用于匹配、查找和替换文本中的模式。在Python中,re模块提供了一系列函数来操作正则表达式。本攻略将详细讲解Python中正则表达式匹配日期与时间的方法。 匹配日期 使用正则表达式匹配日期,可以使用\d{4}-\d{2}-\d{2}匹配所有的日期格式。下面是一个例子,演示如何使用正则表达式匹配字符串中的日期: import …

    python 2023年5月14日
    00
  • python计算质数的6种方法

    下面就详细讲解“Python计算质数的6种方法”的完整攻略。 1. 前言 算法是计算机科学中非常重要的一个领域,而质数计算是其中一个经典问题。Python是一种强大的编程语言,注重可读性和简洁性,因此特别适合用来解决这样的算法问题。在本篇攻略中,我们将介绍Python计算质数的6种方法。 2. 六种方法 方法一:暴力枚举法 该方法是最基本的算法之一。我们从2…

    python 2023年6月5日
    00
  • 5个Python杀手级的自动化脚本分享

    5个Python杀手级的自动化脚本分享 本攻略将介绍5个Python杀手级的自动化脚本,包括自动化测试、数据分析、网络爬虫、自动化运维和自动化办公。我们将为每个脚本提供详细的步骤和示例代码。 自动化测试 自动化测试是一种自动化执行测试用例的方法,可以提高测试效率和准确性。以下是一个示例代码,用于自动化执行Selenium测试用例: from selenium…

    python 2023年5月15日
    00
  • python网页请求urllib2模块简单封装代码

    在Python中,我们可以使用urllib2模块发送HTTP请求。为了方便重复使用,我们可以将urllib2模块封装成通用的模块。以下是一个详细的攻略,包含了封装urllib2模块的步骤和示例。 1. 导入urllib2模块 在开始之前,我们需要导入urllib2模块。可以使用以下代码导入urllib2模块: import urllib2 2. 封装urll…

    python 2023年5月15日
    00
合作推广
合作推广
分享本页
返回顶部