List接口的實現

“如果您認為我們已經完成了 List 接口，那您就錯了。我們才剛剛開始。讓我告訴您有關 LinkedList和ArrayList集合的信息。”

“我將從 ArrayList 集合開始。”

“這是這個集合的繼承圖的樣子：”

“接口是綠色的。”

“抽像類是紫色的。”

“普通班是紅色的。”

“實線代表繼承，虛線代表接口實現。”

“這是最簡單的集合。在ArrayList中，元素存儲在一個簡單的數組中。”

“這個集合相對於陣列的主要優勢在於它的擴展能力，即它能夠根據需要增加其長度。”

“如果數組空間不足，則創建第二個更大的數組，並將第一個數組中的所有元素複製到它。然後第二個數組取代第一個，第一個被丟棄（它將被被垃圾收集器銷毀）。”

“陣法要大多少？”

“新數組的長度計算為 (3*n)/2+1，其中 n 是舊數組的長度。換句話說，如果舊數組有 100 個元素長，那麼新數組將為 300/2+1 = 151。”

“當向 ArrayList 的中間添加一個元素時，會將新元素插入位置右側的所有元素複製到右側 1 個位置，然後將新元素添加到空單元格中。”

“從中間移除一個元素時，該元素右側的所有元素都會向左複製 1 個位置。”

“你是說當你向它添加元素時，ArrayList 會變長，而當你刪除元素時，它會變短？”

“不，ArrayList 內部的數組永遠不會自行變短；但是，您可以通過調用 trimToSize () 方法強制 ArrayList 將其內部數組縮小到盡可能小的大小。 ”

“當然，我會告訴你 LinkedList。”

“這是它的繼承圖：”

“接口是綠色的。”

“抽像類是紫色的。”

“普通班是紅色的。”

“實線代表繼承，虛線代表接口實現。”

“如您所知，LinkedList將元素存儲為鍊錶。”

“我經常聽到，但你能告訴我那是什麼嗎？”

“當然。” “很簡單。”

“鍊錶由 a) 存儲數據和 b) 存儲對下一個和上一個元素的引用的元素組成。”

“如果這樣一個元素存儲字符串，它的類將是這樣的：”

class LinkedListElement
{
String data;
LinkedListElement next;
LinkedListElement previous;
}

“如果我們使用通用類型聲明，那麼它看起來像這樣：”

class LinkedListElement<T>
{
 T data;
 LinkedListElement<T> next;
 LinkedListElement<T> previous;
}

“說得通。”

“為了更好地理解它，讓我們編寫代碼，將 10 個元素添加到雙向鍊錶中：”

public static void main(String[] args)
{
 LinkedListElement<Integer> tail; // The tail (very last element) of the list

 for(int i = 0; i < 10; i++)
 {
  LinkedListElement<Integer> element = new LinkedListElement<Integer>();
  element.data = i;

  if (tail == null) // If the tail doesn't exist, then make our element the last element
  {
   tail = element;
  }
  else // if there is a tail, add the element
  {
   tail.next = element; // Set the next field on the tail element
   element.previous = tail; // Add a reference to the tail to the new element
   tail = element; // Make the new element the tail
  }
 }
}

“假設我們在列表中有 10 個元素。下面是如何將一個元素插入到中間：”

“已更改的鏈接突出顯示為鮮紅色。它們現在指向新元素。”

“新鏈接以亮紫色突出顯​​示。它們是新元素與其相鄰元素的鏈接。”

“現在作為代碼：”

// This field stores the element that is the head of the list
LinkedListElement<Integer> head = …

// Get the 4th element (counting from zero)
LinkedListElement<Integer> element4 = head.next.next.next.next;
// Get the 5th element
LinkedListElement<Integer> element5 = element4.next;

// Create the new element that we will insert
LinkedListElement<Integer> newElement = new LinkedListElement<Integer>();
newElement.data = -18;

// Replace the references in the element on the left
newElement.previous = element4;
element4.next = newElement;

// Replace the references in the element on the right
newElement.next = element5;
element5.previous = newElement;

“謝謝你，Ellie。我確實學到了很多關於列表的新知識。”