【ArrayList与LinkedList专题】16、连环炮，看看你能接住多少招？
本问题对应的项目链接：高频题回答模版训练
说明：这两个一般问的比较简单，并且也没有多少东西可以问的，大家简单了解一下它们的底层 + 使用场景就行。
1、请你说一说 ArrayList 和 LinkedList 区别？
2、如果我要删除第 k 个元素，也就是会执行 remove(k)，那么这个 remove 的操作，它们的时间复杂度各自是多少？
3、可以说一说它们的使用场景吗？或者说一说你平时在处理什么事情的时候，用过它们？
4、AarrayList 底层实现是数组，数组就会有容量限制，可以简单说一下 ArrayList 的扩容机制吗？（）
请在下面打卡你的回答
shuaidi
共以下 9 个回答
1、请你说一说 ArrayList 和 LinkedList 区别？
arraylist是有序的可重复，支持索引，LinkedList 双向链表增删效率较高，通过链表追加，改查效率较低。两者都是线程不安全。
2、如果我要删除第 k 个元素，也就是会执行 remove(k)，那么这个 remove 的操作，它们的时间复杂度各自是多少？
都是O（n）
3、可以说一说它们的使用场景吗？或者说一说你平时在处理什么事情的时候，用过它们？
arraylist存放帖子列表
4、AarrayList 底层实现是数组，数组就会有容量限制，可以简单说一下 ArrayList 的扩容机制吗？
当使用无参构造器时，执行list.add，先判断是否需要扩容，第一次扩容为10，每次添加一个元素都有modcount++记录集合修改次数，当数组容量不够的时候会调用grow扩容，按照1.5倍扩容后使用array.copyof方法替换。
1、请你说一说 ArrayList 和 LinkedList 区别？
ArrayList和LinkedList都是存储有序可重复数据的数据结构，ArrayList底层是通过数组实现的，LinkedList底层是通过链表实现的。数组的修改和查询数据时可以使用索引所以时间复杂度是O（1），但是增加和删除操作时需要挪动数据保证数据的紧凑所以时间复杂度为O（n）。LinkedList修改和查询数据需要从头节点遍历链表，时间复杂度是O（n），但是因为链表是不连续存储的，所以在增加和删除时只需要修改引用关系，时间复杂度为O（1）。
2、如果我要删除第 k 个元素，也就是会执行 remove(k)，那么这个 remove 的操作，它们的时间复杂度各自是多少？
都是O（n）
ArrayList通过索引定位到当前数据的位置需要O（1），之后移动后面的数据对数据进行删除需要O（n）
LinkedList首先遍历链表到第k- 1个元素需要O（n），再通过修改引用来删除数据需要O（1）
3、可以说一说它们的使用场景吗？或者说一说你平时在处理什么事情的时候，用过它们？
在存储一系列重复数据时，同时希望存放和取出的顺序一致的时候，可以使用List，比如存放帖子列表，为了保证帖子的顺序就可以使用ArrayList存储。
4、AarrayList 底层实现是数组，数组就会有容量限制，可以简单说一下 ArrayList 的扩容机制吗？（）
ArrayList在每次调用add方法添加数据时都会调用ensureCapacityInternal来确保需要的容量小于实际的容量，如果大于，就会调用grow方法进行扩容，每次扩容是原来数组大小的1.5倍，最大值为Integr.MAX_VALUE – 8 防止一些虚拟机在数组中存放一些头信息，导致内存溢出。
Array list和linked list都是单值集合类型，他们都支持排序和动态扩容这种类似的操作，的主要区别在于他们的底层实现的数据结构不同。Array list基于数组实现而linked list基于双向链表实现。这就会导致他们增加或删除元素和查找元素有一定的差异.对于添加或删除元素来说，如果说都是在尾部进行添加或删除的话，他们的时间复杂度都是o1,但是进行随机添加删除的话，数组他在进行删除的时候，他需要把目标位置的后续元素都往后移一位,所以说他的时间复杂度是On,但是链表如果说已经找到了目标元素的话，它只需要修改前后的指针就行了，它的时间复杂度是o1,但是找到目标元素这个过程时间复杂度是on，所以说总体来看的话，它的时间复杂度也是o(n).但是对于查询来说，根据下标来查询的话，array list它能够一下子就定位到下标找到位置查找的时间复杂度是o1,而linked list即便知道下标，由于数据结构的关系，它的内存并不连续，不能够通过计算内存地址的方式直接进行访问，它也会进行一个一个的遍历，所以说他的查找时间复杂度是o(n)。
2 其实删除元素来说的话，他们的时间复杂度都是on，但是整体的时间消耗过程却是不一样的。Array list他on的消耗主要是因为他需要把k位置后面的元素都往后挪一位。而linked list它需要on的时间复杂度的原因是因为找到删除位置只能通过遍历的方式找到，删除操作仅仅需要改变前后指针而已。
3 通常在查询操作较多而改动较少的时候，我比较倾向于使用arraylist。在一些对他的添加删除操作比较多的时候，我倾向于使用link list，就比如说通常会把link list当做队列或者说是栈再来进行使用。
4 Array list，如果说在进行初始化的时候，你不指定它的初始容量，它就是默认为10，如果说付了初始容量的话，他可以你的初始容量为准。在进行动态扩容的时候，它是按照1.5倍的大小进行扩容的，当然也有特殊的情况，他并不会按照1.5倍进行扩容，当我们执行addall方法的时候，他会先判断一下1.5倍扩容之后能不能容纳下这么多的元素，如果说不够的话，那么他就会按照你真实需要的容量来进行扩容。
1、请你说一说 ArrayList 和 LinkedList 区别？
– 是否保证线性安全：ArrayList和LinkedList都是不同步的，也不保证线性安全；
– 底层数据接口：ArrayList底层使用的是Object数组；LinkedList的底层使用的双向链表数据结构；
– 插入和删除是否受元素位置的影响
– ArrayList采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。若默认在将指定的元素追加到此列表的末尾，时间复杂度为O(1)——add(E e) 方法；若要在指定位置i插入或删除元素，时间复杂度为O(n)；
– LinkedList采用链表存储，所以头尾插入或者删除元素不受元素位置的影响，时间复杂度为O(1)；要在指定位置i插入和删除元素的话，时间复杂度为O(n)；
– 是否支持随机快速访问 ：LinkedList不支持高效的随机元素访问，而ArrayList支持。
– 内存空间占用：ArrayList的空间浪费主要体现在list列表的结尾会预留一定的容量空间，而LinkedList的空间浪费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放前继指针和后继指针）
如上：
2、如果我要删除第 k 个元素，也就是会执行 remove(k)，那么这个 remove 的操作，它们的时间复杂度各自是多少？
3、可以说一说它们的使用场景吗？或者说一说你平时在处理什么事情的时候，用过它们？
帖子列表，返回前端参数
4、AarrayList 底层实现是数组，数组就会有容量限制，可以简单说一下 ArrayList 的扩容机制吗？（）
1. ArrayList中维护了一个Object类型的数组elementData，transient Object[] elementData
2. 当创建ArrayList对象时，若使用的是无参构造器，则初始化elementData的容量为0，第一次添加，则扩容elementData为10；如需要再次扩容，
则扩容elementData为1.5倍；
3. 如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍；
1.它们两个都可以放指定类型的对象，ArrayList是基于数组实现的集合，它的查询速率很快，但是插入和删除元素的时候，需要移动其它的元素，适合读多写少的场景，可以用来替代数组；LinkedList是基于双向链表的集合，插入删除元素，直接找到对应的位置插入，或者对应的元素删除就行，不会影响到其它元素，适合增加删除操作多的场景。
2.两个的时间复杂度都是o(n)，但是ArrayList还需要移动其它元素
3.ArrayList适合读多写少的场景；LinkedList适合增加删除操作多的场景。APS系统中，用ArrayList来放增量物料的信息，再调用insertBatchSomeColumn方法实现批量插入，因为只需要插入部分属性，有些属性是APS不需要的，所以不能用saveBatch方法
4.初始化的时候长度为0，第一次插入元素，默认长度是10，每次扩容是当前长度的1.5倍。扩容的时候会创建一个长度为1.5倍的数组，把旧数组的元素复制到新数组里面，删掉旧数组
1.ArrayList底层是数组，LinkedList底层是双向链表；
2.对应ArrayList来说，删除第k个元素就是把0~k – 1 和 k + 1 ~ n的元素复制到新数组，时间复杂度O(n)。对于LinkedList来说，需要遍历到第k个元素，再把指针改变，需要O(k)；
3.ArrayList按索引随机查找快，LinkList插入和删除快；
4.初始大小为0，在第一次插入后扩容为10，每次填满后扩容为原来的1.5倍，第一次扩容的大小可以修改，默认为10；
1、请你说一说 ArrayList 和 LinkedList 区别？
ArrayList 底层是用数组实现的，根据索引访问元素，使得查询的复杂度仅为 $O(1)$。但在插入和删除时有数组的复制和移动，复杂度为 $O(n)$；
LinkedList 底层使用双向链表实现的，由于每个节点都含有前驱和后继节点的引用，所以它插入删除时只需修改这些引用，效率要比 ArrayList 高 。但在查询元素时需要从头节点开始依次遍历整个链表，时间复杂度为 $O(n)$
2、如果我要删除第 k 个元素，也就是会执行 remove(k)，那么这个 remove 的操作，它们的时间复杂度各自是多少？
都是 $O(n)$ 。
ArrayList 首先会以 $O(1)$ 时间定位到第 k 个元素，然后将被这个元素分割的两部分复制拼接到一个新数组上，总体为 $O(n)$ 。
LinkedList 首先以 $O(n)$ 时间定位到第 k 个元素，然后 $O(1)$ 时间处理这个元素前后节点的引用，总体也为 $O(n)$ 。
3、可以说一说它们的使用场景吗？或者说一说你平时在处理什么事情的时候，用过它们？
(待补充)
4、AarrayList 底层实现是数组，数组就会有容量限制，可以简单说一下 ArrayList 的扩容机制吗？
ArrayList 的默认容量为 10，当需要扩容时，会先申请一个容量为旧容量 1.5 倍的新数组，然后把旧数组复制到新数组中。值得注意的是，JDK 1.8 中 ArrayList 底层数组的最大容量为 Integer.MAX_VALUE – 8 ，目的是防止某些虚拟机会在数组中存一些额外的信息导致内存溢出。
1、请你说一说 ArrayList 和 LinkedList 区别？
前者基于数组，后者基于链表（双向链表）;
数据量少的话增删操作多最好用LinkedList ，查询多的话最好用ArrayList;
LinkedList 的增删未必就是比 ArrayList 要快：由于 LinkedList 的消耗主要是在遍历上，ArrayList 的消耗主要是在移动和复制上（底层调用的是 arraycopy() 方法，是 native 方法），在百万级数据量情况下，当增删的位置在后半部分，那么 LinkedList 要遍历的数据多，ArrayList要移动的数据少，故ArrayList要快;
2、如果我要删除第 k 个元素，也就是会执行 remove(k)，那么这个 remove 的操作，它们的时间复杂度各自是多少？
两个都是O（n）但是ArrayList是通过调用底层的本地方法复制数组实现插入的。而linkedList只需要查找到位置然后删除。
3、可以说一说它们的使用场景吗？或者说一说你平时在处理什么事情的时候，用过它们？
ArrayList常用来代替数组，LinkedList常用来代替栈，队列；
处理事情具体看项目细节了；
4、ArrayList 底层实现是数组，数组就会有容量限制，可以简单说一下 ArrayList 的扩容机制吗？
1 ArrayList和linkedList区别在于一个是数组实现，一个是双向链表实现。
2 一个O（n）一个O（k），ArrayList是通过调用底层的本地方法复制数组实现插入的。而linkedList只需要查找到位置然后删除。
3 ArrayList我常用来代替数组，因为ArrayList可操作的方法比较多。比如我在支付项目中，获取某个用户的购物车内容时，有很多项目，并且需要使用到一些操作，所以我用ArrayList接收； LinkedList用于大量只需要头部插入即可的业务。
4 首次扩容会从0扩容成10，查过再次扩容会扩容到上一次容量的1.5倍。插入时超过数组大小时会扩容。