常见面试题之List集合

朱雀 2024-03-17 19:41 120阅读 0赞

### 1. 数组 ###

#### 1.1 数组概述 ####

数组（`Array`）是一种用**连续的内存空间**存储**相同数据类型**数据的线性数据结构。

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

![在这里插入图片描述][817c23466cd543bea0fb7f208c56b9f0.png_pic_center]

我们定义了这么一个数组之后，在内存的表示是这样的：

![在这里插入图片描述][03b6f7337a404e598bcf67d182fa9eb1.png_pic_center]

现在假如，我们通过`arrar[1]`，想要获得下标为1这个元素，但是现在栈内存中指向的堆内存数组的首地址，它是如何获取下标为1这个数据的？

![在这里插入图片描述][dcb4ffb1bb59410caf79b3d8f014c20a.png_pic_center]

#### 1.2 寻址公式 ####

为了方便大家理解，我们把数组的内存地址稍微改了一下，都改成了数字，如下图：

![在这里插入图片描述][e559722209c54039bf101025cb09f75f.png_pic_center]

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

arr[i] = baseAddress + i * dataTypeSize

> `baseAddress`：数组的首地址，目前是10。
> 
> `dataTypeSize`：代表数组中元素类型的大小，目前数组重存储的是`int`型的数据，`dataTypeSize`=4个字节。
> 
> `arr`：指的是数组。
> 
> `i`：指的是数组的下标。

有了寻址公式以后，我们再来获取一下下标为1的元素，这个是原来的数组。

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

套入公式：

array[1] =10 + i * 4 = 14

获取到14这个地址，就能获取到下标为1的这个元素了。

#### 1.3 操作数组的时间复杂度 ####

**1.随机查询(根据索引查询)**

数组元素的访问是通过下标来访问的，计算机通过数组的**首地址**和**寻址公式**能够很快速的找到想要访问的元素

public int test01(int[] a,int i){
        
       return a[i];
       // a[i] = baseAddress + i \* dataSize
    }

代码的执行次数并不会随着数组的数据规模大小变化而变化，是常数级的，所以查询数据操作的时间复杂度是`O(1)`。

**2. 未知索引查询`O(n)`或`O(log2n)`**

情况一：查找数组内的元素，查找55号数据，遍历数组时间复杂度为`O(n)`。

![在这里插入图片描述][29534636e57c4f7c8974b1dcb564fcc9.png_pic_center]

情况二：查找排序后数组内的元素，通过二分查找算法查找55号数据时间复杂度为`O(logn)`。

![在这里插入图片描述][51dba58a3d8a46f699a0ac1ae4d1babd.png_pic_center]

**3.插入`O(n)`**

数组是一段连续的内存空间，因此为了保证数组的连续性会使得数组的插入和删除的效率变的很低。

假设数组的长度为`n`，现在如果我们需要将一个数据插入到数组中的第`k`个位置。为了把第`k`个位置腾出来给新来的数据，我们需要将第`k～n`这部分的元素都顺序地往后挪一位。如下图所示：

![在这里插入图片描述][c8d612847d99420983730999e56ed9d8.png_pic_center]

新增之后的数据变化，如下

![在这里插入图片描述][bfe29c21f88d4c18b242479b16f9ff8e.png_pic_center]

所以：

插入操作，最好情况下是`O(1)`的，最坏情况下是`O(n)`的，**平均情况下的时间复杂度是`O(n)`**。

**4.删除`O(n)`**

同理可得：如果我们要删除第`k`个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了，时间复杂度仍然是`O(n)`。

### 2. `ArrayList`源码分析 ###

分析`ArrayList`源码主要从三个方面去翻阅：成员变量，构造函数，关键方法。

> 以下源码都来源于`jdk 1.8`。

#### 2.1 成员变量 ####

![在这里插入图片描述][2c10eed5b09c44329baa7b923c71a549.png_pic_center]

> `DEFAULT_CAPACITY = 10;` 默认初始的容量(`CAPACITY`)。
> 
> `EMPTY_ELEMENTDATA = {};` 用于空实例的共享空数组实例。
> 
> `DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};`用于默认大小的空实例的共享空数组实例。
> 
> `Object[] elementData;` 存储元素的数组缓冲区。
> 
> `int size;` `ArrayList`的大小（它包含的元素数量）。

#### 2.2 构造方法 ####

![在这里插入图片描述][ab1f647fba7e4511aa8aa96e82333fee.png_pic_center]

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

![在这里插入图片描述][2207183059e74593ab134688ec4cfd01.png_pic_center]

> 将`collection`对象转换成数组，然后将数组的地址的赋给`elementData`。

#### 2.3 `ArrayList`源码分析 ####

添加数据的流程：

![在这里插入图片描述][c5ef50f6a27548f08aa7636d3459c0a3.png_pic_center]

**结论：**

*  底层数据结构

`ArrayList`底层是用动态的数组实现的。

*  初始容量

`ArrayList`初始容量为0，当第一次添加数据的时候才会初始化容量为10。

*  扩容逻辑

`ArrayList`在进行扩容的时候是原来容量的1.5倍，每次扩容都需要拷贝数组。

*  添加逻辑
    
     *  确保数组已使用长度（`size`）加1之后足够存下下一个数据 。
     *  计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用`grow`方法扩容（原来的1.5倍）。
     *  确保新增的数据有地方存储之后，则将新元素添加到位于`size`的位置上。
     *  返回添加成功布尔值。

#### 2.4 `ArrayList list=new ArrayList(10)`中的`list`扩容几次 ####

![在这里插入图片描述][62810f44d15141d885b5b1f58c366a60.png_pic_center]

参考回答：

该语句只是声明和实例了一个`ArrayList`，指定了容量为 10，未扩容。

#### 2.5 如何实现数组和`List`之间的转换 ####

如下代码：

![在这里插入图片描述][9f1fd2b1e7574dcd85a6712cf06f4114.png_pic_center]

参考回答：

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

面试官再问：

1，用`Arrays.asList`转`List`后，如果修改了数组内容，`list`受影响吗？

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

![在这里插入图片描述][fa708452824e4f9db054c4d1c31ef943.png_pic_center]

> 数组转`List`受影响。
> 
> `List`转数组不受影响。

再答：

1，用`Arrays.asList`转`List`后，如果修改了数组内容，`list`受影响吗？

`Arrays.asList`转换`list`之后，如果修改了数组的内容，`list`会受影响，因为它的底层使用的`Arrays`类中的一个内部类`ArrayList`来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址。

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

`list`用了`toArray`转数组后，如果修改了`list`内容，数组不会影响，当调用了`toArray`以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使`list`修改了以后，数组也不受影响。

### 3. 链表 ###

#### 3.1 单向链表 ####

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

![在这里插入图片描述][7ea3711d0d714cd8ac5d35edf6ffdacb.png_pic_center]

代码实现参考：

![在这里插入图片描述][bbafb972a234482c83f3e02a46158cf1.png_pic_center]

链表中的某个节点为`B`，`B`的下一个节点为`C` ，表示： `B.next==C`。

#### 3.2 单向链表时间复杂度分析 ####

（1）查询操作

![在这里插入图片描述][e44b37efd3ab41568ddbd72d34e8691b.png_pic_center]

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

（2）插入和删除操作

![在这里插入图片描述][d2b5630b9ac6466d9eeed0cfb84eee74.png_pic_center]

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

#### 3.3 双向链表 ####

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

*  每个结点不止有一个后继指针`next`指向后面的结点。
 *  有一个前驱指针`prev`指向前面的结点。

参考代码：

![在这里插入图片描述][d44cbec6cb4343e4bb9415e40ed41f94.png_pic_center]

![在这里插入图片描述][65f28882444a4eb8ad3a9f41ce9e0fb3.png_pic_center]

对比单链表：

*  双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。
 *  支持双向遍历，这样也带来了双向链表操作的灵活性。

#### 3.4 双向链表时间复杂度分析 ####

![在这里插入图片描述][f08c85384bdd484b81294293c065c1c9.png_pic_center]

