七 集合（List）

7.1 復(fù)雜度分析

7.2 數(shù)組

1.數(shù)組(Array)是一種用連續(xù)的內(nèi)存空間存儲(chǔ)相同數(shù)據(jù)類型

數(shù)據(jù)的線性數(shù)據(jù)結(jié)構(gòu)。

2.數(shù)組下標(biāo)為什么從0開始

尋址公式是:baseAddress+i*dataTypeSize，計(jì)算下標(biāo)的內(nèi)存地址效率較高

3.查找的時(shí)間復(fù)雜度

• 隨機(jī)(通過下標(biāo))查詢的時(shí)間復(fù)雜度是O(1)
• 查找元素(未知下標(biāo))的時(shí)間復(fù)雜度是O(n)
• 查找元素(未知下標(biāo)但排序)通過二分查找的時(shí)間復(fù)雜度是O(logn)

4.插入和刪除時(shí)間復(fù)雜度

插入和刪除的時(shí)候，為了保證數(shù)組的內(nèi)存連續(xù)性，需要挪動(dòng)數(shù)組元素，平均時(shí)間復(fù)雜度為O(n)

7.3 ArrayList 底層實(shí)現(xiàn)

7.4 ArrayList底層的實(shí)現(xiàn)原理是什么

• ArrayList底層是用動(dòng)態(tài)的數(shù)組實(shí)現(xiàn)的
• ArrayList初始容量為0，當(dāng)?shù)谝淮翁砑訑?shù)據(jù)的時(shí)候才會(huì)初始化容量為10
• ArrayList在進(jìn)行擴(kuò)容的時(shí)候是原來(lái)容量的1.5倍，每次擴(kuò)容都需要拷貝數(shù)組
• ArrayList在添加數(shù)據(jù)的時(shí)候
  • 確保數(shù)組已使用長(zhǎng)度(size)加1之后足夠存下下一個(gè)數(shù)據(jù)
  • 計(jì)算數(shù)組的容量，如果當(dāng)前數(shù)組已使用長(zhǎng)度+1后的大于當(dāng)前的數(shù)組長(zhǎng)度，則調(diào)用grow方法擴(kuò)容(原來(lái)的1.5倍)
  • 確保新增的數(shù)據(jù)有地方存儲(chǔ)之后，則將新元素添加到位于size的位置上。
  • 返回添加成功布爾值。

7.5 ArrayList list=new ArrayList(10)中的list擴(kuò)容幾次

7.6 如何實(shí)現(xiàn)數(shù)組和list之間的轉(zhuǎn)換

• 數(shù)組轉(zhuǎn)List ，使用JDK中java.util.Arrays工具類的asList方法
• List轉(zhuǎn)數(shù)組，使用List的toArray方法。無(wú)參toArray方法返回Object數(shù)組，傳入初始化長(zhǎng)度的數(shù)組對(duì)象，返回該對(duì)象數(shù)組

7.7 ArrayList 和 LinkedList 的區(qū)別是什么?

7.7.1單向鏈表

• 鏈表中的每一個(gè)元素稱之為結(jié)點(diǎn)(Node)
• 物理存儲(chǔ)單元上，非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)
• 單向鏈表:每個(gè)結(jié)點(diǎn)包括兩個(gè)部分:一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。記錄下個(gè)結(jié)點(diǎn)地址的指針叫作后繼指針 next

7.7.2 雙向連表