List相關(guān)面試題

數(shù)組

數(shù)組概述

數(shù)組（Array）是一種用連續(xù)的內(nèi)存空間存儲相同數(shù)據(jù)類型數(shù)據(jù)的線性數(shù)據(jù)結(jié)構(gòu)。

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

我們定義了這么一個數(shù)組之后，在內(nèi)存的表示是這樣的：

現(xiàn)在假如，我們通過arrar[1]，想要獲得下標(biāo)為1這個元素，但是現(xiàn)在棧內(nèi)存中指向的堆內(nèi)存數(shù)組的首地址，它是如何獲取下標(biāo)為1這個數(shù)據(jù)的？

尋址公式

為了方便大家理解，我們把數(shù)組的內(nèi)存地址稍微改了一下，都改成了數(shù)字，如下圖

在數(shù)組在內(nèi)存中查找元素的時候，是有一個尋址公式的，如下：

arr[i] = baseAddress + i * dataTypeSize

baseAddress：數(shù)組的首地址，目前是10

dataTypeSize：代表數(shù)組中元素類型的大小，目前數(shù)組重存儲的是int型的數(shù)據(jù)，dataTypeSize=4個字節(jié)

arr：指的是數(shù)組

i：指的是數(shù)組的下標(biāo)

有了尋址公式以后，我們再來獲取一下下標(biāo)為1的元素，這個是原來的數(shù)組

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

套入公式：

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

獲取到14這個地址，就能獲取到下標(biāo)為1的這個元素了。

操作數(shù)組的時間復(fù)雜度

1.隨機(jī)查詢(根據(jù)索引查詢)

數(shù)組元素的訪問是通過下標(biāo)來訪問的，計(jì)算機(jī)通過數(shù)組的首地址和尋址公式能夠很快速的找到想要訪問的元素

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

代碼的執(zhí)行次數(shù)并不會隨著數(shù)組的數(shù)據(jù)規(guī)模大小變化而變化，是常數(shù)級的，所以查詢數(shù)據(jù)操作的時間復(fù)雜度是O(1)

2. 未知索引查詢O(n)或O(log2n)

情況一：查找數(shù)組內(nèi)的元素，查找55號數(shù)據(jù)，遍歷數(shù)組時間復(fù)雜度為O(n)

情況二：查找排序后數(shù)組內(nèi)的元素，通過二分查找算法查找55號數(shù)據(jù)時間復(fù)雜度為O(logn)

3.插入O(n)

數(shù)組是一段連續(xù)的內(nèi)存空間，因此為了保證數(shù)組的連續(xù)性會使得數(shù)組的插入和刪除的效率變的很低。

假設(shè)數(shù)組的長度為 n，現(xiàn)在如果我們需要將一個數(shù)據(jù)插入到數(shù)組中的第 k 個位置。為了把第 k 個位置騰出來給新來的數(shù)據(jù)，我們需要將第 k～n 這部分的元素都順序地往后挪一位。如下圖所示：

新增之后的數(shù)據(jù)變化，如下

所以：

插入操作，最好情況下是O(1)的，最壞情況下是O(n)的，平均情況下的時間復(fù)雜度是O(n)。

4.刪除O(n)

同理可得：如果我們要刪除第 k 個位置的數(shù)據(jù)，為了內(nèi)存的連續(xù)性，也需要搬移數(shù)據(jù)，不然中間就會出現(xiàn)空洞，內(nèi)存就不連續(xù)了，時間復(fù)雜度仍然是O(n)。

ArrayList源碼分析

分析ArrayList源碼主要從三個方面去翻閱：成員變量，構(gòu)造函數(shù)，關(guān)鍵方法

以下源碼都來源于jdk1.8

成員變量

DEFAULT_CAPACITY = 10; 默認(rèn)初始的容量**(CAPACITY)

EMPTY_ELEMENTDATA = {}; 用于空實(shí)例的共享空數(shù)組實(shí)例

DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};用于默認(rèn)大小的空實(shí)例的共享空數(shù)組實(shí)例

