前言：集合前面已经悄悄的讲了一点，泛型也已经引入了，当我看到这个标题的时候，有点震惊。因为一时间不知道作者会讲什么。直到扫到 『数据结构』四个大字后恍然大悟，原来这一章会结合集合，来讲数据结构（正常人初学java会学到数据结构【当然先学过C是有可能碰过数据结构】？应该是学完了java 基础 才学到数据结构吧），这一章给我的感觉是，不太适合初学者。为了方便初学者阅读，我会尽量进行扩展，以保证未学过数据结构的读者也能看懂。如果还是看不懂的，可以使用蓝色标签继续查其他文章进行进一步了解。
13.1 集合接口
13.1.1 将集合的接口和实现分离
在讲这一部分之前，先补充一下基本的数据结构相关的概念：
链表：
每个元素存在指向下一个元素的指针（引用）比如进行景点 a,b,c,d 打卡，最终要去景点 d，那我们可以通过 a->b->c->d 的路线去到 d，如果在a/b/c三个节点各派一个人指引下一个位置，最终也可以到达 d.
优点：插入删除快,a->b->c->d
插入：插入一个e在b/c之间，可以直接断开bc间的链接，让新的节点 e 指向 c， b 指向 e. a->b->e->c->d
删除：删除 c，将删除元素的下一个节点设置为空，将 b 的指针指向 d 即可， a->b->d
缺点：不能随机访问，要一步步按链的方向查，查找慢
双向链表：
每个链表元素有指向下一个元素的指针，也有指向上一个元素的指针
顺序表：
使用连续的内存进行元素保存，比如数组。
优点：查找快，可以进行随机访问
缺点：插入删除慢
插入：插入e，后续元素（红色）都需要向后移动一个位置
删除：删除e, 后续元素（红色）都需要向前移动一个位置
循环数组：
最后一个元素的下一个元素当做是第一个元素，比如: [0,1,2]，最后的 2 下一个元素是第一个元素 0
队列：
类似于斜着的管道中的流水。水在高的一侧进入，低的一侧流出，先进入的水先流出，所以常用先入先出（FIFO）来形容队列。可以用链表实现，也可以用顺序表实现。常用队头表示即将流出的一端，队尾表示刚刚进入的一端。
一共三种功能：
（1）添加元素（队尾）
（2）取出元素并删除（队头）
（3）取出元素不删除（队头）
顺序表参考类：ArrayDeque
链表参考类：LinkedList
集合类的多态(太短了，就不打代码了)：
左侧是父类类型，右侧是子类类型。这样做的好处是，如果发现插入删除比较多，可以改用 LinkedList; 发现查找次数比较多，可以改用 ArrayDeque
总结：
- 队列可以用顺序表实现，也可以用链表实现
- 多态可以左侧使用父类型，右侧使用子类型，以便于在使用使用时进行切换。
相关内容：选择 《Java核心技术 卷1》查找相关笔记
评论