1. ArrayList

---

内部 基于对数组 结构实现

• 查询快：index->value一步到位; value->index逐个比较
• 修改快：index->value一步到位;
• 增加慢：（因为内部默认保持顺序）增加到index=0位置,移位length()-1次，保存1次。增加到最后位置操作1次。超出数组长度，自动默认扩容1.5倍。扩容要新建数组，复制数据。再进行添加操作。
• 删除慢：删除index=0数据，（因为内部默认保持顺序）移位length()-1次,最后一位—— 置null。删除最后一位，直接置null。

image.png

2. 链表结构LinkedList

---

内部基于 双向链表 结构实现

• 查询慢：逐个比较，平均操作(N+1)/2次。
• 修改慢：找到节点，平均操作(N+1)/2次，再修改1次，。
• 增加快：表头或者表尾添加操作1次。中间添加平均操作(N+1)/2次。
• 删除快：表头或者表尾添加操作1次。中间添加平均操作(N+1)/2次。

image.png

3. 队列

---

这是一种特殊结构，针对特殊需求

• 单向队列(Queue):先进先出(FIFO),只能从队列尾插入数据,只能从队列头删除数据.

• 双向队列(Deque):可以从队列尾/头插入数据,只能从队列头/尾删除数据.

image.png

3. 栈stack

---

这是一种特殊结构，针对特殊需求

仅允许在表的一端进行插入和删除，这一端被称为栈顶，另一端称为栈底。

• 后进先出，先进后出。

image.png

4. 哈希表

---

使用哈希编码，将索引与值之间的对应关系唯一性地表达。
即是:
每个对象的哈希码是不同的，它是唯一的。
因为根据这个hash码能直接找到index和value。
所以无论查询、修改、插入、删除，哈希表的性能是超群的。

• 性能超群。
• 元素不能重复。数组：元素能重复。
• 不记录添加顺序。数组：能记录添加顺序。
• 扩容性能变差，容量默认16.
• 加载因子0.75

image.png