Object[] elementData; 存儲元素的數(shù)組緩沖區(qū)

int size; ArrayList的大?。ㄋ脑?cái)?shù)量）

構(gòu)造方法

• 第一個構(gòu)造是帶初始化容量的構(gòu)造函數(shù)，可以按照指定的容量初始化數(shù)組

• 第二個是無參構(gòu)造函數(shù)，默認(rèn)創(chuàng)建一個空集合

將collection對象轉(zhuǎn)換成數(shù)組，然后將數(shù)組的地址的賦給elementData

ArrayList源碼分析

添加數(shù)據(jù)的流程

結(jié)論：

• 底層數(shù)據(jù)結(jié)構(gòu)

ArrayList底層是用動態(tài)的數(shù)組實(shí)現(xiàn)的

• 初始容量

ArrayList初始容量為0，當(dāng)?shù)谝淮翁砑訑?shù)據(jù)的時候才會初始化容量為10

• 擴(kuò)容邏輯

ArrayList在進(jìn)行擴(kuò)容的時候是原來容量的1.5倍，每次擴(kuò)容都需要拷貝數(shù)組

• 添加邏輯

  • 確保數(shù)組已使用長度（size）加1之后足夠存下下一個數(shù)據(jù)

  • 計(jì)算數(shù)組的容量，如果當(dāng)前數(shù)組已使用長度+1后的大于當(dāng)前的數(shù)組長度，則調(diào)用grow方法擴(kuò)容（原來的1.5倍）

  • 確保新增的數(shù)據(jù)有地方存儲之后，則將新元素添加到位于size的位置上。

  • 返回添加成功布爾值。

面試題-ArrayList list=new ArrayList(10)中的list擴(kuò)容幾次

難易程度：☆☆☆

出現(xiàn)頻率：☆☆

參考回答：

該語句只是聲明和實(shí)例了一個 ArrayList，指定了容量為 10，未擴(kuò)容

面試題-如何實(shí)現(xiàn)數(shù)組和List之間的轉(zhuǎn)換

難易程度：☆☆☆

出現(xiàn)頻率：☆☆

如下代碼：

參考回答：

• 數(shù)組轉(zhuǎn)List ，使用JDK中java.util.Arrays工具類的asList方法

• List轉(zhuǎn)數(shù)組，使用List的toArray方法。無參toArray方法返回 Object數(shù)組，傳入初始化長度的數(shù)組對象，返回該對象數(shù)組

面試官再問：

1，用Arrays.asList轉(zhuǎn)List后，如果修改了數(shù)組內(nèi)容，list受影響嗎

2，List用toArray轉(zhuǎn)數(shù)組后，如果修改了List內(nèi)容，數(shù)組受影響嗎

)

數(shù)組轉(zhuǎn)List受影響

List轉(zhuǎn)數(shù)組不受影響

再答：

1，用Arrays.asList轉(zhuǎn)List后，如果修改了數(shù)組內(nèi)容，list受影響嗎

Arrays.asList轉(zhuǎn)換list之后，如果修改了數(shù)組的內(nèi)容，list會受影響，因?yàn)樗牡讓邮褂玫腁rrays類中的一個內(nèi)部類ArrayList來構(gòu)造的集合，在這個集合的構(gòu)造器中，把我們傳入的這個集合進(jìn)行了包裝而已，最終指向的都是同一個內(nèi)存地址

2，List用toArray轉(zhuǎn)數(shù)組后，如果修改了List內(nèi)容，數(shù)組受影響嗎

list用了toArray轉(zhuǎn)數(shù)組后，如果修改了list內(nèi)容，數(shù)組不會影響，當(dāng)調(diào)用了toArray以后，在底層是它是進(jìn)行了數(shù)組的拷貝，跟原來的元素就沒啥關(guān)系了，所以即使list修改了以后，數(shù)組也不受影響

鏈表

單向鏈表

• 鏈表中的每一個元素稱之為結(jié)點(diǎn)（Node）

