2023面试被打脸，数据结构底层都不知道么--回去等通知吧

太过爱你忘了你带给我的痛 2023-10-15 14:53 50阅读 0赞

### 数据结构之常见的8种数据结构： ###

\-数组Array

\-链表 Linked List

\-堆 heap

\-栈 stack

\-队列 Queue

\-树 Tree

\-散列表 Hash

\-图 Graph

![a26fc0859dec4871a026f4ec5a7e38fc.png][]

#### 数据结构-链表篇 ####

#####    Linklist定义： #####

\-是一种线性表，并不会按线性的顺序存储数据，即逻辑上相邻，物理上不一定相邻的元素。通过指针域来寻找对应的元素。

##### Linklist优缺点： #####

优点：  
\-插入、删除速度快

\-灵活分配结点空间

缺点：  
\-查询速度慢

##### 通过Linklist常用方法来深入底层原理 #####

\-add（E e）

![c05dfc0e5e754c388c3df891a2939493.png][]

\-add（int index, E element）

![f5de581ff6cb46d7809873abfe3379bd.png][]

\-remove(Obeject o)

![d3e2381e5c6f4d67bf52d76af3b006a4.png][]

\-remove(int index)

![cd4e6d31989c460886cbd3cba2ce10ba.png][]

\-ListIterator正向遍历

![54c4054f71a445f9805242435fbf07e9.png][]

\-反向遍历

![c52c2a4d9c81481794506c032b9b6993.png][]

##### 总结： #####

\-插入、删除速度快是因为只要通过前后指针就能插入或者删除到链表中，不需要移动其它元素，插入头尾节点更快，因为Node结构体中保存了头尾指针。

\-查询速度慢是因为，查询先通过右位移运算来判断对链表是前半部分遍历还是后半部分遍历，剩下的半部分遍历则是一个个节点遍历，头尾查询快，因为保存了头尾指针。

#### 数据结构--数组篇 ####

##### 数组的定义： #####

\-申请一块连续的内存空间来存储相同类型数据的集合

\-数组存储的是对象的引用而非是对象本身

##### 数组的优缺点： #####

优点：查询速度快（O（1）复杂度），因为它的存储是连续的内存空间，查找元素=首地址 + 每个元素所分配的空间\*下标

从cpu的读取：cpu在读取数组的时候，可以借助缓存机制预读数组的数据，cpu在读取内存的时候会把一块连续的内存空间读入，当进行遍历时，直接命中。而链表是跳跃式的地址，在缓存中命中的概率低，就要跑到内存中去读取数据，缓存的速度远大于内存的读取速度。

缺点：插入 、删除速度慢，因为需要移动该元素后面的所有元素位置

##### 数组的使用场景： #####

\-适合查询多，插入、删除少的场景（整体上来说）

##### 通过数组方法来深入底层原理 #####

ArrayList方法中的常用方法  
\-add（E e）方法

![8d9f3850b28642b3ba1dd323e48adf22.png][]  
流程图：

![9a64b6bf9c054539b50ce51b099a7f56.png][]  
remove（int index）方法：

![5e59def888c4409b90e6a72cafe2ea08.png][]

remove（Object o）方法

![2f5edfbce6a24c8a8baa9d7a8b7d7eb2.png][]

remove注意：remove（Object o）方法使用了2个对null跟非null分别使用了==跟equals做了等值比较，找到元素对应的索引位置后再删除与remove（int index）方法步骤基本一样

Iterator遍历方法

![e97ff4f07c074636b427dcdf7eb99af7.png][]

迭代注意：迭代过程中有2次的ConcurrentModification检验，一次是2个记录修改次参数expectedModCount = modCount等值校验。二次是 i >= elementData.length，并发过程中多次调用next方法。

Iterator的remove方法

![6a85530624294fa0a16b414efca91092.png][]

关于System.arraycopy,Array.copyof区别：  
\-System.arraycopy（Object src, int srcPos, Object dest, int destPos,int length）

有5个参数

src ：原数组

srcPos：原数组开始元素拷贝的索引位置

dest：目标数组

destPos：在目标数组的索引位置开始拷贝

length：拷贝的数组长度

\-Arraycopyof 底层调用的也是Native方法的System.arraycopy

##### ![11a37013778641d88246ff730ec920cd.png][]   面试点提问：几种删除方式有什么区别 #####

重点关注：expectedModCount = modCount;ConcurrentModificationException

##### for循环删除跟Iterator删除方式有什么不同？ #####

![1912e127526a47659e3f869cd5617593.png][]

Iterator方法：

![95dbf25ccd1d4ee59589ff0741027f23.png][]

![2028709085704be9802ff7c9b53e5bb4.png][]

