赞
踩
1.ArrayList的缺陷
1.ArrayList底层使用数组来存储元素,由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。
2.链表
2.1 链表的概念及结构
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
链表的种类:1.单向或者双向链表
2.带头或者不带头节点
3. 循环或者非循环
面试重点:单向不带头链表和双向不带头循环链表
2.2 LinkedList链表
LinkedList的底层是双向链表结构(链表后面介绍),由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。
在集合框架中,LinkedList实现了List接口。
1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口,因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)
2.2.1 LinkedList的使用
- public static void main(String[] args) {
- // 构造一个空的LinkedList
- List<Integer> list1 = new LinkedList<>();
- List<String> list2 = new java.util.ArrayList<>();
- list2.add("JavaSE");
- list2.add("JavaWeb");
- list2.add("JavaEE");
- // 使用ArrayList构造LinkedList
- List<String> list3 = new LinkedList<>(list2);
- }
3.ArrayList和LinkedList的区别(从共性出发看)
不同点 | ArrayList(底层为数组) | LinkedList |
存储空间上 | 物理上一定连续 | 逻辑上连续,物理上分配的空间可能不连续 |
随机访问其中元素(时间复杂度) | 支持O(1) | 不支持:O(N) |
头部插入元素 | 需要挪移元素,效率低O(N) | 只需修改引用的指向,时间复杂度为O(1) |
插入元素 | 空间不够时需要扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。