（1）查询操作

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

（2）增删操作

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

#### 3.5 `ArrayList`和`LinkedList`的区别是什么？ ####

*  底层数据结构
    
     *  `ArrayList`是动态数组的数据结构实现。
     *  `LinkedList` 是双向链表的数据结构实现。
 *  操作数据效率
    
     *  `ArrayList`按照下标查询的时间复杂度`O(1)`【内存是连续的，根据寻址公式】， `LinkedList`不支持下标查询。
     *  查找（未知索引）： `ArrayList`需要遍历，链表也需要链表，时间复杂度都是`O(n)`。
     *  新增和删除
        
         *  `ArrayList`尾部插入和删除，时间复杂度是`O(1)`；其他部分增删需要挪动数组，时间复杂度是`O(n)`。
         *  `LinkedList`头尾节点增删时间复杂度是`O(1)`，其他都需要遍历链表，时间复杂度是`O(n)`。
 *  内存空间占用
    
     *  `ArrayList`底层是数组，内存连续，节省内存。
     *  `LinkedList`是双向链表需要存储数据，和两个指针，更占用内存。
 *  线程安全
    
     *  `ArrayList`和`LinkedList`都不是线程安全的。
     *  如果需要保证线程安全，有两种方案：
        
         *  在方法内使用，局部变量则是线程安全的。
         *  使用线程安全的`ArrayList`和`LinkedList`。

### 4. 面试现场 ###

##### 4.1 说一说`Java`提供的常见集合？（画一下集合结构图） #####

在`java`中提供了量大类的集合框架，主要分为两类：

![在这里插入图片描述][22ad28703f244416ad83f5067a27966d.png_pic_center]

第一个是`Collection` 属于单列集合，第二个是`Map` 属于双列集合。

*  在`Collection`中有两个子接口`List`和`Set`。在我们平常开发的过程中用的比较多像`list`接口中的实现类`ArrarList`和`LinkedList`。 在`Set`接口中有实现类`HashSet`和`TreeSet`。
 *  在`map`接口中有很多的实现类，平时比较常见的是`HashMap`、`TreeMap`，还有一个线程安全的`map:ConcurrentHashMap`。

##### 4.2 `ArrayList`底层是如何实现的？ #####

嗯~，我阅读过`arraylist`的源码，我主要说一下`add`方法吧。

第一：确保数组已使用长度（`size`）加1之后足够存下下一个数据 。

第二：计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用`grow`方法扩容（原来的1.5倍）。

第三：确保新增的数据有地方存储之后，则将新元素添加到位于`size`的位置上。

第四：返回添加成功布尔值。

##### 4.3 `ArrayList list=new ArrayList(10)`中的`list`扩容几次？ #####

好的，在`ArrayList`的源码中提供了一个带参数的构造方法，这个参数就是指定的集合初始长度，所以给了一个10的参数，就是指定了集合的初始长度是10，这里面并没有扩容。

##### 4.4 如何实现数组和`List`之间的转换？ #####

嗯，这个在我们平时开发很常见。

数组转`list`，可以使用`jdk`自动的一个工具类`Arrays`，里面有一个`asList`方法可以转换为数组。

`List` 转数组，可以直接调用`list`中的`toArray`方法，需要给一个参数，指定数组的类型，需要指定数组的长度。

##### 4.5 用`Arrays.asList`转`List`后，如果修改了数组内容，`list`受影响吗？`List`用`toArray`转数组后，如果修改了`List`内容，数组受影响吗？ #####

##### 4.6 `ArrayList`和`LinkedList`的区别是什么？ #####

嗯，它们两个主要是底层使用的数据结构不一样，`ArrayList`是动态数组，`LinkedList` 是双向链表，这也导致了它们很多不同的特点。

1，从操作数据效率来说：

`ArrayList`按照下标查询的时间复杂度`O(1)`【内存是连续的，根据寻址公式】， `LinkedList`不支持下标查询

查找（未知索引）：`ArrayList`需要遍历，链表也需要链表，时间复杂度都是`O(n)`