正序for循环则直接调用remove(Object)或者remove(index)方法，修改了modCount++的值，但是并没有走checkForComodification()检验，该方法只针对了实现了Iterator<E>的类，想要正确删除元素请使用倒序删除

以上2个方法都可以直接删除元素不会报错，正序for循环不保证结果正确性

可以用foreach加强循环删除么？  
a,foreach底层的实现原理就是通过Iterator迭代来实现的。所以会存在修改次数跟预期值修改值的比较判断。

b,而foreach循环在删除元素的时候走的是fastRemove（）方法，

![fe4a537786594029b807a61bd5cdadf7.png][]  
c,只增加了modCount++

![b58251a94d6941288a2ed8f18f64133c.png][]  
d,并没有expectedModCount = modCount赋值语句，在下一次的循环就会报错

![1ba45da1a6f740b697114c9267849699.png][]  
综上所述：使用Iterator跟for循环是可以成功删除元素的，foreach循环则不行。checkForComodification()检验，该方法只针对了实现了Iterator<E>的类，而Iterator跟foreach底层实现都是依赖这个接口。for循环则不依赖

注意上面的Demo只是说删除元素时会不会报错，并不是说上面几种方式都能正确删除完全，使用for循环保证正取删除元素可以使用倒序的方式，或者使用Iterator方式（推荐）。

[a26fc0859dec4871a026f4ec5a7e38fc.png]: https://img-blog.csdnimg.cn/a26fc0859dec4871a026f4ec5a7e38fc.png
[c05dfc0e5e754c388c3df891a2939493.png]: https://img-blog.csdnimg.cn/c05dfc0e5e754c388c3df891a2939493.png
[f5de581ff6cb46d7809873abfe3379bd.png]: https://img-blog.csdnimg.cn/f5de581ff6cb46d7809873abfe3379bd.png
[d3e2381e5c6f4d67bf52d76af3b006a4.png]: https://img-blog.csdnimg.cn/d3e2381e5c6f4d67bf52d76af3b006a4.png
[cd4e6d31989c460886cbd3cba2ce10ba.png]: https://img-blog.csdnimg.cn/cd4e6d31989c460886cbd3cba2ce10ba.png
[54c4054f71a445f9805242435fbf07e9.png]: https://img-blog.csdnimg.cn/54c4054f71a445f9805242435fbf07e9.png
[c52c2a4d9c81481794506c032b9b6993.png]: https://img-blog.csdnimg.cn/c52c2a4d9c81481794506c032b9b6993.png
[8d9f3850b28642b3ba1dd323e48adf22.png]: https://img-blog.csdnimg.cn/8d9f3850b28642b3ba1dd323e48adf22.png
[9a64b6bf9c054539b50ce51b099a7f56.png]: https://img-blog.csdnimg.cn/9a64b6bf9c054539b50ce51b099a7f56.png
[5e59def888c4409b90e6a72cafe2ea08.png]: https://img-blog.csdnimg.cn/5e59def888c4409b90e6a72cafe2ea08.png
[2f5edfbce6a24c8a8baa9d7a8b7d7eb2.png]: https://img-blog.csdnimg.cn/2f5edfbce6a24c8a8baa9d7a8b7d7eb2.png
[e97ff4f07c074636b427dcdf7eb99af7.png]: https://img-blog.csdnimg.cn/e97ff4f07c074636b427dcdf7eb99af7.png
[6a85530624294fa0a16b414efca91092.png]: https://img-blog.csdnimg.cn/6a85530624294fa0a16b414efca91092.png
[11a37013778641d88246ff730ec920cd.png]: https://img-blog.csdnimg.cn/11a37013778641d88246ff730ec920cd.png
[1912e127526a47659e3f869cd5617593.png]: https://img-blog.csdnimg.cn/1912e127526a47659e3f869cd5617593.png
[95dbf25ccd1d4ee59589ff0741027f23.png]: https://img-blog.csdnimg.cn/95dbf25ccd1d4ee59589ff0741027f23.png
[2028709085704be9802ff7c9b53e5bb4.png]: https://img-blog.csdnimg.cn/2028709085704be9802ff7c9b53e5bb4.png
[fe4a537786594029b807a61bd5cdadf7.png]: https://img-blog.csdnimg.cn/fe4a537786594029b807a61bd5cdadf7.png
[b58251a94d6941288a2ed8f18f64133c.png]: https://img-blog.csdnimg.cn/b58251a94d6941288a2ed8f18f64133c.png
[1ba45da1a6f740b697114c9267849699.png]: https://img-blog.csdnimg.cn/1ba45da1a6f740b697114c9267849699.png