一.數組
1.什么是數組？
數組是一種用連續的內存空間存儲相同類型數據的線性數據結構。
2.為什么數組下標是從0開始？
（1）數組根據下標查找元素是基于尋址公式：元素地址=數組首地址+索引i*數組存儲數據類型的大小
（2）如果下標從0開始，則尋址公式應改為：元素地址=數組首地址+(i-1)*數組存儲數據類型的大小；對cpu而言多了一個(i-1)的操作，性能下降。
3.數組查找元素的時間復雜度
（1）已知下標：O(1)
（2）未知下標：O(n)
（3）未知下標但排序：根據二分法查找是O(logn)
（4）插入和刪除時，為了保證在內存存儲的連續性，需要數組元素，平均時間復雜度為O(n)
二.ArrayList
1.ArrayList的底層實現原理是什么？
（1）ArrayList底層是用動態的數組實現的。
（2）ArrayList創建時，若未指定容量，則初始化數組長度為0；第一次添加數據時才將數組長度擴容為10。
（3）后續的每次擴容，都將數組長度擴容為原來的1.5倍；每次擴容都需要將原數組元素拷貝到新數組。
（4）ArrayList在添加數據時：
? ? ? ? a.計算數組當前已存儲容量size，若size+1>length，則調用grow()方法進行擴容(擴容為原來的1.5倍)。
? ? ? ? b.將新添加的數據存儲到數組的size位置上，添加成功返回布爾值
2.ArrayList list = new ArrayList(10)；代碼中list擴容了幾次？
（1）ArrayList有三種構造方法：
? ? ? ? a.ArrayList(int initialCapacity)：帶初始化容量的構造函數，將數組的容量初始化為initialCapacity；
? ? ? ? b.ArrayList()：無參構造函數，數組容量初始化為0，第一次添加元素時才擴容為10；
????????c.ArrayList(Collection<?extends E> c)：將c轉化為ArrayList
（2）代碼中是使用了ArrayList的帶初始化容量的構造函數，并未進行擴容。
3.如何實現數組和List之間的轉換？
（1）數組轉List：調用JDK中的工具類Arrays中的asList()方法。
（2）List轉數組：調用List類中的toArray()方法。若toArray()方法不傳參，則返回一個Object數組；若傳入一個已經初始化長度的數組，則將List中的數據存到該數組并返回該數組。
4.通過Arrays.asList()將數組轉List后，若修改數組內容，List會受影響嗎？
（1）asList()的實現原理是通過Arrays類中的一個內部類ArrayList來將數組包裝成一個ArrayList；
（2）asList()方法會將ArrayList中的數組指向傳入的數組，再將ArrayList對象返回，以此來實現將數組轉化成List。
（3）這個指向是一個引用傳遞，ArrayList的數組和傳入的數組指向同一塊地址，因此修改數組內容，List會受影響。
5.ArrayList 和 Arrays類的內部類Arrays.ArrayList的區別
（1）add方法
? ? ? ? a.ArrayList和Arrays.ArrayList都繼承了抽象類AbstractList；
? ? ? ? b.AbstractList中的add()方法默認為若子類未重寫該方法，則使用時會拋出UnsupportedOperationException異常
? ? ? ? c.ArrayList重寫了add()方法，可以有添加元素操作
? ? ? ? d.Arrays.ArrayList未重寫add()方法，無法添加元素
******e.由于Arrays.asList()返回的是Arrays.ArrayList對象，因此通過這種方式將數組轉成的List是無法添加元素的。
（2）構造參數為數組或集合時
? ? ? ? a.ArrayList只能接收Collection
? ? ? ? b.Arrays.ArrayList能接收數組E[]
6.通過List類的toArray()將List轉成數組后，若修改List內容，數組會受影響嗎？
不會受影響，toArray()的實現原理是將List中的數組進行拷貝，并返回一個新數組對象。返回的數組與List中的數組不指向同一塊地址，因此互不影響。
7.ArrayList和LinkedList的區別是什么？
1.底層數據結構
（1）ArrayList底層是用動態的數組實現的
（2）LinkedList底層是用雙向鏈表實現的
2.操作數據的效率不同
（1）查
? ? ? ? a.已知索引的情況下，ArrayList根據尋址公式查找，效率是O(1)；LnkedList是遍歷查找，效率是O(n)。
? ? ? ? b.未知索引的情況下，ArrayList和LinkedList都是遍歷查找，效率都是O(n)。
（2）增刪
? ? ? ? a.ArrayList進行尾部增刪效率是O(1)，其他位置的增刪都需要挪動數組，效率是O(n)。
? ? ? ? b.LinkedList進行頭尾增刪效率是O(1)，其他位置的增刪都需要遍歷鏈表，效率是O(n)。
3.內存空間占用
（1）ArrayList底層是數組，在內存中是連續存儲的，節省內存空間。
（2）LinkedList底層是雙向鏈表，在內存中是離散存儲的，還需額外存儲前后兩個節點的地址，更占用內存空間
4.線程安全
ArrayList和LinkedList都是線程不安全的，若要保證線程安全，有兩種方案：
（1）在方法內定義使用，對于局部變量是線程安全的。
（2）使用Collections.synchronizedList(new ArrayList<>())或Collections.synchronizedList(new LinkedList<>())構建線程安全的List，該方法就是創建加了synchronized鎖的List，線程安全但操作性能下降。
)
