ArrayList源码分析、扩容机制面试题，数组和List的相互转换，ArrayList与Li ...

目录
1.java聚集框架体系
2. 前置知识-数组
2.1 数组
2.1.1 定义：
2.1.2 数组如何获取其他元素的地址值？（寻址公式）
2.1.3 为什么数组索引从0开始呢？从1开始不可吗？
3. ArrayList
3.1 ArrayList和和Vector的区别？（了解）
3.2 ArrayList 可以添加 null 值吗？
3.3 ArrayList源码
成员变量
​编辑构造方法
3.4 ArrayList 底层实现原理 ★
3.5 ArrayList list = new ArrayList(10)中的list扩容几次？★
3.6 数组和List之间相互转换？★
3.7 数组和List之间相互转换过程中，数据发生修改，结果会变吗（有影响吗）？★
3.7.1  用Arrays.asList() 转List后，如修改了数组内容，list聚集结果受影响吗？
3.7.2 List用toArray() 转数组后，如果修改了List内容，数组受影响吗？
4. 前置知识-链表
4.1单向链表
4.1.1 单向链表特点及参考源码
4.1.2 单向链表时间复杂度分析
1 查询操纵
2 插入和删除操纵
4.2 双向链表
4.2.1 双向链表特点及参考源码
4.2.2 双向链表时间复杂度分析
1. 查询操纵
2 增删操纵
5. LinkedList
6. ArrayList与LinkedList区别？★

---

1.java聚集框架体系

2. 前置知识-数组

2.1 数组

2.1.1 定义：

数组（Array）是一种用连续的内存空间存储雷同数据类型数据的线性数据布局。

1. int[] array = {22,33,88,66,55,25};

复制代码

2.1.2 数组如何获取其他元素的地址值？（寻址公式）

   在数组在内存中查找元素的时候，是有一个寻址公式的，如下：   

1. arr[i] = baseAddress + i * dataTypeSize

复制代码

2.1.3 为什么数组索引从0开始呢？从1开始不可吗？

     实际上并不是不可。而是如果数组索引从1开始的话，团体性能会变低。
因为寻址公式会变为a = baseAddress + (i-1) *dataTypeSize，也就是说，多了一个减法操纵。
    3. ArrayList

     ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用步伐可以使用ArrayList底层API的 ensureCapacity()操纵来增长 ArrayList 实例的容量。这可以淘汰递增式再分配的数量。
      3.1 ArrayList和和Vector的区别？（了解）

     

• ArrayList 是 List 的重要实现类，底层使用 Object[]存储，实用于频仍的查找工作，线程不安全 。  
  
• Vector 是 List 的古诚实现类，底层使用Object[] 存储，线程安全。
  

    3.2 ArrayList 可以添加 null 值吗？

     可以。ArrayList 中可以存储任何类型的对象，包括 null 值。不外，不建议向ArrayList 中添加 null 值， null 值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。
    3.3 ArrayList源码

  
  成员变量

  

  
  构造方法

  

         第一个构造是带初始化容量的构造函数，可以按照指定的容量初始化数组           第二个是无参构造函数，默认创建一个空聚集           

1. /**
2. *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
3. *如果指定的集合为null，throws NullPointerException。
4. */
5. public ArrayList(Collection<? extends E> c) {
6.     elementData = c.toArray();
7.     if ((size = elementData.length) != 0) {
8.         if (elementData.getClass() != Object[].class)
9.             elementData = Arrays.copyOf(elementData, size, Object[].class);
10.     } else {
11.         // replace with empty array.
12.         this.elementData = EMPTY_ELEMENTDATA;
13.     }
14. }

复制代码

               将     collection     对象转换成数组，然后将数组的地址的赋给     elementData           3.4 ArrayList 底层实现原理 ★

  

  1. 底层数据布局
         ArrayList    底层是用动态的数组实现的          2. 初始容量
         ArrayList    初始容量为    0    ，当第一次添加数据的时候才会初始化容量为    10        3. 扩容逻辑
         ArrayList    在进行扩容的时候是原来容量的    1.5    倍，每次扩容都需要拷贝数组        4. 添加逻辑
  添加数据的流程：
  

         1. 确保数组已使用长度（    size    ）加    1    之后充足存下下一个数据           2. 计算数组的容量，如果当前数组已使用长度    +1    后的大于当前的数组长度，           3. 则调用    grow    方法扩容（原来的    1.5    倍）           4. 确保新增的数据有地方存储之后，则将新元素添加到位于    size    的位置上。           5. 返回添加成功布尔值。       3.5 ArrayList list = new ArrayList(10)中的list扩容几次？★

      答：该语句只是声明和实例了一个    ArrayList   ，指定了容量为    10   ，未扩容      ArrayList的扩容机制如下：
  

• 当ArrayList被初始化时，如果没有指定初始容量，它将使用默认的初始容量（10）。
  
• 当添加元素超过当前容量时，ArrayList会进行扩容。默认情况下，扩容后的容量是当前容量的1.5倍（即增长50%）。
  

  3.6 数组和List之间相互转换？★

   参考回答：
  

