List集合的特有方法

• 方法介紹

  方法名	描述
  void add(int index,E element)	在此集合中的指定位置插入指定的元素
  E remove(int index)	刪除指定索引處的元素，返回被刪除的元素
  E set(int index,E element)	修改指定索引處的元素，返回被修改的元素
  E get(int index)	返回指定索引處的元素

list中的5種遍歷方式

細節點注意：

List系列集合中的兩個刪除的方法

?1.直接刪除元素2.通過索引進行刪除

代碼示例:

?List<Integer> list = new ArrayList<>();?list.add(1);list.add(2);list.add(3);?//此方法刪除的是1索引上的元素list.remove(1);?//此方法刪除的是真正的1這個元素Integer i = Integer.valueOf(1);list.remove(i);

ArrayList與數組的區別

• 數組聲明了它容納的元素的類型，而集合不聲明。這是由于集合以object形式來存儲它們的元素。

• 一個數組實例具有固定的大小，不能伸縮。集合則可根據需要動態改變大小。

ArrayList和LinkedList簡介

以下內容為查詢結果

ArrayList底層是數組，查詢快、增刪慢；LinkedList底層是鏈表，查詢慢、增刪快；

ArrayList底層是數組，存儲空間是連續的，可以根據尋址方式直接找到對應的元素位置，時間復雜度是O(1)。

舉例來說：在一條街上，第一家店是001號，那么005號在第五間：

但LinkedList底層是鏈表，存儲空間不連續，需要通過指針關聯，在查詢過程中需要不斷跳轉新的地址：

這也是ArrayList比LinkedList查詢快的原因。

Java中的原生的數組是不能擴容的，如果初始化時申請了5個元素空間，那么就最多能存5個元素。ArrayList底層也是數組，但是支持動態擴容，所以ArrayList是動態數組：

假設原始容量為5，那么插入新元素時就會擴容，元素拷貝等耗時操作，這就是ArrayList增刪慢的原因。但是ArrayList增刪元素必然會懲罰擴容和拷貝嗎？

插入同理，尾部插入時不涉及元素拷貝。

LinkedList中，理想狀態下，鏈表的增刪操作時間復雜度為O(1):

LinkedList集合的特有功能

• 特有方法

  方法名	說明
  public void addFirst(E e)	在該列表開頭插入指定的元素
  public void addLast(E e)	將指定的元素追加到此列表的末尾
  public E getFirst()	返回此列表中的第一個元素
  public E getLast()	返回此列表中的最后一個元素
  public E removeFirst()	從此列表中刪除并返回第一個元素
  public E removeLast()	從此列表中刪除并返回最后一個元素

問題

1 ArrayList如何添加元素？

• 擴容：往ArryList中添加元素的時候，會首先檢查是否需要擴容。當size == elementData.length時，表示數據數量已經超過了數組容量，需要擴容，擴容后的數組的長度為原來數組長度的1.5倍；

• 復制：當擴容檢查完畢后，如果添加的元素不在數組尾部，則將索引后面的元素通過System.arraycopy往后移動一位；

• 賦值：將值賦給數組中的對應索引，并將size++；

如果此時ArrayList的長度為size，在多線程運行的情況下，線程A想要將元素存放在索引為index的位置上，但此時CPU暫停線程A的調度，線程B得到運行的機會，也是向index的位置上添加元素。之后線程A和線程B都繼續運行，都會增加size的值，這樣數組的長度就變成了size + 2，這樣就線程不安全了。

2 ArrayList是否能無限添加元素？會拋出異常嗎？

可以無限添加，不會拋出異常。ArrayList會自動為其擴容，擴容后的大小是int newCapacity = (oldCapacity * 3) / 2 + 1。

3 ArrayList和LinkedList的時間復雜度？

ArrayList是線性表（數組）：

add(E e)：在數組尾部添加元素，時間復雜度為O(1)； add(int index, E element)：在索引為index的位置添加元素，需要后面的元素后移，時間復雜度為O(n)； remove(int index)/remove(Object o)：刪除元素，需要后面的元素后移，時間復雜度為O(n)； set(int index, E element)：修改元素，時間復雜度為O(1)； get(int index)：獲取索引為index的元素，時間復雜度為O(1)； LinkedList是鏈表操作：

add(E e)：在數組尾部添加元素，時間復雜度為O(1)； add(int index, E element)：在索引為index的位置添加元素，指針指向操作，時間復雜度為O(1)； remove(int index)/remove(Object o)：刪除元素，指針指向操作，時間復雜度為O(1) set(int index, E element)：修改元素，時間復雜度為O(n)； get(int index)：獲取索引為index的元素，時間復雜度為O(n)；

4 ArrayList線程安全嗎？為什么？如何解決多線程問題？

ArrayList線程不安全，因為相關的操作方法沒有做同步，操作沒有原子性，在多線程環境下會出現變量的讀寫異常。比如size++是非原子性的，如果兩個線程同時執行，兩個線程分別讀了size的值，再分別執行size++，最后size的值變成了size + 1而不是size + 2。

多線程環境下使用CopyOnWriteArrayList保證線程安全，活著使用Collections.synchronizedList(list)，或者給多線程的操作加鎖，或者使用Vector。