每日一考-9.11

ArrayList和LinkedList区别 3

简说
arraylist

1. 基于数组，需要连续内存
2. 随机访问快（指根据下标访问）
3. 尾部插入、删除性能可以，其它部分插入、删除都会移动数据，因此性能会低
4. 可以利用 cpu 缓存，局部性原理

linkedlist

1. 基于双向链表，无需连续内存
2. 随机访问慢（要沿着链表遍历）
3. 头尾插入删除性能高
4. 占用内存多

细说
由于arraylist底层是数组，所以元素必须连续存储，当要进行随机查找，其实是根据arraylist连续存储中的下标查找，这操作速度很快。

由于linkedlist底层是双向链表，所以存储是无序的，占用内存多（大约同样存储量，占用内存是arraylist的4倍左右），进行随机查找时，得一个一个查，所以访问效率低很多。

且arraylist底层实现了一个RandomAccess（随机访问接口），而linkedlist没有实现，实现这个接口就可以通过下标去找，没有实现就只有通过迭代器找

list集合去重都有哪些方法 3

1. 双重for循环

2. 利用list集合中contains方法循环遍历，清空，重新添加

3. 利用HashSet不能重复特性，但不能保证顺序，只有额外加判断条件保证顺序

4. 利用Java8特性stream流进行list去重

5. （最佳）使用LinkedHashSet删除ArrayList中的重复元素

   可以做到即删除了重复数据，又保持添加到其中的数据的顺序。

数组和链表分别适用于什么场景，为什么 3

数组：数组是将元素在内存中连续存储的；它的优点：因为数据是连续存储的，内存地址连续，所以在查找数据的时候效率比较高；它的缺点：在存储之前，我们需要申请一块连续的内存空间，并且在编译的时候就必须确定好它的空间的大小。在运行的时候空间的大小是无法随着你的需要进行增加和减少而改变的，当数据两比较大的时候，有可能会出现越界的情况，数据比较小的时候，又有可能会浪费掉内存空间。在改变数据个数时，增加、插入、删除数据效率比较低。

链表：链表是动态申请内存空间，不需要像数组需要提前申请好内存的大小，链表只需在用的时候申请就可以，根据需要来动态申请或者删除内存空间，对于数据增加和删除以及插入比数组灵活。还有就是链表中数据在内存中可以在任意的位置，通过应用来关联数据（就是通过存在元素的指针来联系）。

其实这两者最典型的实现就是arraylist和linkedlist

数组应用场景：数据比较少；经常做的运算是按序号访问数据元素；数组更容易实现，任何高级语言都支持；构建的线性表较稳定。

链表应用场景：对线性表的长度或者规模难以估计；频繁做插入删除操作；构建动态性比较强的线性表。