• 数组转List ，使用JDK中java.util.Arrays工具类的asList方法，返回一个List聚集
  
• List转数组，使用List的toArray方法。无参toArray方法返回 Object数组，传入初始化长度的数组对象，返回该对象数组
  

  

3.7 数组和List之间相互转换过程中，数据发生修改，结果会变吗（有影响吗）？★

分为两种情况：
3.7.1  用Arrays.asList() 转List后，如修改了数组内容，list聚集结果受影响吗？

答：会受影响
   Arrays.asList 方法返回的是一个固定巨细的列表，它的底层仍旧是原始数组。
  当你通过 Arrays.asList 得到的列表并尝试修改其中的元素时，实际上是在修改原始数组的内容，因为列表中的元素和数组中的元素是同一个对象（同一个地址引用）。
  源码如下：

3.7.2 List用toArray() 转数组后，如果修改了List内容，数组受影响吗？

答：不会影响。
   list用了toArray转数组后，如果修改了list内容，数组不会影响，当调用了toArray  以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，以是纵然  list修改了以后，数组
  也不受影响
  4. 前置知识-链表

   LinkedList 底层数据布局——双向链表
  4.1单向链表

4.1.1 单向链表特点及参考源码

   

• 链表中的每一个元素称之为结点（Node）
  
• 物理存储单元上，非连续、非顺序的存储布局
  
• 单向链表：每个结点包括两个部分：一个是存储数据元素的数据域，另一个 是存储下一个结点地址的指针域。记录下个结点地址的指针叫作后继指针next
  

  

代码实现参考：

4.1.2 单向链表时间复杂度分析

1 查询操纵

      查询：头节点：O(1)，一般情况：O(n)      

• 只有在查询头节点的时候不需要遍历链表，时间复杂度是O(1)
  
• 查询其他结点需要遍历链表，时间复杂度是O(n)
  

  2 插入和删除操纵

   增删：头节点：O(1)，一般情况：O(n)
  

• 只有在添加和删除头节点的时候不需要遍历链表，时间复杂度是O(1)
  
• 添加或删除其他结点需要遍历链表找到对应节点后，才华完成新增或删除节点，时间复杂度是O(n)
  

  
4.2 双向链表

4.2.1 双向链表特点及参考源码

      而双向链表，顾名思义，它支持两个方向     

• 每个结点不止有一个后继指针 next 指向背面的结点
  
• 有一个前驱指针 prev 指向前面的结点
  

    代码实现参考：   

   4.2.2 双向链表时间复杂度分析

   

  
1. 查询操纵

   查询：头尾节点：O(1)，一般情况：O(n)，给定节点找前驱节点：O(1)
  

• 查询头尾结点的时间复杂度是O(1)
  
• 均匀的查询时间复杂度是O(n)
  
• 给定节点找前驱节点的时间复杂度为O(1)
  

  2 增删操纵

       增删：头尾节点：O(1)，一般情况：O(n)，给定节点找前驱节点：O(1)   

• 头尾结点增删的时间复杂度为O(1)
  
• 其他部分结点增删的时间复杂度是 O(n)
  
• 给定节点增删的时间复杂度为O(1)
  

  5. LinkedList

   LinkedList 底层数据布局——双向链表
  查询快，增删改慢，实用于读多写少的场景
  6. ArrayList与LinkedList区别？★

从四个方面来谈。
   

• 底层数据布局：ArrayList 是动态数组的数据布局实现，LinkedList 是双向链表的数据布局实现
  
• 服从上，除了 LinkedList不支持下标查询，ArrayList支持下标查询。其他都差不多。
  
• 空间上，ArrayList底层是数组，内存连续，节省内存。LinkedList 是双向链表需要存储数据，和两个指针，更占用内存。
  
• 线程安全问题，ArrayList和LinkedList都不是线程安全的。
  

    如果需要包管线程安全，有两种方案：
  

• 在方法内使用，局部变量则是线程安全的
  
• 使用线程安全的ArrayList和LinkedList：
  

1. Collections.synchronizedList(new ArrayList<>());
2. Collections.synchronizedList(new LinkedList<>());

复制代码

还有一下三个方面的区别可以了解一下：
   

• 插入和删除是否受元素位置的影响：
  
  
  
  • ArrayList 接纳数组存储，以是插入和删除元素的时间复杂度受元素位置的影响。 比如：实行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)），时间复杂度就为 O(n)。因为在进行上述操纵的时候聚集中第 i 和第 i 个元素之后的(n-i)个元素都要实行向后位/向前移一位的操纵。
    
  • LinkedList 接纳链表存储，以是在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、 removeLast()），时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o),remove(int index)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入和删除。
    
  
  
• 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList（实现了 RandomAccess 接口） 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  
• 内存空间占用： ArrayList 的空间浪费重要体现在在 list 列表的结尾会预留肯定的容量空间，而 LinkedList 的空间耗费则体现在它的每一个元素都需要斲丧比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。