Java 中的動態數組

在建立不同複雜程度的程式時，每個開發人員都會使用許多資料類型，包括陣列。這種結構非常適合儲存一組單一類型，提供出色的效能，並且通常很方便。 陣列的一個顯著缺點是它們是靜態的：必須事先指定它們的大小。然而，程式設計師還不知道如何預測未來（當然，除非人工智慧能夠以驚人的速度處理資訊並能夠預測任何事件）。為此，我們創建了一個可以在程式運行時改變其大小的結構。它被稱為動態數組。

JavaRush 課程中的動態數組

這個主題在 Java 文法任務中的 JavaRush 課程的第 7 級和部分第 8 級中以非常容易理解和清晰的方式進行了介紹。在多個講座和多達 18 個問題的過程中，涵蓋了關鍵問題、動態陣列的類型以及它們之間的差異，包括效能。這個主題非常重要，因為動態數組可以緩解開發人員的憂鬱和頭痛，並節省大量時間。

什麼是動態數組？

動態數組是在程式執行過程中可以改變其大小的陣列。在Java中，這個角色主要由ArrayList和LinkedList類別來扮演。與陣列不同，ArrayList 和 LinkedList 只包含引用資料類型，即只能儲存物件。幸運的是，Java 具有自動裝箱和自動拆箱機制，可讓您在動態陣列中儲存基本類型。與靜態數組一樣，動態數組是同構的，即它可以儲存單一資料類型。然而，由於繼承機制和介面的正確使用，可以在一個動態數組中儲存從一個公共類別繼承的一系列不同的類，但下面會詳細介紹。也就是說，靜態數組的工作原理是這樣的： 而Java 中的動態數組的工作原理如下（我們從第三步繼續這個圖）： 在 Java 中，有一個特殊的原生函數用於複製數組，所以這樣的「移動」 」 不是很貴。

為什麼我們需要動態數組？

Java 中的動態陣列用於處理在編寫程式時其大小未知的同類資料集。例如，您可能希望快取目前正在使用該應用程式的每個用戶端的資料。無法提前預測此類客戶的數量。如果沒有動態數組，可以透過以下選項解決此問題：

1. 建立一個100%可能滿足需求的大數組；
2. 建立一個用作緩衝區的靜態數組；
3. 應用其他動態結構，例如集合。

第一個選項僅適用於嚴格限制範圍的情況。在其他情況下，這樣的陣列會佔用大量的記憶體空間，效率極低。第二個需要實作額外的機制來清除緩衝區、讀取等等。由於功能差異，第三種也有缺點。

Java 中的動態數組有什麼作用？

在Java 語言中，ArrayList 和LinkedList 類別充當動態陣列。最常用的是 ArrayList，因為它充當經典數組，與實現雙向鍊錶概念的 LinkedList 不同。我們稍後再討論。

ArrayList、LinkedList－概念及操作規則

ArrayList是一個經典的陣列，可以在程式執行過程中擴展。它基於常規數組：創建時其大小為 10 個元素。隨著尺寸的增加，容量也隨之增加。ArrayList 的工作規則：

• 就像靜態數組一樣，它從0開始索引；
• 末尾插入和索引訪問非常快 - O(1)；
• 要在開頭或中間插入元素，您需要將所有元素複製到右側一個單元格，然後將新元素貼到所需位置；
• 按值存取取決於元素的數量 - O(n)；
• 與經典數組不同，它可以儲存 null；

對於 LinkedList，一切都有點複雜：它是基於雙向鍊錶。也就是說，從結構上來說，這個動態Java數組是許多分散的互相引用的物件。用圖片來解釋比較容易。在 LinkedList 中，我們有一個主對象Head，它儲存有關元素數量的信息，以及指向第一個和最後一個元素的連結： 現在欄位size = 0是 ,first和last = null。新增到此清單的每個元素都是單獨內部物件的內容。讓我們新增一個元素Johnny： 現在我們有一個值為「Johnny」的節點。對於主元素，第一個和最後一個元素的連結指向新節點。該物件還具有到上一個和下一個元素的連結。到前一個元素的連結將始終為 null，因為這是第一個元素，而到下一個元素的連結將始終為 null，因為它尚不存在。讓我們解決這個問題： 新增一個值為「Watson」的新元素，它成為第二個元素。請注意，第一個元素有一個next指向下一個元素的字段，新元素有一個previous指向前一個元素的字段。對於主元素，最後一個元素的連結現在指向新節點。下圖顯示如何將元素新增至清單的中間： 新增了一個新元素「Hamish」。要將其插入到列表的中間，只需重新分配元素的連結即可，如圖所示。這些插圖解釋了頂層雙向鍊錶的過程，但沒有詳細說明。總結 LinkedList 的故事，我們可以得出其運行的幾個規則：

• 就像數組一樣，索引從0開始；
• 對第一個和最後一個元素的存取不依賴元素的數量 - O(1)；
• 透過索引取得元素，從清單中間插入或刪除取決於元素的數量 - O(n)；
• 可以使用迭代器機制：那麼插入和刪除將在常數時間內發生；
• 與經典數組不同，它可以儲存 null。

程式碼範例

讓我們來看一些例子。程式碼片段包括 ArrayList 和 LinkedList 的範例。

創建

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

新增元素

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

乍一看，add()AND方法addLast()執行相同的功能，但方法add()是從介面來到 LinkedList List，而方法addLast又來自介面Deque。LinkedList 實作了這兩個介面。在這種情況下，一個好的做法是使用最適合上下文的方法。如果LinkedList用作佇列，那麼最好使用addLast. 如果 LinkedList 用作列表，則使用add().

刪除一個元素

// Удаление element по индексу
arrayList.remove(0);
// Удаление element по значению
arrayList.remove("Johnny");

// Удаление первого element в списке
linkedList.removeFirst();
// Удаление первого element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего element в списке
linkedList.removeLast();
// Удаление первого вхождения element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

如果按索引刪除對象，則此方法傳回已刪除的對象。如果按值刪除物件（或刪除 LinkedList 的第一個或最後一個元素），則如果找到並刪除該對象，則該方法將傳回true ，否則傳回 false。

訪問元素並蒐索列表

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего element
String lastLinkedElement = linkedList.getLast();

// Поиск element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

繞圈行走

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

這裡值得多說幾句關於搜尋的事情。許多新手開發人員在搜尋清單中的元素時，會在循環中開始搜索，將所有元素與搜尋到的元素進行比較，儘管存在方法indexOf()和lastIndexOf()。您也可以使用該方法contains()來獲取元素在列表中的事實：

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

進一步閱讀的鏈接

1. 這裡有一篇關於從 ArrayList 中刪除元素的優秀文章。由於這是一個動態 Java 數組，因此刪除元素有很多微妙之處。
2. 此處詳細說明了 ArrayList 的工作原理。
3. 有關 LinkedList 的更多資訊。
4. Habr 的幾篇關於ArrayList和LinkedList的文章。