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。我确实学到了很多关于列表的新知识。”