Python - 链表(Linked)

Python - 链表(Linked) 首页 / 数据结构入门教程 / Python - 链表(Linked)

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

创建链表

无涯教程创建一个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("Mon")
e2=Node("Tue")
e3=Node("Wed")
# 将第一个节点链接到第二个节点
list1.headval.nextval=e2

# 将第二个节点链接到第三个节点
e2.nextval=e3

遍历链表

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

class Node:
    def __init__(self, dataval=None):
        self.dataval=dataval
        self.nextval=None

class SLinkedList:
    def __init__(self):
        self.headval=None

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

list=SLinkedList()
list.headval=Node("Mon")
e2=Node("Tue")
e3=Node("Wed")

# 将第一个节点链接到第二个节点
list.headval.nextval=e2

# 将第二个节点链接到第三个节点
e2.nextval=e3

list.listprint()

执行以上代码后,将产生以下输出:

Mon
Tue
Wed

插入链表

在链表中插入元素涉及将指针从现有节点重新分配给新插入的节点,取决于是否在以下位置插入新数据元素 在链表的开头,中间或结尾,有以下情形。

链表开头插入

将新数据节点的下一个指针指向链接列表的头节点。

链接:https://www.learnfk.comhttps://www.learnfk.com/python-data-structure/python-linked-lists.html

来源:LearnFk无涯教程网

class Node:
    def __init__(self, dataval=None):
        self.dataval=dataval
        self.nextval=None

class SLinkedList:
    def __init__(self):
        self.headval=None

# 打印链表
    def listprint(self):
        printval=self.headval
        while printval is not None:
            print (printval.dataval)
            printval=printval.nextval
    def AtBegining(self,newdata):
        NewNode=Node(newdata)

# 将新节点 next val 更新为现有节点
        NewNode.nextval=self.headval
        self.headval=NewNode

list=SLinkedList()
list.headval=Node("Mon")
e2=Node("Tue")
e3=Node("Wed")

list.headval.nextval=e2
e2.nextval=e3

list.AtBegining("Sun")

list.listprint()

执行以上代码后,将产生以下输出:

Sun
Mon
Tue
Wed

链表末尾插入

将新数据节点链接插入到最后一个节点的下一个指针指向的节点。

class Node:
    def __init__(self, dataval=None):
        self.dataval=dataval
        self.nextval=None

class SLinkedList:
    def __init__(self):
        self.headval=None

#添加新节点的函数
    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

# 打印链表
    def listprint(self):
        printval=self.headval
        while printval is not None:
            print (printval.dataval)
            printval=printval.nextval


list=SLinkedList()
list.headval=Node("Mon")
e2=Node("Tue")
e3=Node("Wed")

list.headval.nextval=e2
e2.nextval=e3

list.AtEnd("Thu")

list.listprint()

执行以上代码后,将产生以下输出:

Mon
Tue
Wed
Thu

节点之间插入

将新节点的下一个指针更改为中间节点的下一个指针,然后将新节点分配给中间节点的下一个指针。

class Node:
    def __init__(self, dataval=None):
        self.dataval=dataval
        self.nextval=None

class SLinkedList:
    def __init__(self):
        self.headval=None

# 添加节点的函数
    def Inbetween(self,middle_node,newdata):
        if middle_node is None:
            print("The mentioned node is absent")
            return

        NewNode=Node(newdata)
        NewNode.nextval=middle_node.nextval
        middle_node.nextval=NewNode

# 打印链表
    def listprint(self):
        printval=self.headval
        while printval is not None:
            print (printval.dataval)
            printval=printval.nextval


list=SLinkedList()
list.headval=Node("Mon")
e2=Node("Tue")
e3=Node("Thu")

list.headval.nextval=e2
e2.nextval=e3

list.Inbetween(list.headval.nextval,"Fri")

list.listprint()

执行以上代码后,将产生以下输出:

Mon
Tue
Fri
Thu

链表删除节点

找到要删除的节点的上一个节点, 然后,将该节点的下一个指针指向要删除的节点的下一个节点。

无涯教程网

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

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

    def Atbegining(self, data_in):
        NewNode=Node(data_in)
        NewNode.next=self.head
        self.head=NewNode
		
#删除节点的函数
    def RemoveNode(self, Removekey):

        HeadVal=self.head

        if (HeadVal is not None):
            if (HeadVal.data == Removekey):
                self.head=HeadVal.next
                HeadVal=None
                return

        while (HeadVal is not None):
            if HeadVal.data == Removekey:
                break
            prev=HeadVal
            HeadVal=HeadVal.next

        if (HeadVal == None):
            return

        prev.next=HeadVal.next

        HeadVal=None

    def LListprint(self):
        printval=self.head
        while (printval):
            print(printval.data),
            printval=printval.next


llist=SLinkedList()
llist.Atbegining("Mon")
llist.Atbegining("Tue")
llist.Atbegining("Wed")
llist.Atbegining("Thu")
llist.RemoveNode("Tue")
llist.LListprint()

执行以上代码后,将产生以下输出:

Thu
Wed
Mon

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

OpenResty从入门到实战 -〔温铭〕

ZooKeeper实战与源码剖析 -〔么敬国〕

Node.js开发实战 -〔杨浩〕

检索技术核心20讲 -〔陈东〕

如何读懂一首诗 -〔王天博〕

零基础实战机器学习 -〔黄佳〕

自动化测试高手课 -〔柳胜〕

Web 3.0入局攻略 -〔郭大治〕

云原生架构与GitOps实战 -〔王炜〕

好记忆不如烂笔头。留下您的足迹吧 :)