List接口与ArrayList、LinkedList、Vector类

系统管理员 2022-05-16 09:49 224阅读 0赞

1.List是集合列表接口，ArrayList和LinkedList都是List接口的实现类，表示一种有序的集合，其中的元素可以重复。

2.ArrayList的动态扩容机制

当ArrayList中增加一个新的对象时，Java会检查ArrayList确保现有的数组有足够的容量来存储这个新对象，如果没有足够容量就新建一个更大长度的数组，旧的数组使用Array.copyOf方法复制到新数组中，现有的数组引用指向新的数组。

3.Array和ArrayList的区别

（1）Array可以包含基本数据类型和对象类型，ArrayList只能包含对象类型；

（2）Array的大小是固定的，ArrayList的大小是变化的；

（3）ArrayList提供了更多的方法和特性；

4.LinkedList工作原理和实现

LinkedList是以双链表实现，链表容量无限制（本身需要消耗额外的链表指针空间来操作），其内部主要成员为first和last两个node节点，在每次修改列表时用来指引双向列表的首尾位置。当我们使用下标方式调用列表的get(index)，set(index, e)方法时需要遍历链表将指针移动到位进行访问（会判断index是否大于链表长度的一般决定是首部遍历还是尾部遍历，访问的复杂度为O(N/2)），无法像ArrayList那样进行随机访问，只有在两头的操作（如add(), addFirst(), removeFirst()等）才不需要进行遍历寻找定位。

5.ArrayList和LinkedList各自适用的场景和原因

ArrayList是动态数组顺序表，顺序表的存储地址是连续的，所以查找比较快，可以根据下标进行O(1)复杂度的查找，但是插入和删除由于需要对其他元素进进行移动，所以比较费时，效率较低，所以ArrayList适合查询操作，不适合增删操作；

LinkedList是双向链表的数据结构，同时实现了双端队列Deque接口，链表节点的存储地址是不连续的，每个存储地址通过指针关联，在查找时需要遍历指针遍历节点，所以查找速度慢，但是插入和删除时比较快，只需要修改指针指向即可。

6.Vector的特点

Vector是线程安全的动态数组，同ArrayList一样继承自AbstractList，内部实现依然基于数组，Vector是线程安全的，会在可能出现线程安全的方法前面加上synchronized关键字，和ArrayList相似，随机访问速度快，插入和删除的速率慢，支持null元素，有序，元素可以重复，不能存放基本数据类型的数据，加入的数据均为对象。