• 物理存儲單元上，非連續(xù)、非順序的存儲結(jié)構(gòu)

• 單向鏈表：每個結(jié)點(diǎn)包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點(diǎn)地址的指針域。記錄下個結(jié)點(diǎn)地址的指針叫作后繼指針 next

代碼實(shí)現(xiàn)參考：

鏈表中的某個節(jié)點(diǎn)為B，B的下一個節(jié)點(diǎn)為C 表示： B.next==C

單向鏈表時間復(fù)雜度分析

（1）查詢操作

• 只有在查詢頭節(jié)點(diǎn)的時候不需要遍歷鏈表，時間復(fù)雜度是O(1)

• 查詢其他結(jié)點(diǎn)需要遍歷鏈表，時間復(fù)雜度是O(n)

（2）插入和刪除操作

• 只有在添加和刪除頭節(jié)點(diǎn)的時候不需要遍歷鏈表，時間復(fù)雜度是O(1)
• 添加或刪除其他結(jié)點(diǎn)需要遍歷鏈表找到對應(yīng)節(jié)點(diǎn)后，才能完成新增或刪除節(jié)點(diǎn)，時間復(fù)雜度是O(n)

雙向鏈表

而雙向鏈表，顧名思義，它支持兩個方向

• 每個結(jié)點(diǎn)不止有一個后繼指針 next 指向后面的結(jié)點(diǎn)

• 有一個前驅(qū)指針 prev 指向前面的結(jié)點(diǎn)

參考代碼

對比單鏈表：

• 雙向鏈表需要額外的兩個空間來存儲后繼結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)的地址

• 支持雙向遍歷，這樣也帶來了雙向鏈表操作的靈活性

雙向鏈表時間復(fù)雜度分析

（1）查詢操作

• 查詢頭尾結(jié)點(diǎn)的時間復(fù)雜度是O(1)

• 平均的查詢時間復(fù)雜度是O(n)

• 給定節(jié)點(diǎn)找前驅(qū)節(jié)點(diǎn)的時間復(fù)雜度為O(1)

（2）增刪操作

• 頭尾結(jié)點(diǎn)增刪的時間復(fù)雜度為O(1)

• 其他部分結(jié)點(diǎn)增刪的時間復(fù)雜度是 O(n)

• 給定節(jié)點(diǎn)增刪的時間復(fù)雜度為O(1)

面試題-ArrayList和LinkedList的區(qū)別是什么？

• 底層數(shù)據(jù)結(jié)構(gòu)

  • ArrayList 是動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)

  • LinkedList 是雙向鏈表的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)

• 操作數(shù)據(jù)效率

  • ArrayList按照下標(biāo)查詢的時間復(fù)雜度O(1)【內(nèi)存是連續(xù)的，根據(jù)尋址公式】， LinkedList不支持下標(biāo)查詢
  • 查找（未知索引）： ArrayList需要遍歷，鏈表也需要鏈表，時間復(fù)雜度都是O(n)
  • 新增和刪除
    • ArrayList尾部插入和刪除，時間復(fù)雜度是O(1)；其他部分增刪需要挪動數(shù)組，時間復(fù)雜度是O(n)
    • LinkedList頭尾節(jié)點(diǎn)增刪時間復(fù)雜度是O(1)，其他都需要遍歷鏈表，時間復(fù)雜度是O(n)

• 內(nèi)存空間占用

  • ArrayList底層是數(shù)組，內(nèi)存連續(xù)，節(jié)省內(nèi)存

  • LinkedList 是雙向鏈表需要存儲數(shù)據(jù)，和兩個指針，更占用內(nèi)存

• 線程安全

  • ArrayList和LinkedList都不是線程安全的
  • 如果需要保證線程安全，有兩種方案：
    • 在方法內(nèi)使用，局部變量則是線程安全的
    • 使用線程安全的ArrayList和LinkedList

總結(jié) 

到此這篇關(guān)于Java集合List相關(guān)面試題整理大全的文章就介紹到這了,更多相關(guān)Java集合List面試題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論