数组和链表

区别(优缺点)

分点总结

       1、存储,访问方式

????①数组中的元素是连续存储的，可根据索引随机访问元素。

????②链表中的元素不连续，是靠指针指向下一个元素的位置，只能顺序遍历访问，不能随机访问。

??2、结构大小

????①数组大小固定，不可动态改变

????②链表大小可动态变化

??3、增删查

????①数组查询速度快（下标），增删速度慢（需要移动大量元素）

????②链表增删速度快（修改引用），查询速度慢（需要顺序遍历）

?   4、时间复杂度

             ①数组，查询的时间复杂度是O(1)，插入和删除时间复杂度是O(n)，因为最好是O(1)，最差是O(n)，所以平均时间复杂度是O(n)/2，既时间复杂度是O(n)。

             ②链表，查询的时间复杂度是O(n)，插入和删除的时间复杂度是O(1)。

面试回答

（1）数组中的元素是连续存储的，可根据索引随机访问元素，所以数组查询速度快，查询的时间复杂度是O(1)。单正是因为连续存储，所以插入和删除元素慢，因为得移动后面的所有数据以保持连续性，时间复杂度是O(n)（因为最好是O(1)，最差是O(n)，所以平均时间复杂度是O(n)/2，既时间复杂度是O(n)）。

（2）链表中的元素不连续，是靠指针指向下一个元素的位置，只能顺序遍历访问，所以数组查询速度慢，查询的时间复杂度是O(n)。正式是不连续的，操作指针即可插入和删除元素，所以插入和删除元素快，时间复杂度是O(1)。

常见面试题

ArrayList 和 LinkedList 的区别

1.ArrayList是实现了基于动态数组的数据结构，LinkedList是实现了基于链表的数据结构。

2.对于添加、删除元素，LinedList比较占优势，因为ArrayList要移动数据。

3.对于遍历和查找元素，ArrayList比较快，因为LinkedList要移动指针。

ArrayList和Vector的区别

首先，这两个类都实现了List接口（List接口继承了Collection接口），是有序集合，相当于一种动态的数组，能够通过索引(元素在List中位置，类似于数组的下标)来访问元素，并且其中的数据是允许重复的。

区别主要包括两个部分:

（1）同步性：

Vector是线程安全的,而ArrayList是非线程安全的，所以如果不是要求线程安全的情况下，最好使用ArrayList，效率会高些。

（2）数据增长：

ArrayList与Vector都有一个初始的容量大小，当存储超过了容量时，就需要增加ArrayList与Vector的存储空间，Vector默认增长原来的一倍，ArrayList增加原来的0.5倍。