目錄
1.java集合框架體系
2. 前置知識-數組
2.1?數組
2.1.1 定義：
2.1.2 數組如何獲取其他元素的地址值？（尋址公式）
2.1.3?為什么數組索引從0開始呢？從1開始不行嗎？
3. ArrayList
3.1 ArrayList和和Vector的區別？（了解）
3.2?ArrayList 可以添加 null 值嗎？
3.3?ArrayList源碼
成員變量
?編輯構造方法
3.4 ArrayList 底層實現原理 ★
3.5?ArrayList list = new ArrayList(10)中的list擴容幾次？★
3.6?數組和List之間相互轉換？★
3.7?數組和List之間相互轉換過程中，數據發生修改，結果會變嗎（有影響嗎）？★
3.7.1? 用Arrays.asList() 轉List后，如修改了數組內容，list集合結果受影響嗎？
3.7.2 List用toArray() 轉數組后，如果修改了List內容，數組受影響嗎？
4. 前置知識-鏈表
4.1單向鏈表
4.1.1 單向鏈表特點及參考源碼
4.1.2?單向鏈表時間復雜度分析
1 查詢操作
2 插入和刪除操作
4.2 雙向鏈表
4.2.1?雙向鏈表特點及參考源碼
4.2.2?雙向鏈表時間復雜度分析
1.?查詢操作
2 增刪操作
5.?LinkedList
6.?ArrayList與LinkedList區別？★
1.java集合框架體系
2. 前置知識-數組
2.1?數組
2.1.1 定義：
數組（Array）是一種用連續的內存空間存儲相同數據類型數據的線性數據結構。
int[] array = {22,33,88,66,55,25};2.1.2 數組如何獲取其他元素的地址值？（尋址公式）
arr[i] = baseAddress + i * dataTypeSize2.1.3?為什么數組索引從0開始呢？從1開始不行嗎？
實際上并不是不行。而是如果數組索引從1開始的話，整體性能會變低。
因為尋址公式會變為a[i] = baseAddress + (i-1) *dataTypeSize，也就是說，多了一個減法操作。
3. ArrayList
?ArrayList 的底層是數組隊列，相當于動態數組。與 Java 中的數組相比，它的容量能動態增長。在添加大量元素前，應用程序可以使用ArrayList底層API的 ensureCapacity()操作來增加 ArrayList 實例的容量。這可以減少遞增式再分配的數量。
3.1 ArrayList和和Vector的區別？（了解）
ArrayList 是 List 的主要實現類，底層使用 Object[]存儲，適用于頻繁的查找工作，線程不安全 。 ?
Vector 是 List 的古老實現類，底層使用Object[] 存儲，線程安全。
3.2?ArrayList 可以添加 null 值嗎？
可以。ArrayList 中可以存儲任何類型的對象，包括 null 值。不過，不建議向ArrayList 中添加 null 值， null 值無意義，會讓代碼難以維護比如忘記做判空處理就會導致空指針異常。
3.3?ArrayList源碼
成員變量
構造方法
第一個構造是帶初始化容量的構造函數，可以按照指定的容量初始化數組第二個是無參構造函數，默認創建一個空集合
/***構造包含指定collection元素的列表，這些元素利用該集合的迭代器按順序返回*如果指定的集合為null，throws NullPointerException。*/
public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}
}
將 collection 對象轉換成數組，然后將數組的地址的賦給 elementData
3.4 ArrayList 底層實現原理 ★
1. 底層數據結構
ArrayList 底層是用動態的數組實現的
2. 初始容量
ArrayList 初始容量為 0 ，當第一次添加數據的時候才會初始化容量為 10
3. 擴容邏輯
ArrayList 在進行擴容的時候是原來容量的 1.5 倍，每次擴容都需要拷貝數組
4. 添加邏輯
添加數據的流程：
1. 確保數組已使用長度（ size ）加 1 之后足夠存下下一個數據2. 計算數組的容量，如果當前數組已使用長度 +1 后的大于當前的數組長度，3. 則調用 grow 方法擴容（原來的 1.5 倍）4. 確保新增的數據有地方存儲之后，則將新元素添加到位于 size 的位置上。5. 返回添加成功布爾值。
3.5?ArrayList list = new ArrayList(10)中的list擴容幾次？★
答：該語句只是聲明和實例了一個 ArrayList ，指定了容量為 10 ，未擴容
ArrayList的擴容機制如下：
當
ArrayList被初始化時，如果沒有指定初始容量，它將使用默認的初始容量（10）。當添加元素超過當前容量時，
ArrayList會進行擴容。默認情況下，擴容后的容量是當前容量的1.5倍（即增加50%）。
3.6?數組和List之間相互轉換？★
參考回答：
- 數組轉List ，使用JDK中java.util.Arrays工具類的asList方法，返回一個List集合
- List轉數組，使用List的toArray方法。無參toArray方法返回 Object數組，傳入初始化長度的數組對象，返回該對象數組
3.7?數組和List之間相互轉換過程中，數據發生修改，結果會變嗎（有影響嗎）？★
分為兩種情況：
3.7.1? 用Arrays.asList() 轉List后，如修改了數組內容，list集合結果受影響嗎？
答：會受影響
Arrays.asList方法返回的是一個固定大小的列表，它的底層仍然是原始數組。當你通過
Arrays.asList獲得的列表并嘗試修改其中的元素時，實際上是在修改原始數組的內容，因為列表中的元素和數組中的元素是同一個對象（同一個地址引用）。
源碼如下：
3.7.2 List用toArray() 轉數組后，如果修改了List內容，數組受影響嗎？
答：不會影響。
list用了toArray轉數組后，如果修改了list內容，數組不會影響，當調用了toArray ?以后，在底層是它是進行了數組的拷貝，跟原來的元素就沒啥關系了，所以即使 ?list修改了以后，數組
也不受影響
4. 前置知識-鏈表
LinkedList 底層數據結構——雙向鏈表
4.1單向鏈表
4.1.1 單向鏈表特點及參考源碼
- 鏈表中的每一個元素稱之為結點（Node）
- 物理存儲單元上，非連續、非順序的存儲結構
- 單向鏈表：每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個 是存儲下一個結點地址的指針域。記錄下個結點地址的指針叫作后繼指針next
代碼實現參考：
4.1.2?單向鏈表時間復雜度分析
1 查詢操作
查詢：頭節點：O(1)，一般情況：O(n)
- 只有在查詢頭節點的時候不需要遍歷鏈表，時間復雜度是O(1)
- 查詢其他結點需要遍歷鏈表，時間復雜度是O(n)
2 插入和刪除操作
增刪：頭節點：O(1)，一般情況：O(n)
- 只有在添加和刪除頭節點的時候不需要遍歷鏈表，時間復雜度是O(1)
- 添加或刪除其他結點需要遍歷鏈表找到對應節點后，才能完成新增或刪除節點，時間復雜度是O(n)
4.2 雙向鏈表
4.2.1?雙向鏈表特點及參考源碼
而雙向鏈表，顧名思義，它支持兩個方向
- 每個結點不止有一個后繼指針 next 指向后面的結點
- 有一個前驅指針 prev 指向前面的結點
4.2.2?雙向鏈表時間復雜度分析
1.?查詢操作
查詢：頭尾節點：O(1)，一般情況：O(n)，給定節點找前驅節點：O(1)
- 查詢頭尾結點的時間復雜度是O(1)
- 平均的查詢時間復雜度是O(n)
- 給定節點找前驅節點的時間復雜度為O(1)
2 增刪操作
增刪：頭尾節點：O(1)，一般情況：O(n)，給定節點找前驅節點：O(1)
- 頭尾結點增刪的時間復雜度為O(1)
- 其他部分結點增刪的時間復雜度是 O(n)
- 給定節點增刪的時間復雜度為O(1)
5.?LinkedList
LinkedList 底層數據結構——雙向鏈表
查詢快，增刪改慢，適用于讀多寫少的場景
6.?ArrayList與LinkedList區別？★
從四個方面來談。
- 底層數據結構：ArrayList 是動態數組的數據結構實現，LinkedList 是雙向鏈表的數據結構實現
- 效率上，除了 LinkedList不支持下標查詢，ArrayList支持下標查詢。其他都差不多。
- 空間上，ArrayList底層是數組，內存連續，節省內存。LinkedList 是雙向鏈表需要存儲數據，和兩個指針，更占用內存。
- 線程安全問題，ArrayList和LinkedList都不是線程安全的。
如果需要保證線程安全，有兩種方案：
- 在方法內使用，局部變量則是線程安全的
- 使用線程安全的ArrayList和LinkedList：
Collections.synchronizedList(new ArrayList<>()); Collections.synchronizedList(new LinkedList<>());
還有一下三個方面的區別可以了解一下：
- 插入和刪除是否受元素位置的影響：
ArrayList?采用數組存儲，所以插入和刪除元素的時間復雜度受元素位置的影響。 比如：執行add(E e)方法的時候，?ArrayList?會默認在將指定的元素追加到此列表的末尾，這種情況時間復雜度就是 O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element)），時間復雜度就為 O(n)。因為在進行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執行向后位/向前移一位的操作。LinkedList?采用鏈表存儲，所以在頭尾插入或者刪除元素不受元素位置的影響（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、?removeLast()），時間復雜度為 O(1)，如果是要在指定位置?i?插入和刪除元素的話（add(int index, E element)，remove(Object o),remove(int index)）， 時間復雜度為 O(n) ，因為需要先移動到指定位置再插入和刪除。- 是否支持快速隨機訪問：?
LinkedList?不支持高效的隨機元素訪問，而?ArrayList（實現了?RandomAccess?接口） 支持。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應于get(int index)方法)。- 內存空間占用：?
ArrayList?的空間浪費主要體現在在 list 列表的結尾會預留一定的容量空間，而 LinkedList 的空間花費則體現在它的每一個元素都需要消耗比 ArrayList 更多的空間（因為要存放直接后繼和直接前驅以及數據）。
)
