道县找人做网站,深圳做网站得外包公司,房山网站建设服务,沈阳关键词排名首页链表
链表#xff1a;适用于插入删除多、读少的场景。
链表在新增、删除数据都比较容易#xff0c;可以在 O(1) 的时间复杂度内完成。 但对于查找#xff0c;不管是按照位置的查找还是按照数值条件的查找#xff0c;都需要对全部数据进行遍历。这显然就是 O(n) 的时间复杂…链表
链表适用于插入删除多、读少的场景。
链表在新增、删除数据都比较容易可以在 O(1) 的时间复杂度内完成。 但对于查找不管是按照位置的查找还是按照数值条件的查找都需要对全部数据进行遍历。这显然就是 O(n) 的时间复杂度
定一个奇数个元素的链表查找出这个链表中间位置的结点的数值——— 一个巧妙的办法就是利用快慢指针进行处理。其中快指针每次循环向后跳转两次而慢指针每次向后跳转一次
链表的基本操作读取O(n)、更新O(1)、插入O(1)、删除O(1)。
栈
栈——特殊的线性表——高频使用新增、删除操作且新增和删除操作的数据执行顺序具备后来居上的相反关系时
后进先出一个杯子——浏览器都有页面前进和后退功能这就是个很典型的后进先出的场景 表尾用来输入数据通常也叫作栈顶top相应地表头就是栈底bottom。栈顶和栈底是用来表示这个栈的两个指针 对于栈的新增操作通常也叫作 push 或压栈。对于栈的删除操作通常也叫作 pop 或出栈
一个 top 指针来指示栈顶元素在数组中的位置。假设栈中只有一个数据元素则 top 0。一般以 top 是否为 -1 来判定是否为空栈。 当定义了栈的最大容量为 StackSize 时则栈顶 top 必须小于 StackSize。
删除数据元素即出栈操作只需要 top - 1 就可以了。
对于查找操作栈没有额外的改变跟线性表一样它也需要遍历整个栈来完成基于某些条件的数值查找。
对于链栈来说是不需要头指针的。相反它需要增加指向栈顶的 top 指针这是压栈和出栈操作的重要支持
新增操作和删除操作时间复杂度都是 O(1。 查找操作栈和线性表一样只能通过全局遍历的方式进行也就是需要 O(n) 的时间复杂度。 队列
队列 先进先出平行线–特殊的线性表——队列的增和删的操作只能分别在这个队列的队尾和队头进行——对处理顺序敏感的前提
一个队列都依赖队头front和队尾rear两个指针进行唯一确定
当队列为空时front 和 rear 都指向头结点
循环队列解决数组越界的问题
链式队列进行删除数据操作时实际删除的是头结点的后继结点。这是因为头结点仅仅用来标识队列并不存储数据
为了防止删除最后一个有效数据结点后 front 指针和 rear 指针变成野指针导致队列没有意义
在可以确定队列长度最大值时建议使用循环队列。无法确定队列长度时应考虑使用链式队列
数组
数组 : 增删困难、查找容易的特点
增加若插入数据在最后则时间复杂度为 O(1)如果中间某处插入数据则时间复杂度为 O(n)。 删除对应位置的删除扫描全数组时间复杂度为 O(n)。 查找如果只需根据索引值进行一次查找时间复杂度是 O(1)。但是要在数组中查找一个数值满足指定条件的数据则时间复杂度是 O(n)
数组更适合在数据数量确定即较少使用新增数据、删除数据操作的场景下使用 在数据对位置敏感的场景下比如需要高频根据索引位置查找数据时数组就是个很好的选择
数组适合多读、插入删除少的场景。
比较 链表的长度是可变的数组的长度是固定的
链表优势是增删劣势是查但是增删必须先查 数组优势是查劣势是增删
如果数据的元素个数不确定且需要经常进行数据的新增和删除时——链表 如果数据元素大小确定删除插入的操作并不多根据索引位置查找数据——数组
数组的基本操作读取O(1)、更新O(1)、插入O(n)、删除O(n)、扩容O(n)
树
增删操作的时间复杂度都是 O(1)。 对于查找操作如果是普通二叉树则查找的时间复杂度和遍历一样都是 O(n)。 如果是二叉查找树则可以在 O(logn) 的时间复杂度内完成查找动作。 树结构在存在“一对多”的数据关系中可被高频使用这也是它区别于链表系列数据结构的关键点。
哈希表
哈希表的基本操作写入O(1)、读取O(1)、扩容O(n) 通过哈希函数我们可以把字符串或其他类型的key转化成数组的下标index
python中的数据结构
list list对应数据结构的线性表列表长度在初始状态时无需指定当插入元素超过初始长度后再启动动态扩容删除时尤其位于列表开始处元素时间复杂度为O(n) Python的list当做栈用完全没有问题push 和 pop 操作的时间复杂度都为 O(1)–增删 插入元素的时间复杂为O(n)所以凡是涉及频繁插入删除元素的操作都不太适合用list. list 使用在需要查询、修改的场景极不擅长需要频繁插入、删除元素的场景。
tuple
元组是一类不允许添加删除元素的特殊列表也就是一旦创建后续决不允许增加、删除、修改
如果非常确定你的对象后面不会被修改则可以大胆使用元组。相比于list, tuple实例更加节省内存这点尤其重要
set
去重如果想缓存某些元素值且要求元素值不能重复时适合选用此结构。并且set内允许增删元素且效率很高。 set在内部将值哈希为索引然后按照索引去获取数据因此删除、增加、查询元素效果都很高
dict
dict字典尤其适合在查询多的场景时间复杂度为O(1). 字典是一种哈希表同时保存了键值对 如leetcode第一题求解两数之和时就会使用到dict的O(1)查询时间复杂度 dict占用字节数是list、tuple的3、4倍因此对内存要求苛刻的场景要慎重考虑
deque
deque 双端队列基于list优化了列表两端的增删数据操作 from collections import deque d deque([3,2,4,0]) d.popleft() # 左侧移除元素O(1)时间复杂度 d.appendleft(3) # 左侧添加元素O(1)时间复杂度
Counter
Counter一种继承于dict用于统计元素个数的数据结构也称为bag 或 multiset. 基本用法 from collections import Counter c Counter([1,3,2,3,4,2,2]) # 统计每个元素的出现次数 In [17]: c Out[17]: Counter({1: 1, 3: 2, 2: 3, 4: 1})
heapq
heapq基于list优化的一个数据结构堆队列也称为优先队列。堆队列特点在于最小的元素总是在根结点heap[0]
heapq.heapify(a) # 对a建堆建堆后完成对a的就地排序 a[0] # a[0]一定是最小元素 heapq.nlargest(3,a) # a的前3个最大元素
