本文將詳細介紹 Collections Framework 中的 ArrayList 類,該類可能是最容易理解的,因為它是基於常規數組。在面試中你幾乎肯定會被問到關於這個類別及其在 Java 中的實現的問題。在第二部分中,我們將分析其餘方法並編寫我們自己的數字動態數組的實作。ArrayList類別繼承自AbstractList類,並實作了以下介面:List、RandomAccess、Cloneable、Serializable。 ArrayList類別詳細分析[第2部分] ArrayList類別支援動態數組,可依需求進行擴充。它的必要性和有效性是透過以下事實來解釋的:常規數組具有固定長度:一旦創建,它就不能增長或收縮,如果不知道需要多大的數組,就會施加限制。本質上,ArrayList 類別是物件引用的可變長度清單陣列。重要的是要理解,當從內部數組中刪除元素時,內部數組的大小(單元數)不會自動減小。
因此,當在索引處插入元素並且數組中沒有可用空間時,呼叫
您也可以使用 為我們的集合新增元素
讓我們嘗試從下面的陣列中刪除索引 3 處的元素:
讓我們考慮該方法的第二個版本:
刪除不屬於傳遞集合的元素:
假設我們有一個集合:
更換元件
檢查集合中的元素:
size
事實上,表示數組中實際存在的元素數量的變數 的值減少了。假設我們建立 ArrayList 類別的新物件並向其新增 5 個元素。預設情況下,建立一個包含 10 個元素的陣列。在這種情況下,我們物件的所謂容量(大小/體積)將等於 10,但變數的值size
將等於 5。當我們刪除元素時,我們會看到變數值的變化size
,因為我們.length
無法存取 ArrayList 類別的內部陣列並找出它的長度。可以使用另一種方法來減小尺寸trimToSize()
,這將在下面討論。讓我們看看類別欄位。
-
負責動態數組預設體積的欄位:
private static final int DEFAULT_CAPACITY = 10
當建立一個新物件new ArrayList<>()(不含參數的建構子)時,內部會建立一個包含10個元素的陣列。
-
儲存集合所有元素的欄位:
transient Object[] elementData
用關鍵字標記
transient
- 使用標準序列化演算法時,該欄位不會寫入位元組流。值得注意的是,該欄位沒有用關鍵字 標記private
,但這樣做是為了方便從嵌套類別(例如 SubList)存取該欄位。 - 一個計數器字段,用於儲存數組中實際元素的數量:
private int size
當執行插入和刪除等操作時,該值會遞增/遞減。
public ArrayList()
– 建立一個包含 10 個元素的空列表陣列;public ArrayList(Collection < ? extends E > c)
– 建立一個清單數組,並使用傳遞的集合中的元素進行初始化(如果我們想要基於某個集合建立新的 ArrayList);public ArrayList(int initialCapacity)
– 建立一個具有初始容量的清單陣列。如果傳遞的參數initialCapacity大於0,則建立指定大小的陣列(內部欄位elementData被指派一個指向大小為initialCapacity的Object類型的新陣列的連結)。如果參數為 0,則建立一個空數組。如果指定的參數小於 0,則拋出 IllegalArgumentException。
List < String> list = new ArrayList<>();
新建立的物件list
包含屬性(欄位)elementData
和size
。在我們的例子中,值儲存elementData
只不過是特定類型的陣列(在通用 - 中指定<>
)String[]
。如果呼叫不帶參數的建構函數,則預設會建立一個包含 10 個 Object 類型元素的陣列(當然,會強制轉換為該類型)。 新增元素 傳統上,向列表數組添加元素是使用add()
.
public boolean add(E элемент)
好吧,讓我們加入: list.add("0");
在這個方法中,呼叫該方法的重載版本add()
,標記為private
,它又將三個參數作為輸入:要新增的元素、內部陣列及其大小。在私有方法中,會進行一次檢查:如果傳遞的 size 參數等於內部數組的長度(即數組已滿),則將方法的結果(字段的grow(int minCapacity)
當前值)賦給數組size + 1 傳遞給該方法,因為有必要考慮要添加的元素),其中為數組內部分配一個指向透過複製原始數組的元素獲得的新創建數組的連結:
Arrays.copyOf(elementData, newCapacity(minCapacity))
作為該方法的第二個參數,copyOf
我們指示方法的結果newCapacity(int minCapacity)
,其中計算新的陣列大小。它使用以下公式計算: int newCapacity = oldCapacity + (oldCapacity >> 1)
對於具有預設大小的數組,以下情況成立: >> 1
– 位元右移一位(將數字減少到一半的運算子)。本質上,它的意思是除以2 的1 次方。事實證明,我們將10 除以2 並加上10。總計,數組的新容量為15,但由於我們要添加第11 個元素,因此15 + 1 = 16. 讓我們回到列表,假設我們已經向其中添加了 10 個元素,並嘗試添加 11。檢查將顯示數組中沒有空間。相應地,建立並呼叫一個新數組Arrays.copyOf
,該數組內部使用系統方法System.arraycopy()
。 或者,這裡是 JavaRush 上一篇文章中的一個清晰示例: 在完成所有這些檢查並在必要時增加數組的大小之後,然後在私有方法中,add()
將一個新元素添加到數組的末尾,並將當前參數size
增加 1 。舊數組隨後將由垃圾收集器處理。這就是動態數組的工作原理:當我們添加元素時,我們檢查其中是否還有空間。如果有空間,那麼我們只需將元素添加到數組的末尾即可。結束並不意味著數組中的最後一個單元格,而是與值 對應的單元格size
。我們將第一個元素加入到陣列中;它被放置在索引為 [0] 的儲存格中。字段值size
增加了 1 並且 = 1。我們添加下一個元素:我們看到size = 1
,因此我們將該元素放置在索引為 [1] 的單元格中,依此類推。該方法有一個帶有兩個參數的重載版本:
public void add(int index, E element)
我們可以指定要新增元素的儲存格的位置(索引)。首先,檢查指定索引值的正確性,因為有可能指定不正確的索引,該索引將指向不存在或根本不存在的儲存格。檢查索引:index > size || index < 0
– 如果指定的索引大於陣列的目前大小或小於 0,則拋出例外IndexOutOfBoundsException
。然後,如有必要,增加數組的大小,類似於上面的範例。您可能聽說過,在陣列中進行新增/刪除操作期間,某些內容會移到某處(向右或向左)。因此,移位是透過複製數組來執行的: System.arraycopy(elementData, index, elementData, index + 1, s - index);
位於指定索引右側的所有元素將向右移動一位(索引+1)。並且只有在此之後,才會將新元素新增到內部數組的指定索引處。由於我們已將數組的一部分向右移動了一位(未建立新數組),因此我們需要的單元格將可以自由寫入。舊數組的連結被刪除,將來它將被垃圾收集器接管。將「maserati」貼到已被佔用的儲存格 [3] 中:
System.arraycopy()
將發生兩次:第一次在 中grow()
,第二次在方法本身中add(index, value)
,這顯然會影響整個添加操作的速度。因此,當需要向內部數組寫入另一個元素,但那裡沒有空間時,ArrayList 內部會發生以下情況:
- 建立一個新數組,其大小是原始數組的 1.5 倍,再加上一個元素。
- 舊數組中的所有元素都會複製到新數組
- 新數組儲存在ArrayList物件的內部變數中,舊數組被宣告為垃圾。
public void ensureCapacity(int minCapacity)
透過提前增加陣列容量,您可以避免以後額外重新分配 RAM。此方法增加內部陣列的大小以容納傳遞給 的元素數量minCapacity
。此方法ensureCapacity()
不影響字段size
,它影響capacity
內部數組(的大小)。我再次強調,size
兩者是capacity
不同的東西,不要混淆它們非常重要!如果要將建構 ArrayList 的基礎數組的大小減少到當前實際儲存的元素數,則應該呼叫trimToSize()
. 從集合中移除元素後,size()
會顯示實際存在的元素數量,並且capacity
不會減少!假設:我們輸入了 100 個元素,刪除了前 50 個,size
它會變成 50,所以capacity
它仍然是 100。為了減少 和capacity
,我們需要使用 方法trimToSize()
,它將我們的整個容量調整為當前大小。怎麼樣?複製我們的數組,以便不留任何空白單元格(新數組的長度只是等於大小字段)。
addAll
。
public boolean addAll(Collection< ? extends E> c)
public boolean addAll(int index, Collection< ? extends E> collection);
第一個選項可讓您將方法參數中指定的集合(例如另一個工作表)中的所有元素新增至為其進行方法呼叫的原始集合(在末尾插入)。傳遞的集合(也可以是集合)使用toArray()
. 當然,加法操作也是利用複製來進行的。第二個是將所有元素添加collection
到清單中,從索引開始index
。在這種情況下,所有元素都會向右移動清單中元素的數量collection
。刪除元素 首先,讓我們來看看從 ArrayList 中刪除元素的經典選項。
public E remove(int index)
依索引執行刪除,並將所有後續(指定索引處的元素之後)元素向左移動,從而關閉「洞」。它還會傳回已刪除的元素 (E),該元素在刪除之前已寫入附加變量,我們透過方法呼叫來獲得該變數的值。要理解 E 是什麼,您需要熟悉所謂的泛型類型。符號 E 表示該方法傳回建立 ArrayList 物件時指定的資料類型(記住:List <String> list
因此,在這種情況下,E 將被「取代」String
)。為了獲得一般性的理解,我強烈建議您熟悉泛型類型。檢查輸入索引的正確性,然後在方法內部,元素並沒有完全刪除,而是呼叫了一個私有方法fastRemove(Object[] es, int i)
,其中已經發生了刪除。我們將數組和指定的索引作為輸入傳遞給該方法。使用 複製元素System.arraycopy()
,減少陣列的大小,然後將 null 指派給最後一個元素。值得注意的是,並沒有創建一個新數組: System.arraycopy(es, i + 1, es, i, size - 1 - i);
指定索引(i+1)下位置右側的部分被複製到我們的原始數組(es)中,並且從該位置開始定位(i) 要刪除的元素所在的位置。因此,我們向左移動並刪除了元素。
public boolean remove(Object o)
此方法從清單中刪除傳遞的元素o
,或更準確地說,從指定連結處的物件中刪除。如果清單中存在某個元素,則該元素將被刪除,並且所有元素都會向左移動。如果清單中存在該元素並且已成功刪除,則該方法傳回 true;否則傳回 false。與按索引刪除的選項類似,請呼叫該方法fastRemove()
,其中發生完全相同的操作。不同的是,該方法額外透過Object類別的remove(Object o)
方法來搜尋所需的物件。equals()
當按值刪除時,循環將遍歷清單中的所有元素,直到找到匹配項。只有找到的第一個元素才會被刪除。讓我們總結一下:從動態數組中刪除元素時,不會像常規數組那樣留下空洞(刪除的單元格不會為空)。所有後續元素(位於索引右側)均向左移動一位。還有幾種附加方法可用於不同程度地從清單中刪除元素。讓我們簡單地看一下它們。清理我們的收藏:
public void clear()
一個簡單的循環for
迭代數組的所有元素,為每個元素分配 null。您可以從我們的集合中刪除包含在另一個傳輸的集合中的那些元素,如下所示:
public boolean removeAll(Collection< ?> c)
如果您需要刪除多個元素,您可能不應該在條件循環中執行此操作:使用該方法更方便、更安全removeAll()
。它接受將從清單中刪除的元素的集合。此集合必須包含與目標清單儲存類型相同的元素。否則就會被丟掉ClassCastException
。如果清單因方法呼叫而更改,則該方法將傳回 true。
public boolean retainAll(Collection< ?> c)
List< String> listFirst = new ArrayList<>();
listFirst.add("White");
listFirst.add("Black");
listFirst.add("Red");
第二個:
List< String> listSecond = new ArrayList<>();
listSecond.add("Green");
listSecond.add("Red");
listSecond.add("White");
然後listSecond.retainAll(listFirst)
之後listSecond
會留下:
"White"
"Red"
由於“綠色”被刪除,它不在listFirst
. 但之後listSecond.removeAll(listFirst)
它將listSecond
保持:
"Green"
Удалorсь все элементы, которые есть в listFirst.
不屬於傳遞的集合 - 意味著如果有元素不在傳遞的集合中,那麼您需要從第一個(應用該方法的)元素中刪除它們。屬於轉移的集合 - 因此,如果第一個和第二個(轉移的)集合中都有一個元素,則第一個集合中的重複項將被銷毀。
protected void removeRange(int fromIndex, int toIndex)
從清單中刪除起始指定索引(包含)和結束指定索引(不包含)之間的所有元素。值得注意的是,該方法不能直接在 ArrayList 物件上呼叫。要使用它,您需要繼承自AbstractList/ArrayList
. 該方法也被另一個方法(subList,稍後討論)使用。
public boolean removeIf(Predicate< ? super E> filter)
根據給定謂詞從集合中刪除元素。謂詞本身是一個特定的函數/演算法/條件,根據該函數/演算法/條件將刪除與給定條件相對應的一個或多個元素。Predicate
— 函數式介面(僅包含一個方法,因此可以用作 lambda),其工作原理是「接收一個參數 - 傳回布林值」。本質上,該方法重寫了介面的實作Collection
並實現了以下“策略”:它迭代元素並標記那些與我們的Predicate
;相符的元素。然後第二次運行以刪除(並移動)在第一次迭代中標記的元素。讓我們實作一個接口Predicate
,如果兩個物件相等則返回 true:
class SamplePredicate< T> implements Predicate< T>{
T varc1;
public boolean test(T varc){
if(varc1.equals(varc)){
return true;
}
return false;
}
}
在另一個類別中,讓我們建立一個 ArrayListString
和我們的類別的一個對象,該物件實作Predicate
:
ArrayList< String> color_list = new ArrayList<> ();
SamplePredicate< String> filter = new SamplePredicate<> ();
varc1
讓我們將值「White」 寫入 變數:
filter.varc1 = "White";
讓我們在列表中添加幾行:
color_list.add("White");
color_list.add("Black");
color_list.add("Red");
color_list.add("White");
color_list.add("Yellow");
color_list.add("White");
讓我們執行 list 上的方法removeIf
,我們將帶有條件的物件傳遞給該方法:
color_list.removeIf(filter);
結果,所有值為「White」的行都將從清單中刪除,因為我們的「謂詞」會比較它們是否相等。最終列表:[黑、紅、黃]。
public E set(int index, E element)
將指定位置的元素替換index
為傳遞的元素element
。索引也必須大於零且小於最後一個元素的索引,否則會拋出異常IndexOutOfBoundsException
。不會出現內部陣列的副本。簡單地說,插入一個新元素,而不是指定索引處的元素,即 覆蓋該值。
public void replaceAll(UnaryOperator<e> operator)
更改集合的所有元素(可能有條件)。主要與lambda或匿名類別結合使用(但為了清楚起見,在範例中我們將簡單地使用實作介面的類別)來實作介面UnaryOperator
並定義其方法。我們來實作一下這個介面:
class MyOperator< T> implements UnaryOperator< T>{
T varc1;
public T apply(T varc){
return varc1;
}
}
在另一個類別中,讓我們建立一個 ArrayListString
和我們的類別的一個對象,該物件實作UnaryOperator
:
ArrayList< String> color_list = new ArrayList<> ();
MyOperator< String> operator = new MyOperator<> ();
varc1
讓我們將值「White」 寫入 變數:
operator.varc1 = "White";
讓我們在列表中添加幾行:
color_list.add("White");
color_list.add("Black");
color_list.add("Red");
color_list.add("White");
color_list.add("Yellow");
color_list.add("White");
讓我們在列表上執行一個方法,replaceAll
我們將向其傳遞物件operator
:
color_list.replaceAll(operator);
結果,清單中的所有值都被替換為「白色」:[白色,白色,白色,白色,白色,白色]。例如,您可以透過以下方式從集合中的字串中刪除所有空格:
ArrayList< String> list = new ArrayList<>(Arrays.asList("A ", " B ", "C"));
list.replaceAll(String::trim);
其他方法:可以使用以下方法將ArrayList列表數組轉換為常規數組:
public Object[] toArray()
或者
public < T> T[] toArray(T[] a)
- 這裡返回數組的類型是在runtime
該方法中確定的,並且將允許:
- 加快某些操作的速度;
- 將數組作為參數傳遞給未重載的方法以直接接受集合;
- 將新的基於集合的代碼與無法識別集合的舊代碼整合。
public Object clone()
請注意,該方法clone()
傳回 Object 類型,因此呼叫它後您需要轉換為所需的類別。克隆創建一個新的獨立物件。檢查集合中是否存在物件:
public boolean contains(Object o)
檢查清單中是否存在物件(內部使用 Object 類別的 equals 方法,即比較引用),根據結果傳回 true/false。除了通常的循環之外,您還可以使用以下方法迭代(存取每個元素,以及執行某些操作)集合:
public void forEach(Consumer< ? super E> action)
這是我們顯示列表的方式:
List< Integer> numbers = new ArrayList<>(Arrays.asList(10, 20, 50, 100, -5));
numbers.forEach((number)-> System.out.println(number));
如果不使用 lambda,您需要使用匿名類別並重寫accept
介面方法Consumer
:
numbers.forEach(new Consumer< Integer>() {
@Override
public void accept(Integer integer) {
System.out.println(integer);
}
});
透過索引獲取元素:
public E get(int index)
用於隨機存取集合元素。傳回位於清單中指定索引處的元素。如果index < 0
or 是index >=
清單中元素的最大數量,則會拋出異常IndexOutOfBoundsException
。這是從清單中檢索元素的基本方法,無論 ArrayList 的大小如何,透過索引檢索元素的時間將始終相同,因為它正在存取特定的陣列單元格。尋找指定物件的索引:
public int indexOf(Object o);
public int lastIndexOf(Object o);
這些方法傳回清單中第一個(第一次遇到給定物件時)或最後一次出現(最後一次遇到給定物件時)元素的索引。如果清單中不存在該元素,則該方法將傳回 -1。
public boolean isEmpty();
如果清單為空(查看欄位是否相等size 0
),則此方法傳回 true,否則傳回 false。如果清單僅包含 null 元素,則方法將傳回 false。換句話說,此方法也考慮了 null 元素。找出列表中元素的數量:
public int size();
傳回清單中的元素數量(大小欄位值)。元素的數量可能與清單容量(capacity)不同。取得列表的迭代器:
public Iterator< E> iterator();
傳回清單的迭代器,以便稍後在循環或任何其他處理中使用。迭代器實作快速失敗行為。如果它運行整個集合並注意到對其進行了一些修改(不是使用迭代器方法獲得的),它會立即拋出異常ConcurrentModificationException
。迭代器有一個叫做 的東西modification count
。當迭代器在每個之後迭代集合時next/hasNext/remove
,它會檢查此計數器。如果它與迭代器期望看到的不匹配,則會拋出異常。我不會在這裡詳細討論迭代器。
public ListIterator< E> listIterator() и public ListIterator< E> listIterator(int index)
傳回清單的清單迭代器,以便稍後在循環或任何其他處理中使用。此介面擴展了列表的雙向遍歷和其元素修改的ListIterator
介面。Iterator
在重載版本中,您可以傳遞「遍歷」開始的索引。本範例中的索引表示方法將開始其工作的第一個元素next()
,並且當呼叫該方法時,previous()
將從索引「passed index - 1」下的元素開始遍歷。
public Spliterator <E> spliterator()
Java 8 引進了一種新型的後期綁定和快速失敗迭代器,稱為分隔符號迭代器。分隔符號迭代器允許您迭代元素序列,但它們的使用方式不同。Spliterator介面最重要的特性是它能夠支援元素序列的各個部分的平行迭代,從而支援並行程式設計。
GO TO FULL VERSION