0

我想了解数组和链表。如果您尝试对数组和链表中的元素进行排序，这会更快。哪个列表索引是更快的数组或链表？如果我们尝试从数组和链表中找到一个元素，那么最后一件事会花费更少的时间来找到相应的元素？我对数组和链表知之甚少。如果我错了，请纠正我。数组是固定大小和连续的内存数据结构。而链表不是固定大小的。

4

3 回答 3

0

ArrayList表示为一个数组，但是 ArrayList 类可以做所有事情，包括调整数组大小，因此您不必关心大小。

Add to end : constant time
Add to else : linear time (average is n/2 = O(n))
Get : constant
Delete : same as add

LinkedList表示为链表。这意味着链表的每个部分都可以访问下一部分和之前的部分。

Add to anywhere : constant time
Delete from anywhere : constant time
Get : linear time (average is n/2 = O(n))

但两者都是列表，这意味着它们不是固定的。唯一的区别是当您使用它们时，与其他 List 实现相比，某些方法比其他方法更快/更慢。

于 2013-10-17T11:41:09.727 回答
0

数组对于所有这些操作都更快。只有当您需要删除或添加元素时，链表才会更快。但是对于固定的项目集合，数组总是更快。

于 2013-10-17T11:41:22.557 回答
0

来自 SCJP 认证书：

数组列表：

把它想象成一个可增长的数组。它为您提供快速迭代和快速随机访问。显而易见：它是一个有序集合（按索引），但没有排序。您可能想知道，从 1.4 版开始，ArrayList 现在实现了新的 RandomAccess 接口——一个标记接口（意味着它没有方法），上面写着“这个列表支持快速（通常是恒定时间）随机访问”。当您需要快速迭代但不太可能进行大量插入和删除时，请在 LinkedList 上选择它

链表：

LinkedList 是按索引位置排序的，就像 ArrayList 一样，只是元素之间是双向链接的。此链接为您提供了新的方法（除了您从 List 接口获得的方法）用于从开头或结尾添加和删除，这使其成为实现堆栈或队列的简单选择。请记住，LinkedList 的迭代速度可能比 ArrayList 慢，但是当您需要快速插入和删除时，它是一个不错的选择。从 Java 5 开始，LinkedList 类已得到增强，可以实现 java.util.Queue 接口。因此，它现在支持常见的队列方法：peek()、poll() 和 offer()

于 2013-10-17T11:43:30.937 回答