数据结构的存储方式

数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）。

数组 : 紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。由于是连续存储内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)

链表 : 元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题。如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

总结
数组
优点: 构建简单，根据下标（indedx）查询某个元素的时间复杂度 O(1)
缺点: 必须连续空间，查询元素是否存在要遍历整个数组 O(n), 删除和添加某个元素 O(n)

链表
优点: 灵活分配内存空间，删除，添加元素 O(1) (单链表：前提是前一个元素已知) (双链表：前提是前/后一个元素已知)
缺点: 读取元素要从链表头开始一个一个读取，查询第K 个元素 O(k)

应用场景

需要很多快速查询 : 数组
数据元素个数不确定, 需要经常添加删除 : 链表
数据元素确定，删除插入操作不多 : 数组

python 中的基本数据结构

str 是一种序列，类似于 tuple

list 和 tuple 两种类型采用了顺序表的实现技术

tuple 是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与 list 的性质类似。

list 是一种采用分离式技术实现的动态顺序表,建立空表（或者很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大（目前的阀值为50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出现过多空闲的存储位置。

dict 和 set 都是通过 hash table 来实现的键值对数据结构, 实现上 set 是带空值相同的 dict。

特点

dict 中的数据是无序存放的
操作的时间复杂度，插入、查找和删除都可以在O(1)的时间复杂度
键的限制，只有可 hash 的对象才能成为 dict 的 key 和 set 的 value。可 hash 的对象即 python中的不可变对象和自定义的对象。可变对象(lits ,set , dict )是不能作为字典的键和st的值的。
dict的内存花销大但是查询速度快。自定义的对象，或者python内部的对象都是dict包装的。（hash简单的来说即映射，映射之后，不可能是连续的存在内存空间中的，总有一些内存时空的，当发现内存空间中的”空” 不足时，便会触发扩容操作，以免引起hash冲突）

补充
数组的特点是：寻址容易，插入和删除困难；

而链表的特点是：寻址困难，插入和删除容易。

Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。hash就是找到一种数据内容和数据存放地址之间的映射关系。基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）

一个对象的哈希值如果在其生命周期内绝不改变，就被称为可哈希（它需要具有 __hash__() 方法），并可以同其他对象进行比较（它需要具有 __eq__()方法）。可哈希对象必须具有相同的哈希值比较结果才会相同。

可哈希性使得对象能够作为字典键或集合成员使用，因为这些数据结构要在内部使用哈希值。