新增和删除

*  `ArrayList`尾部插入和删除，时间复杂度是`O(1)`；其他部分增删需要挪动数组，时间复杂度是`O(n)`
 *  `LinkedList`头尾节点增删时间复杂度是`O(1)`，其他都需要遍历链表，时间复杂度是`O(n)`

2，从内存空间占用来说：

`ArrayList`底层是数组，内存连续，节省内存；

`LinkedList`是双向链表需要存储数据，和两个指针，更占用内存。

3，从线程安全来说，`ArrayList`和`LinkedList`都不是线程安全的。

##### 4.7 刚才你说了`ArrayList`和`LinkedList`不是线程安全的，你们在项目中是如何解决这个的线程安全问题的？ #####

嗯，是这样的，主要有两种解决方案：

第一：我们使用这个集合，优先在方法内使用，定义为局部变量，这样的话，就不会出现线程安全问题。

第二：如果非要在成员变量中使用的话，可以使用线程安全的集合来替代。

`ArrayList`可以通过`Collections`的`synchronizedList`方法将`ArrayList`转换成线程安全的容器后再使用。

`LinkedList`换成`ConcurrentLinkedQueue`来使用。

[817c23466cd543bea0fb7f208c56b9f0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/480dc5dc54864bceb5b5eb26c781d662.png
[03b6f7337a404e598bcf67d182fa9eb1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/4e5ea174399847a591235589ac3317ee.png
[dcb4ffb1bb59410caf79b3d8f014c20a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/12017dad04a54f3cb7e4d9724a9cca78.png
[e559722209c54039bf101025cb09f75f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/f84550330e8c4d51a3c851a3690694b4.png
[29534636e57c4f7c8974b1dcb564fcc9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/db3cd2da49c8462581efe86aac96f250.png
[51dba58a3d8a46f699a0ac1ae4d1babd.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/e1f2a9578a52427586ea3f9f18ea4d83.png
[c8d612847d99420983730999e56ed9d8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/ce07ff901e4243038a35fb8622a0cb3c.png
[bfe29c21f88d4c18b242479b16f9ff8e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/c8eec518b75f4461af14b59bed4bf7ff.png
[2c10eed5b09c44329baa7b923c71a549.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/bb0741c20ee54c9095e9fdfe8aad8a3c.png
[ab1f647fba7e4511aa8aa96e82333fee.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/639b6ced6d4c4bf7824e1bb87486000d.png
[2207183059e74593ab134688ec4cfd01.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9bc5a36462d64c9f8ccf9c248e22757c.png
[c5ef50f6a27548f08aa7636d3459c0a3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/e370eeecdb6649e18cbae72b3e8dfc4c.png
[62810f44d15141d885b5b1f58c366a60.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/514d155c208a4c9f9a185398ae879672.png
[9f1fd2b1e7574dcd85a6712cf06f4114.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/eeda3d23275e4bb485c1d3c92c78fada.png
[fa708452824e4f9db054c4d1c31ef943.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8c74f24c0844433585c5fc1585473227.png
[7ea3711d0d714cd8ac5d35edf6ffdacb.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7a2834d4e4d247e1bfe4a4573f8caa0f.png
[bbafb972a234482c83f3e02a46158cf1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/553206d963ef49f8a4c3190f29766387.png
[e44b37efd3ab41568ddbd72d34e8691b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/24c49b7099a34cb8b8c01d2e051eab09.png
[d2b5630b9ac6466d9eeed0cfb84eee74.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/84d22083919d4d6489f34f113339a92c.png
[d44cbec6cb4343e4bb9415e40ed41f94.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7b51b98cd99249c2a7e8dbb7928b4edd.png
[65f28882444a4eb8ad3a9f41ce9e0fb3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/3f2cb35b7a35437ba77ca3ac39df0a40.png
[f08c85384bdd484b81294293c065c1c9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/316db772e5104b84be9e9e559d2bec87.png
[22ad28703f244416ad83f5067a27966d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/eaa68f9c0fdf4945bed364c38f2c214f.png