数据结构--数组篇（想到啥写啥）

骑猪看日落 2023-09-23 23:03 71阅读 0赞

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

\-数组Array

\-链表 Linked List

\-堆 heap

\-栈 stack

\-队列 Queue

\-树 Tree

\-散列表 Hash

\-图 Graph

![3a7b1e473731c13b494fd09035b399e1.png][]

## 数组的定义： ##

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

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

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

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

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

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

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

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

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

#### ArrayList方法中的常用方法 ####

##### \-add（E e）方法 #####

![fddeeb0c5ed45a84f445c82043a91aa3.png][]

![5a369fbe5c427065d302b2149ee53649.png][]

流程图：

![55aac9b01abb9da8a5a0b2065d53999b.png][]

##### remove（int index）方法： #####

![696425ec97f8ea413fe4ebf56f66bb15.png][]

##### remove（Object o）方法 #####

![e2c26eb69d9d412e2b9db222238d96a3.png][]

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

##### Iterator遍历方法 #####

![d67c36056724f005a1a41f8d3ac84883.png][]

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

##### Iterator的remove方法 #####

![85d2d6dc78b0d375007e069cb6f338ad.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

![756f694e0d85c0e4bf460ab09eceed0e.png][]

### 面试点提问：几种删除方式有什么区别 ###

重点关注：**expectedModCount** = **modCount**;*ConcurrentModificationException*

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

![c968b5fe214a4ada9adaeee5d2f28812.png][]

Iterator方法：

![acf14ab907b342efa9c36149c8b60221.png][]

![feb0bd70fc3048a3afcd24bf747f58c3.png][]

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

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

#### 可以用foreach加强循环删除么？ ####

a,foreach底层的实现原理就是通过Iterator迭代来实现的。所以会存在修改次数跟预期值修改值的比较判断。

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

![2ef0bcbf587d46aa9fe45c3a1ce79746.png][]

c,只增加了modCount++

![1636cc73aefc4e02b438fc7afe44b2a9.png][]

d,并没有**expectedModCount** = **modCount赋值语句，在下一次的循环就会报错**

![62c6b7e1dbe849e9932a08b495c60472.png][]

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

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

[3a7b1e473731c13b494fd09035b399e1.png]: https://img-blog.csdnimg.cn/img_convert/3a7b1e473731c13b494fd09035b399e1.png
[fddeeb0c5ed45a84f445c82043a91aa3.png]: https://img-blog.csdnimg.cn/img_convert/fddeeb0c5ed45a84f445c82043a91aa3.png
[5a369fbe5c427065d302b2149ee53649.png]: https://img-blog.csdnimg.cn/img_convert/5a369fbe5c427065d302b2149ee53649.png
[55aac9b01abb9da8a5a0b2065d53999b.png]: https://img-blog.csdnimg.cn/img_convert/55aac9b01abb9da8a5a0b2065d53999b.png
[696425ec97f8ea413fe4ebf56f66bb15.png]: https://img-blog.csdnimg.cn/img_convert/696425ec97f8ea413fe4ebf56f66bb15.png
[e2c26eb69d9d412e2b9db222238d96a3.png]: https://img-blog.csdnimg.cn/img_convert/e2c26eb69d9d412e2b9db222238d96a3.png
[d67c36056724f005a1a41f8d3ac84883.png]: https://img-blog.csdnimg.cn/img_convert/d67c36056724f005a1a41f8d3ac84883.png
[85d2d6dc78b0d375007e069cb6f338ad.png]: https://img-blog.csdnimg.cn/img_convert/85d2d6dc78b0d375007e069cb6f338ad.png
[756f694e0d85c0e4bf460ab09eceed0e.png]: https://img-blog.csdnimg.cn/img_convert/756f694e0d85c0e4bf460ab09eceed0e.png
[c968b5fe214a4ada9adaeee5d2f28812.png]: https://img-blog.csdnimg.cn/img_convert/c968b5fe214a4ada9adaeee5d2f28812.png
[acf14ab907b342efa9c36149c8b60221.png]: https://img-blog.csdnimg.cn/img_convert/acf14ab907b342efa9c36149c8b60221.png
[feb0bd70fc3048a3afcd24bf747f58c3.png]: https://img-blog.csdnimg.cn/img_convert/feb0bd70fc3048a3afcd24bf747f58c3.png
[2ef0bcbf587d46aa9fe45c3a1ce79746.png]: https://img-blog.csdnimg.cn/img_convert/2ef0bcbf587d46aa9fe45c3a1ce79746.png
[1636cc73aefc4e02b438fc7afe44b2a9.png]: https://img-blog.csdnimg.cn/img_convert/1636cc73aefc4e02b438fc7afe44b2a9.png
[62c6b7e1dbe849e9932a08b495c60472.png]: https://img-blog.csdnimg.cn/img_convert/62c6b7e1dbe849e9932a08b495c60472.png