Python实现链表

链表是一系列数据元素,它们通过指针连接在一起。每个数据元素都包含指向指针形式的另一个数据元素的连接。

Python在其标准库中没有链接列表;作者将使用的节点的概念来实现链表。

关于如何实现节点可参考:https://www.perfcode.com/p/1346.html

在本文中,我们将研究称为单链表的链表的类型。 在这种类型的数据结构中,任何两个数据元素之间只有一个链接。 我们创建了这样一个列表,并创建了其他方法来从列表中插入,更新和删除元素。

创建一个链表

我们创建一个Node对象,并创建另一个类来使用该Node对象。 我们通过节点对象传递适当的值,以指向下一个数据元素。

下面的程序使用三个数据元素创建链接列表:

class Node:
    def __init__(self,dataval=None):
        self.dataval = dataval
        self.nextval = None
 
class SLinkedList:
    def __init__(self):
        self.headval = None
          
list1 = SLinkedList()
list1.headval = Node("星期一")
 
e2 = Node("星期二")
e3 = Node("星期三")
 
# 将第一个节点链接到第二个节点
list1.headval.nextval = e2
# 将第二个节点链接到第三个节点
e2.nextval = e3

遍历链表

单链表只能从第一个数据元素开始沿向前的方向遍历。 我们只需将当前数据元素的指针指向下一个节点,就可以打印下一个数据元素的值。

修改SLinkedList类,为其添加一个listprint()方法:

def listprint(self):
    printval = self.headval
        
    while printval is not None:
        print (printval.dataval)
        printval=printval.nextval

通过调用 list1.listprint() 方法,程序将打印星期一,星期二,星期三。

插入链表

在链表中插入元素涉及将指针从现有节点重新分配给新插入的节点。 根据是在链表的开头,中间还是结尾插入新数据元素,我们有以下几种情况:

1.在链表的开头插入

这涉及将新数据节点的下一个指针指向链接列表的当前头。 因此,链表的当前头成为第二个数据元素,新节点成为链表的头。

修改SLinkedList类,加入AtBegining()方法:

def AtBegining(self,newdata):
    NewNode = Node(newdata)
    #将新节点的下一个值更新为现有节点
    NewNode.nextval = self.headval
    self.headval = NewNode

在链表的末尾插入

这涉及将链接列表的当前最后一个节点的下一个指针指向新的数据节点。 因此,链表的当前最后一个节点将成为倒数第二个数据节点,新节点将成为链表的最后一个节点。

修改SLinkedList类,为其添加AtEnd()方法:

def AtEnd(self, newdata):
    NewNode = Node(newdata)
    if self.headval is None:
        self.headval = NewNode
        return
    laste = self.headval
    while(laste.nextval):
        laste = laste.nextval
    laste.nextval=NewNode

按照前文的方法修改代码重新运行查看效果。

3.在两个数据节点之间插入

这涉及跟踪特定节点的指针以指向新节点。 通过传入新节点和现有节点,然后插入新节点,这是可能的。 因此,我们定义了一个新的方法,它将新节点的下一个指针更改为中间节点的下一个指针。 然后将新节点分配给中间节点的下一个指针。

修改SLinkedList类,添加一个Inbetween()方法:

def Inbetween(self,middle_node,newdata):
    if middle_node is None:
         print("节点不存在")
         return
    NewNode = Node(newdata)
    NewNode.nextval = middle_node.nextval
    middle_node.nextval = NewNode

按照前文方法加入list1.Inbetween(list1.headval.nextval,”星期五”)再重新运行程序。

原创内容,如需转载,请注明出处;

本文地址: https://www.perfcode.com/p/1349.html

分类: 计算机技术
推荐阅读:
Python 列表(List)的详细用法 列表(list)按特定顺序存储一系列项目。你可以使用索引或在循环中访问项。本问讲述了Python中列表的增加、修改、删除、遍历、复制等基本操作。
Rust使用cfg来实现不同系统的条件编译 Rust使用cfg来实现不同系统的条件编译
未定义标识符 CV_BayerGR2BGR 解决方法 CV_BayerGR2BGR 是 OpenCV 中的颜色转换常量,值为49,在文件 opencv2/imgproc/types_c.h 中定义;提示未定义标识符CV_BayerGR2BGR是因为没有引入opencv2/imgproc/types_c.h这个头文件;
Python globals()函数 globals() 是 Python 内置函数之一,用于返回当前全局作用域中所有变量的字典。这个字典包含了所有已定义的全局变量,键为变量名,值为对应的值。可以通过修改这个字典中的变量来更新全局作用域中的变量。
Python 使用tld库获取复杂URL的顶级域名 我们会碰到各种各样的URL链接,比如:www.a.com/ b.com.cn/ a.b.c.com.cn a.com/b.com Python有内置的库可以识别一些简单的URL,但是像a.b.c.com.cn这样却无能为力。我们需要一个强大的第三方库来实现提取顶级域名。
让Linux终端像电影里一样下起数字雨 在Linux系统里,如果你想要实现电影里的数字雨,一条命令即可: