数据结构
把多个数据按照一定的存储方式,存储起来,这种存储方式称之为数据结构.
数据的存储方式有很多,数组,队列,链表,栈,哈希表等等.
不同的数据结构,性能是不一样的,比如有的查询比较快,但是增加和删除比较慢；有的增加和删除比较快,但是查询比较慢.
实际开发中如何选择,要看你的需求,是查比较多还是增删比较多,根据你的需求选择合适的即可
1.数组结构
数组是最简单的数据结构，就是用来存储多个相同类型数据的容器
面向对象
一般的,操作数组比较麻烦,但是如String类,提供了很多方法,把操作数组的算法给封装起来,
咱们就直接调用某方法即可完成相同的功能.
性能分析:
增加(Create)、读取(Retrieve)、更新(Update)和删除(Delete) CRUD
-
增加：
扩容:性能不好,需要复制数组,扩容次数越多性能越低 不扩容:性能高,只需要操作1次,效率极高 小结:性能不错,效率还是比较高的 -
读取：
索引查询:操作1次,效率极高 元素查询:元素查询使用的是线性查找,可能是1次找到,也有可能是多次找到,性能一般 小结:性能不错,效率还是比较高的 -
更新：
通过索引:操作1次,效率极高 小结:性能不错,效率极高 -
删除：
删除是带有补位的,分情况:删除第一个,性能低,删除最后一个性能高 小结:性能一般,但是出现删除频繁的需求,不应该选择这个数据结构, 一般要删除的内容处于后一半的概率是不高的,不适合删除操作
总结:
擅长做增(不扩容)/查/改
2.链表结构
结构跟火车类似
-
单向链表
从头开始访问,只能访问到相邻的下一元素,不能回头
class Node{ Object item; Node next; } -
双向链表
从头或者尾部开始访问元素,只能访问相邻的元素,可以来回访问
class Node{ Object item; Node next; Node prov; }
链表结构的性能分析:
-
C
增加在头或者尾:一次搞定,操作2个节点,非常快,性能极高 增加在中间:必须从头或者尾开始检索,找到了元素后才能进行增加操作,需要操作3个节点,效率不高 -
R
读取在头或者尾:一次找到,效率极高 读取在中间:必须从头或者尾开始检索,效率不高 -
U
更新在头或者尾:一次找到,直接操作,效率极高 更新在中间:必须从头或者尾开始检索,找到后才能进行修改,效率不高 -
D
删除在头或者尾:一次搞定,操作2个节点,直接操作,效率极高 删除在中间:必须从头或者尾开始检索,找到后才能进行删除,操作3个的节点,效率不高
总结:
擅长**首尾元素**的CRUD操作
3.队列结构
-
Queue：
单向队列，先进先出。
增加时只能加入到末尾，删除时只能从头开始删除
-
Deque：
双向队列，既可以先进先出，又可以先进后出
增加时既能加入到首位也能加入到末尾，删除时既能删除首位也能删除末尾
总结:
擅长频繁的**首尾元素**增删操作
4.栈结构
先进后出,例如手枪的弹夹
压栈：push 压到栈顶
弹栈：pop 删除栈顶元素,并返回栈顶元素
查看：peek 查看栈顶元素