26

我想知道为什么LinkedList没有initialCapacity

我知道什么时候使用ArrayList,什么时候使用LinkedList

定义 Collection 最终大小的好习惯,例如:

List<String> arraylist = new ArrayList<String>(5);

例如LinkedList

List<String> linkedlist = new LinkedList<String>(); // right way

List<String> arraylist = new LinkedList<String>(5); // compilation error

有人可以阐明这个问题吗?

[编辑]

顺便说一句,我可以写

List<String> arraylist = new ArrayList<String>(5);
List<String> linkedlist = new LinkedList<String>(arraylist);
4

7 回答 7

46

LinkedList 本质上没有“容量”,因为它不会在将项目添加到列表之前为项目分配内存。LinkedList 中的每一项都包含一个指向列表中下一项的指针。

http://www.stoimen.com/blog/wp-content/uploads/2012/06/0.-Arrays-vs.-linked-list.png

事先为列表分配内存是没有意义的,因为 LinkedList 没有容量

于 2013-09-27T12:02:13.720 回答
10

它的模型不是基于数组,而是基于真正的链表,所以没有必要,而且没有意义。像你有空数组项一样有空链接没有多大意义。

于 2013-09-27T12:01:21.830 回答
3

为什么需要 LinkedList 上的容量?LinkedList 不适用于固定大小的数组。每个 LinkedListElement 都有一个指向列表中下一个元素的指针(链接!)。因此,可以在恒定时间内将元素添加到链表中。但是随机访问 List 中的元素是昂贵的。您需要遍历列表中的所有元素,直到到达目的地。

于 2013-09-27T12:02:59.443 回答
2

为什么LinkedList会有初始容量?

ArrayList由一个数组备份,所以初始容量就是数组的初始大小。LinkedList不需要那个。

于 2013-09-27T12:01:35.227 回答
1

链表不需要初始值。这就是数组和链表的主要区别。

数组将在某处结束。但链表不是。链表不适用于边界值。

于 2013-09-27T12:07:40.907 回答
1

当你声明一个数组时,你必须知道它的大小,因为指针需要在内存中创建。链表不需要这个,因为在将任何对象添加到链表之前不需要指向内存的指针。

链表被递归定义为:一个空列表和指向该空列表的元素

因此,每当您添加一个元素时,您都会在创建元素时分配内存(或者在 Java 中,编译器会这样做),然后当您将其添加到列表时,它现在指向列表(或列表中的最后一个元素指向给它)。

所以你不需要声明链表的初始大小,因为链表总是以空列表开始,当添加一个元素时它指向列表。

于 2013-09-27T12:11:53.380 回答
0

ArrayList 和 LinkedList 都有 List 接口的实现类。

ArrayList 使用 Resizable Array 或 Grow-able Array.In 数组数据结构使用连续内存分配,借助它我们可以使用索引访问数组的元素。当我们声明任何数组时,我们应该声明初始容量,因为找到用于存储数组元素的连续内存块。

LinkedList 在 Line 数据结构下使用双链表。在使用非连续内存分配并使用头尾概念访问这些元素的链表数据结构中。所以在 LinkedList 中我们不需要任何初始容量。

于 2021-03-23T02:09:46.317 回答