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日

相关文章

  • Python – 从长度不等的列表中获取所有具有替换的唯一组合

    【问题标题】:Python – Get all unique combinations with replacement from lists of list with unequal lengthPython – 从长度不等的列表中获取所有具有替换的唯一组合 【发布时间】:2023-04-02 14:55:01 【问题描述】: 注意:这不是标题所说的重复问…

    Python开发 2023年4月8日
    00
  • python实现自动化脚本编写

    Python实现自动化脚本编写攻略 自动化脚本编写是指利用编程语言等工具自动化执行某些操作,提高工作效率和减少人工错误的发生。Python是一门易于学习和使用的编程语言,在自动化脚本编写中有着广泛应用。以下是实现自动化脚本编写的攻略: 第一步:了解需要自动化的任务 在开始自动化脚本编写前,我们需要了解需要自动化的任务,确定任务的目标和预期结果。例如,我们想要…

    python 2023年5月19日
    00
  • 实例Python处理XML文件的方法

    Python处理XML文件是一个常见的应用场景。在本文中,我们将深入讲解如何使用Python处理XML文件,并提供两个示例,以便更好地理解这个过程。 Python处理XML文件的方法 Python处理XML文件的方法如下: 使用ElementTree模块解析XML文件,获取XML根节点。 使用ElementTree模块的方法,如find()、findall(…

    python 2023年5月15日
    00
  • 基于PyQt5制作一个windows通知管理器

    下面是制作一个Windows通知管理器的完整攻略,包含以下步骤: 步骤一:安装并学习PyQt5 PyQt5是基于Python的GUI框架,用于创建跨平台的应用程序。首先需要安装PyQt5,可以使用pip工具来安装: pip install PyQt5 然后需要学习PyQt5的基础知识,包括信号与槽、控件、布局等。 步骤二:创建主界面 首先需要创建一个主界面,…

    python 2023年6月3日
    00
  • python中字符串的操作方法大全

    Python中字符串的操作方法大全 在Python中,字符串是一种不可变的序列类型,可以使用多种方法进行操作。本文将介绍Python中字符串的操作方法,包括字符串的创建、字符串的索引和切片、字符串的拼接和重复、字符串的查和替换、字符串的大小写转换、字符串的分割和连接、字符串格式化等。 字符串的创建 在Python中,可以使用单引号、引号或三引号来创建字符串。…

    python 2023年5月13日
    00
  • Python实现学生管理系统的完整代码(面向对象)

    “Python实现学生管理系统的完整代码(面向对象)”是一个非常常见的Python实战项目,通过实现学生管理系统的完整代码,可以学习到Python面向对象编程的基础知识和应用。 下面介绍Python实现学生管理系统的完整攻略: 1. 确定系统需求和功能模块 在实现一个学生管理系统之前,我们需要先确定系统的需求和功能模块。通过需求分析,我们可以确定一个学生管理…

    python 2023年5月19日
    00
  • python实现扫雷小游戏

    Python实现扫雷小游戏 1. 确定游戏规则 在开始编写扫雷小游戏之前,我们需要先明确游戏规则。简单来说,扫雷游戏的规则如下: 棋盘上有若干个方块 有些方块下面藏有地雷 玩家需要翻开方块,如果是地雷则游戏结束 每个方块周围的数字表示该方块周围8个方块中地雷的数量 玩家需要根据周围的数字猜测哪些方块隐藏地雷 当所有非地雷的方块都被翻开时,游戏胜利 2. 设计…

    python 2023年5月14日
    00
  • python小程序实现刷票功能详解

    Python小程序实现刷票功能详解 如果你正在寻找一些刷票的Python小程序代码,那么你来到了正确的地方。这篇文章将为你提供一系列的示例和说明,让你了解如何通过Python编写一个简单的刷票程序。 步骤1:选择一个要刷的网站 首先,你需要确定一个要进行刷票的网站。在选择网站时,需要注意选择正规的、合法的,不会侵犯他人利益的网站。否则,你会处于违法和不道德的…

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