链表 LinkedList
JDK中有标准库实现：
java.util.LinkedList，和java.util.List对比，其实两者都可以看做是动态数组
链表的特征
- 线性数据结构——链表
- 是真正的动态数据结构：数据存储在节点(Node)中,是真正的动态，因为不需要处理固定容量的问题
- 是最简单的动态数据结构
- 更深入的理解引用(或指针)
- 更深入的理解递归
- 辅助组成其他数据结构(图、树、hash).
数组和链表的对比
参考博客：https://blog.csdn.net/qq_40550973/article/details/80598360
| 对比 | 优点 | 缺点 |
|---|---|---|
| 数组 | 支持用下标快速查询 | 需要额外维护扩缩容，不是真正地动态 |
| 链表 | 动态，不需要自己维护扩缩容 | 不适合用于索引有语义的情况，即没办法用下标访问 |
LinkedList优缺点
优点：
- 1.有序
- 2.可以向前面和向后添加
- 3.中间插入也很方便
- 4.可以用实现简单队列模式（
removeFirst()处理队列中的任务，add()向队列中排队）
缺点：
- 1.消耗内存有点大
- 2.定位删除和定位查找 都是比较慢
- 3.检索能力差
LinkedList的API
参考博客 https://www.cnblogs.com/ysocean/p/8657850.html 和 和第2章的
java.util.List对比很相似
- 1、添加元素
- ①、addFirst(E e)
- ②、addLast(E e)和add(E e)
- ③、add(int index, E element)
- ④、addAll(Collection c)
- 2、删除元素
- ①、remove()和removeFirst()
- ②、removeLast()
- ③、remove(int index)
- ④、remove(Object o)
- 3、修改元素
set(int index, E element)
- 4、查找元素
- ①、getFirst()
- ②、getLast()
- ③、get(int index)
- ④、indexOf(Object o)
- 5、遍历集合
- ①、普通 for 循环
- ②、迭代器
- 9、迭代器和for循环效率差异