Python数据结构-----链表1.0（单链表的增删改查以及反转）

目录

前言：

1.单链表

1.1简介

1.2 对比列表

2.单链表的创建

3.单链表的遍历

4.链表元素的查询

5.节点的删除

6.节点的插入

7.链表元素的修改

8.链表的反转

9.全部代码

前言：

前面我们在C语言学习过了数据结构中的链表，既然说到数据结构，那我们可以通过C语言的指针去灵活实现数据结构（链表，栈，队列，二叉树），这就会有人去问了，那Python又没有指针这种东西，如何去实现数据结构呢？别忘了，Python是有面对对象的，一切皆对象，每一个对象都是有一个'类指针'，我们看不见也摸不着的。好了，这里就废话不多说了，一起来学习今天的内容吧---单链表

1.单链表

1.1简介

单链表是数据结构中最简单的线性表，其每一个节点包含数据域（data）和指针域（next），数据域是用来存放内容的，指针域是用来连接下一个节点，也就是说单链表可以实现把一些毫无相关且不连续的空间连接到一起，实现多组数据存放的功能。如图所示：

1.2 对比列表

在此之前我们学习过了列表，那列表是一种空间连续的数据容器，也可以实现多组数据的存放功能，这一点跟链表是一样的。二者最大的不同就是空间连续与不连续，当然，在相关操作中的复杂度也是有出入的

对比

1.按数据查找：

按照顺序查找，列表与链表的时间复杂度是一样的 o(n)

2.按位置查找：

列表的复杂度是 o(1)

链表的复杂度是 o(n)

3.元素的插入：

列表的复杂度是 o(n)

链表的复杂度是 0(1)

4.元素的删除：

列表的复杂度是 0(n)

链表的复杂度是 0(1)

2.单链表的创建

在Python中，一个链表是一个链表对象，其中每一个节点也是一个节点对象，要想实现链表，我们只需要把这些节点对象连接到一起，组合成链表对象就行了。

节点对象的建立：

#建立节点对象
class Listnode(object):
    def __init__(self,data=0,next=None):
        self.data=data
        self.next=next

链表对象的建立：

#建立节点对象
class Listnode(object):
    def __init__(self,data=0,next=None):
        self.data=data
        self.next=next
#创建链表对象
class List(object):
    def __init__(self):#先定义头节点的实例化对象
        self.head=None
    def create(self,alldata):#创建链表,alldata是表示一组数据
        self.head=Listnode(alldata[0]) #创建好头节点，把第一个数据给到头结点
        cur=self.head  #cur为移动指针
        for i in alldata[1:]:#根据数据的多少，依次创建后面的节点
            p=Listnode(i)
            cur.next=p
            cur=p
        return self.head #返回一个这个实例化头节点

这样就实现了一个单链表的创建了，是不是很简单呢？

说明：注意这里建立了一个链表类对象，后面的链表增删改查等方法会放到这个链表类对象当中

3.单链表的遍历

遍历一个链表，把里面的数据依次取出。

接上：

#上面链表对象的创建等内容省略
#……………………
    #遍历链表
    def tarvel(self):
        if self.head: #先判断头结点是否为空
            p=self.head
            while p:
                print(p.data,end=' ')#依次输出数据
                p=p.next
            print('')
        else:
            return
li=List()
li.create([x for x in range(10)])
li.tarvel()
#输出结果：0 1 2 3 4 5 6 7 8 9 

4.链表元素的查询

输入一个元素值value，然后在链表查询这个元素的节点是否存在，如果存在就输出这个节点的位置，如果不存在就输出不存在

 #前面内容接上……
    #链表元素的查询
    def select(self,value):
        if self.head: #判断头结点是否为空
            count=1
            p=self.head
            while p:
                if p.data==value:
                    print(f'在第{count}个节点')
                    break
                else:
                    p=p.next
                    count+=1
            if p==None:
                print('不存在')
        else:
            return None

li=List()
li.create([x for x in range(10)])
li.select(5) #在第6个节点
li.select(55) #不存在

5.节点的删除

输入一个元素，把链表中这个元素节点的位置删除

#内容接上……
    #链表节点的删除
    def remove(self,value):
        if self.head:
            p=self.head
            while p:
                if p.next.data==value: #获取到要删除节点的上一个节点
                    p.next=p.next.next #把下一个获取到的节点指向下下个节点
                    print('删除成功')
                    break
                else:
                    p=p.next
            if p==None:
                print('删除失败')
        else:
            return None

li=List()
li.create([x for x in range(10)])
li.tarvel()
li.remove(5)
li.tarvel()
#输出结果：
# 0 1 2 3 4 5 6 7 8 9
# 删除成功
# 0 1 2 3 4 6 7 8 9

6.节点的插入

