數(shù)據(jù)結(jié)構(gòu)之常見的8種數(shù)據(jù)結(jié)構(gòu)：

-數(shù)組Array

-鏈表 Linked List

-堆 heap

-棧 stack

-隊(duì)列 Queue

-樹 Tree

-散列表 Hash

-圖 Graph

數(shù)據(jù)結(jié)構(gòu)-鏈表篇

Linklist定義：

-是一種線性表，并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，即邏輯上相鄰，物理上不一定相鄰的元素。通過指針域來尋找對應(yīng)的元素。

Linklist優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：
-插入、刪除速度快

-靈活分配結(jié)點(diǎn)空間

缺點(diǎn)：
-查詢速度慢

通過Linklist常用方法來深入底層原理

-add（E e）

-add（int index, E element）

-remove(Obeject o)

-remove(int index)

-ListIterator正向遍歷

-反向遍歷

總結(jié)：

-插入、刪除速度快是因?yàn)橹灰ㄟ^前后指針就能插入或者刪除到鏈表中，不需要移動(dòng)其它元素，插入頭尾節(jié)點(diǎn)更快，因?yàn)镹ode結(jié)構(gòu)體中保存了頭尾指針。

-查詢速度慢是因?yàn)?，查詢先通過右位移運(yùn)算來判斷對鏈表是前半部分遍歷還是后半部分遍歷，剩下的半部分遍歷則是一個(gè)個(gè)節(jié)點(diǎn)遍歷，頭尾查詢快，因?yàn)楸４媪祟^尾指針。
?

數(shù)據(jù)結(jié)構(gòu)--數(shù)組篇

數(shù)組的定義：

-申請一塊連續(xù)的內(nèi)存空間來存儲(chǔ)相同類型數(shù)據(jù)的集合

-數(shù)組存儲(chǔ)的是對象的引用而非是對象本身

數(shù)組的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：查詢速度快（O（1）復(fù)雜度），因?yàn)樗拇鎯?chǔ)是連續(xù)的內(nèi)存空間，查找元素=首地址 + 每個(gè)元素所分配的空間*下標(biāo)

從cpu的讀?。篶pu在讀取數(shù)組的時(shí)候，可以借助緩存機(jī)制預(yù)讀數(shù)組的數(shù)據(jù)，cpu在讀取內(nèi)存的時(shí)候會(huì)把一塊連續(xù)的內(nèi)存空間讀入，當(dāng)進(jìn)行遍歷時(shí)，直接命中。而鏈表是跳躍式的地址，在緩存中命中的概率低，就要跑到內(nèi)存中去讀取數(shù)據(jù)，緩存的速度遠(yuǎn)大于內(nèi)存的讀取速度。

缺點(diǎn)：插入 、刪除速度慢，因?yàn)樾枰苿?dòng)該元素后面的所有元素位置

數(shù)組的使用場景：

-適合查詢多，插入、刪除少的場景（整體上來說）

通過數(shù)組方法來深入底層原理

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

流程圖：

remove（int index）方法：

remove（Object o）方法

remove注意：remove（Object o）方法使用了2個(gè)對null跟非null分別使用了==跟equals做了等值比較，找到元素對應(yīng)的索引位置后再刪除與remove（int index）方法步驟基本一樣

Iterator遍歷方法

迭代注意：迭代過程中有2次的ConcurrentModification檢驗(yàn)，一次是2個(gè)記錄修改次參數(shù)expectedModCount = modCount等值校驗(yàn)。二次是 i >= elementData.length，并發(fā)過程中多次調(diào)用next方法。

Iterator的remove方法

關(guān)于System.arraycopy,Array.copyof區(qū)別：
-System.arraycopy（Object src, int srcPos, Object dest, int destPos,int length）

有5個(gè)參數(shù)

src ：原數(shù)組

srcPos：原數(shù)組開始元素拷貝的索引位置

dest：目標(biāo)數(shù)組

destPos：在目標(biāo)數(shù)組的索引位置開始拷貝

length：拷貝的數(shù)組長度

-Arraycopyof 底層調(diào)用的也是Native方法的System.arraycopy

面試點(diǎn)提問：幾種刪除方式有什么區(qū)別

重點(diǎn)關(guān)注：expectedModCount = modCount;ConcurrentModificationException

for循環(huán)刪除跟Iterator刪除方式有什么不同？

Iterator方法：

正序for循環(huán)則直接調(diào)用remove(Object)或者remove(index)方法，修改了modCount++的值，但是并沒有走checkForComodification()檢驗(yàn)，該方法只針對了實(shí)現(xiàn)了Iterator<E>的類，想要正確刪除元素請使用倒序刪除

以上2個(gè)方法都可以直接刪除元素不會(huì)報(bào)錯(cuò)，正序for循環(huán)不保證結(jié)果正確性

可以用foreach加強(qiáng)循環(huán)刪除么？
a,foreach底層的實(shí)現(xiàn)原理就是通過Iterator迭代來實(shí)現(xiàn)的。所以會(huì)存在修改次數(shù)跟預(yù)期值修改值的比較判斷。

b,而foreach循環(huán)在刪除元素的時(shí)候走的是fastRemove（）方法，

c,只增加了modCount++

d,并沒有expectedModCount = modCount賦值語句，在下一次的循環(huán)就會(huì)報(bào)錯(cuò)

綜上所述：使用Iterator跟for循環(huán)是可以成功刪除元素的，foreach循環(huán)則不行。checkForComodification()檢驗(yàn)，該方法只針對了實(shí)現(xiàn)了Iterator<E>的類，而Iterator跟foreach底層實(shí)現(xiàn)都是依賴這個(gè)接口。for循環(huán)則不依賴

注意上面的Demo只是說刪除元素時(shí)會(huì)不會(huì)報(bào)錯(cuò)，并不是說上面幾種方式都能正確刪除完全，使用for循環(huán)保證正取刪除元素可以使用倒序的方式，或者使用Iterator方式（推薦）。
?文章來源地址http://www.zghlxwxcb.cn/news/detail-689947.html

到了這里，關(guān)于面試被打臉，數(shù)據(jù)結(jié)構(gòu)底層都不知道么--回去等通知吧的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！