“如果您认为我们已经完成了 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<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。我确实学到了很多关于列表的新知识。”