给定一个数据value，然后把这个数据插入到链表中第n节点后面

#内容接上……
    #插入数据节点到链表中
    def insert(self,value,n):

        q=Listnode(value) #创建一个节点
        if n == 0:#判断是否插入作为第一个节点
            q.next=self.head
            self.head=q #新节点作为头结点
        else:
            p=self.head
            count=1
            while count<n:
                p=p.next
                count+=1
            q.next=p.next
            p.next=q
            print('插入成功')

li=List()
li.create([x for x in range(10)])
li.tarvel()
li.insert(99,3)
li.tarvel()
#输出结果：
# 0 1 2 3 4 5 6 7 8 9 
# 插入成功
# 0 1 2 99 3 4 5 6 7 8 9 

7.链表元素的修改

给定一个数据value，然后把链表第n个节点的数据改为value

#内容接上……
    #链表元素的修改
    def update(self,value,n):
        if self.head:
            p=self.head
            count=1
            while count<n:
                p=p.next
                count+=1
            p.data=value
            print('修改成功')
        else:
            return None

li=List()
li.create([x for x in range(10)])
li.tarvel()
li.update('newdata',2)
li.tarvel()
#输出结果：
# 0 1 2 3 4 5 6 7 8 9 
# 修改成功
# 0 newdata 2 3 4 5 6 7 8 9 

8.链表的反转

给定一个链表，然后让这个链表倒置输出

如图所示：

要想实现链表的转置，我们只需要把指针域指向的区域反过来就行了，如图所示：

代码实现：

#内容接上……
    #链表的转置
    def reverse(self):
        #初始化操作
        p=self.head.next
        self.head.next=None
        while p:
            q=p.next #获取到当前进行操作节点的下一个节点
            p.next=self.head #然后把当前操作节点的指针域指向上一个节点
            self.head=p       #头节点往后面移动
            p=q               

li=List()
li.create([x for x in range(10)])
li.tarvel()
li.reverse()
li.tarvel()
#输出结果：
# 0 1 2 3 4 5 6 7 8 9 
# 9 8 7 6 5 4 3 2 1 0 

9.全部代码

以上就是Python中链表增删改查以及转置的全部内容了，下面就是全部代码：

#建立节点对象
class Listnode(object):
    def __init__(self,data=0,next=None):
        self.data=data
        self.next=next
#创建链表对象
class List(object):
    def __init__(self):#先定义头节点的实例化对象
        self.head=None
    # 创建链表
    def create(self,alldata):#alldata是表示一组数据
        self.head=Listnode(alldata[0]) #创建好头节点，把第一个数据给到头结点
        cur=self.head  #cur为移动指针
        for i in alldata[1:]:#根据数据的多少，依次创建后面的节点
            p=Listnode(i)
            cur.next=p
            cur=p
        return self.head #返回一个这个实例化头节点
    #遍历链表
    def tarvel(self):
        if self.head: #先判断头结点是否为空
            p=self.head
            while p:
                print(p.data,end=' ')#依次输出数据
                p=p.next
            print('')
        else:
            return
    #链表元素的查询
    def select(self,value):
        if self.head:
            count=1
            p=self.head
            while p:
                if p.data==value:
                    print(f'在第{count}个节点')
                    break
                else:
                    p=p.next
                    count+=1
            if p==None:
                print('不存在')
        else:
            return None
#内容接上……
    #链表节点的删除
    def remove(self,value):
        if self.head:
            p=self.head
            while p:
                if p.next.data==value: #获取到要删除节点的上一个节点
                    p.next=p.next.next #把下一个获取到的节点指向下下个节点
                    print('删除成功')
                    break
                else:
                    p=p.next
            if p==None:
                print('删除失败')
        else:
            return None
#内容接上……
    #插入数据节点到链表中
    def insert(self,value,n):

        q=Listnode(value) #创建一个节点
        if n == 0:#判断是否插入作为第一个节点
            q.next=self.head
            self.head=q #新节点作为头结点
        else:
            p=self.head
            count=1
            while count<n:
                p=p.next
                count+=1
            q.next=p.next
            p.next=q
            print('插入成功')
#内容接上……
    #链表元素的修改
    def update(self,value,n):
        if self.head:
            p=self.head
            count=1
            while count<n:
                p=p.next
                count+=1
            p.data=value
            print('修改成功')
        else:
            return None
#内容接上……
    #链表的转置
    def reverse(self):
        #初始化操作
        p=self.head.next
        self.head.next=None
        while p:
            q=p.next #获取到当前进行操作节点的下一个节点
            p.next=self.head #然后把当前操作节点的指针域指向上一个节点
            self.head=p       #头节点往后面移动
            p=q

这些就是链表类型的相关方法，over

好了，这一期就到这里了，我们下一期再见！

分享一张壁纸：