1. ArrayList
内部 基于对数组 结构实现
- 查询快:index->value一步到位; value->index逐个比较
- 修改快:index->value一步到位;
- 增加慢:(因为内部默认保持顺序)增加到index=0位置,移位length()-1次,保存1次。增加到最后位置操作1次。超出数组长度,自动默认扩容1.5倍。扩容要新建数组,复制数据。再进行添加操作。
- 删除慢:删除index=0数据,(因为内部默认保持顺序)移位length()-1次,最后一位—— 置null。删除最后一位,直接置null。
2. 链表结构LinkedList
内部基于 双向链表 结构实现
- 查询慢:逐个比较,平均操作(N+1)/2次。
- 修改慢:找到节点,平均操作(N+1)/2次,再修改1次,。
- 增加快:表头或者表尾添加操作1次。中间添加平均操作(N+1)/2次。
- 删除快:表头或者表尾添加操作1次。中间添加平均操作(N+1)/2次。
3. 队列
这是一种特殊结构,针对特殊需求
- 单向队列(Queue):先进先出(FIFO),只能从队列尾插入数据,只能从队列头删除数据.
image.png
- 双向队列(Deque):可以从队列尾/头插入数据,只能从队列头/尾删除数据.
3. 栈stack
这是一种特殊结构,针对特殊需求
仅允许在表的一端进行插入和删除,这一端被称为栈顶,另一端称为栈底。
- 后进先出,先进后出。
4. 哈希表
使用哈希编码,将索引与值之间的对应关系唯一性地表达。
即是:
每个对象的哈希码是不同的,它是唯一的。
因为根据这个hash码能直接找到index和value。
所以无论查询、修改、插入、删除,哈希表的性能是超群的。
- 性能超群。
- 元素不能重复。数组:元素能重复。
- 不记录添加顺序。数组:能记录添加顺序。
- 扩容性能变差,容量默认16.
- 加载因子0.75
网友评论