我使用了很多列表和数组,但我还没有遇到一个场景,数组列表不能像链表一样容易使用,如果不是更容易的话。我希望有人能给我一些例子,说明什么时候链表明显更好。


当前回答

数组具有O(1)随机访问,但是向数组中添加或删除内容的代价非常高。

链表在任何地方添加或删除项目和迭代都非常便宜,但随机访问是O(n)。

其他回答

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

数组列表适用于写一次读多次或追加程序,但不适用于从前面或中间进行添加/删除。

嗯,我猜数组列表可以用在以下情况下:

您无法确定将会出现多少个元素 但是您需要通过索引随机访问所有元素

例如,您需要导入并访问联系人列表中的所有元素(您不知道其大小)

数组具有O(1)随机访问,但是向数组中添加或删除内容的代价非常高。

链表在任何地方添加或删除项目和迭代都非常便宜,但随机访问是O(n)。

我认为主要的区别在于你是否经常需要从列表顶部插入或删除内容。

对于一个数组,如果你从列表的顶部移除一些东西复杂度是o(n)因为数组元素的所有下标都要移位。

对于链表,它是o(1),因为您只需要创建节点,重新分配头,并将对next的引用分配为前一个头。

当经常在列表的末尾插入或删除时,数组是更可取的,因为复杂度将是o(1),不需要重新索引,但对于链表,它将是o(n),因为你需要从头到最后一个节点。

我认为在链表和数组中搜索都是o(log n)因为你可能会使用二分搜索。

使用链表对数组和多项式操作进行基数排序。