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


当前回答

如果您需要在中间插入项,并且不想开始调整数组大小和移动内容,则列表的优势就会显现出来。

你是对的,通常情况下并非如此。我遇到过一些非常具体的案例,但不是很多。

其他回答

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

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

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

如果您需要在中间插入项,并且不想开始调整数组大小和移动内容,则列表的优势就会显现出来。

你是对的,通常情况下并非如此。我遇到过一些非常具体的案例,但不是很多。

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

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

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

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

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

1)如上所述,与ArrayList(O(n))相比,在LinkedList中插入和删除操作具有良好的性能(O(1))。因此,如果应用程序需要频繁的添加和删除,那么LinkedList是最好的选择。

2)搜索(get方法)操作在Arraylist (O(1))中是快速的,但在LinkedList (O(n))中不是,所以如果有更少的添加和删除操作和更多的搜索操作要求,Arraylist将是你最好的选择。

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