hao同学的技术博客

  • 首页
  • Java
    • Java
    • JVM教程
    • Java面试
    • Java并发入门
    • Java并发进阶
  • 项目
    • 从零打造项目
  • Python
    • Python
    • Python爬虫
    • 算法
  • Java框架
    • Spring
    • SpringBoot
  • 前端
    • Angular
  • 其他
    • Linux
    • SQL
  • 随笔
分享技术,记录人生
一个痴迷于技术的厨艺爱好者
  1. 首页
  2. 算法
  3. 正文

Python 实现单链表

2022年5月23日 385点热度 0人点赞 0条评论

Python 实现单链表插图

前言

数据结构中的线性表:分为顺序表和链表。

线性表

线性表(Linear List)是由 n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1]组成的有限序列。

其中:

  • 数据元素的个数 n 定义为表的长度 = "list".length() ("list".length() = 0(表里没有一个元素)时称为空表)
  • 将非空的线性表(n>=1)记作:(a[0],a[1],a[2],…,a[n-1])
  • 数据元素 a[i](0≤i≤n-1)只是个抽象符号,其具体含义在不同情况下可以不同

一个数据元素可以由若干个数据项组成。数据元素称为记录,含有大量记录的线性表又称为文件。这种结构具有下列特点:存在一个唯一的没有前驱的(头)数据元素;存在一个唯一的没有后继的(尾)数据元素;此外,每一个数据元素均有一个直接前驱和一个直接后继数据元素。

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。它具有以下特点:

  • 长度固定,必须在分配内存之前确定数组的长度。
  • 地址空间连续,即允许元素的随机访问。
  • 存储密度大,内存中存储的全部是数据元素。
  • 要访问特定元素,可以使用索引访问,时间复杂度为 O(1)。
  • 要想在顺序表中插入或删除一个元素,由于要满足地址的连续性,涉及到之后所有元素的移动,因此时间复杂度为 O(n)。

链表

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到 O(1) 的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间,而顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。

应用

单链表的实现

C 语言实现链表是靠指针与结构体实现的,结构体(结点)的尾部是指向下一结点的指针,Python 没有指针,但是 Python 可以通过定义一个类,类中的一个元素就存放在下一个结点,这样也可以实现链表。

节点对象

#节点对象
class Node():
    def __init__(self, val=None):
        self.val = val  #节点数据值
        self.next = None    #相连的下一个节点对象

    def __str__(self):
        return str(self.val)

依靠节点对象,实现单链表的一系列简单操作。

#单链表
class SingleLinkList():
    def __init__(self, node=None):
        self._header = node

    def add(self, var):
        '''
        单链表添加元素
        :param var:传过来的数据
        :return:
        '''
        node = Node(var)  # 将数据封装为节点
        if self._header == None:
            self._header = node
        else:
            cur = self._header
            while cur.next != None:
                cur = cur.next  #移动游标
            cur.next = node

    def traversal(self):
        '''
        遍历输出单链表
        :return:
        '''
        if self._header == None:
            return
        else:
            cur = self._header
            while cur != None:
                print(cur)
                cur = cur.next

    def size(self):
        '''
        链表长度
        :return:
        '''
        count = 0
        if self._header != None:
            cur = self._header
            while cur != None:
                count += 1
                cur = cur.next

        return count

    def update(self, index, val):
        '''
        修改某索引值下的节点数据
        :param index:
        :param val:
        :return:
        '''
        size = self.size()
        node = Node(val)

        if size == 0:
            print('Empty,can\'t update')
            return

        if index < 0 or index > size-1:
            print('Index is error')
            return

        cur = self._header
        for i in range(index+1):
            if index == 0:
                self._header = node
                self._header.next = cur.next
                break
            if i == index:
                pre.next = node
                node.next = cur.next
                break
            pre = cur
            cur = cur.next

    def delete(self, index):
        '''
        根据索引删除链表中的数据(索引从0开始)
        :param index: 索引值
        :return:
        '''
        size = self.size()
        if size == 0:
            print('Empty,can\'t delete')
            return

        if index < 0 or index > size-1:
            print('Index is error')
            return

        cur = self._header
        for i in range(index+1):
            if index == 0:
                self._header = cur.next
                break
            if i == index:
                pre.next = cur.next
                break
            pre = cur
            cur = cur.next
            print(f'pre:{pre},cur:{cur}')

    def reverse(self):
        '''
        单链表反转
        :return:
        '''
        if self._header == None or self.size() == 1:
            return self
        else:
            pre = None  # 让头节点.next先断开,因为反转后之前的头结点变为尾节点,所以该节点.next应为置为None
            cur = self._header  # 从原先的头节点开始
            while cur != None:
                post = cur.next  # 保存下一个节点
                cur.next = pre  # 更换当前节点的next
                pre = cur  # 更新pre,用于下个节点的next
                cur = post  # 按照单链表原先的顺序进行遍历
            self._header = pre  # 逆转后的头节点

if __name__ == '__main__':
    single_link = SingleLinkList()
    single_link.add(3)
    single_link.add(5)
    single_link.add(6)
    single_link.add(7)
    single_link.add(8)
    print("对链表进行遍历")
    single_link.traversal()

    # print("根据索引对链表进行删除(索引从0开始)")
    # index = 4
    # single_link.delete(index)
    # single_link.traversal()

    print("根据索引对链表进行修改(索引从0开始)")
    index = 2
    single_link.update(index,'a')
    single_link.traversal()

    print("对链表进行逆向操作之后")
    single_link.reverse()
    single_link.traversal()
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: Python 算法
最后更新:2022年5月23日

hresh

这是一个专注于IT技术学习交流的个人技术博客网站,包括Java学习、Python爬虫、Web开发实践等领域,深耕Java领域,内容涵盖Java基础、Java并发编程、Java虚拟机、Java面试等核心知识点。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

hresh

这是一个专注于IT技术学习交流的个人技术博客网站,包括Java学习、Python爬虫、Web开发实践等领域,深耕Java领域,内容涵盖Java基础、Java并发编程、Java虚拟机、Java面试等核心知识点。

文章目录
  • 前言
  • 应用
最新 热点 随机
最新 热点 随机
后端必知:遵循Google Java规范并引入checkstyle检查 Spring Security结合Redis实现缓存功能 Spring Security结合JWT实现认证与授权 Spring Security自定义认证逻辑实现图片验证码登录 Spring Security进阶学习 Spring Security入门学习
Python 判断两个单链表的交点 基于SpringBoot将Json数据导入到数据库 Python实现百度贴吧图片爬取 代理模式详解 Angular基础知识学习(一) Java面试准备之JVM系列三

COPYRIGHT © 2022 hao同学的技术博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

鄂ICP备2022007381号

鄂公网安备 42010302002449号