我使用了很多列表和数组,但我还没有遇到一个场景,数组列表不能像链表一样容易使用,如果不是更容易的话。我希望有人能给我一些例子,说明什么时候链表明显更好。
当前回答
嗯,我猜数组列表可以用在以下情况下:
您无法确定将会出现多少个元素 但是您需要通过索引随机访问所有元素
例如,您需要导入并访问联系人列表中的所有元素(您不知道其大小)
其他回答
To add to the other answers, most array list implementations reserve extra capacity at the end of the list so that new elements can be added to the end of the list in O(1) time. When the capacity of an array list is exceeded, a new, larger array is allocated internally, and all the old elements are copied over. Usually, the new array is double the size of the old one. This means that on average, adding new elements to the end of an array list is an O(1) operation in these implementations. So even if you don't know the number of elements in advance, an array list may still be faster than a linked list for adding elements, as long as you are adding them at the end. Obviously, inserting new elements at arbitrary locations in an array list is still an O(n) operation.
访问数组列表中的元素也比访问链表快,即使访问是顺序的。这是因为数组元素存储在连续的内存中,可以很容易地缓存。链表节点可能分散在许多不同的页面上。
如果知道要在任意位置插入或删除项,我建议只使用链表。数组列表在其他方面会更快。
这完全取决于你在迭代时所做的操作类型,所有数据结构都在时间和内存之间进行权衡,我们应该根据需要选择正确的DS。有些情况下,LinkedList比数组快,反之亦然。考虑数据结构上的三个基本操作。
搜索
由于array是基于索引的数据结构,搜索array.get(index)将花费O(1)时间,而linkedlist不是索引DS,因此您将需要遍历到index,其中index <=n, n是链表的大小,因此array在随机访问元素时比链表更快。
那么,这背后有什么好处呢?
As Arrays are contiguous memory blocks, large chunks of them will be loaded into the cache upon first access this makes it comparatively quick to access remaining elements of the array,as much as we access the elements in array locality of reference also increases thus less catch misses, Cache locality refers to the operations being in the cache and thus execute much faster as compared to in memory,basically In array we maximize the chances of sequential element access being in the cache. While Linked lists aren't necessarily in contiguous blocks of memory, there's no guarantee that items which appear sequentially in the list are actually arranged near each-other in memory, this means fewer cache hits e.g. more cache misses because we need to read from memory for every access of linked list element which increases the time it takes to access them and degraded performance so if we are doing more random access operation aka searching , array will be fast as explained below.
插入
这是简单和快速的LinkedList的插入是O(1)操作在LinkedList (Java)阵列相比,考虑数组充满的情况下,我们需要将内容复制到新数组如果数组完全使一个元素插入ArrayList O (n)在坏的情况下,而ArrayList还需要更新其指数年底如果你插入一些除了数组,链表的我们不必调整它,你只需要更新指针。
删除
它的工作原理类似于插入,在LinkedList中比在array中更好。
到目前为止,数组是使用最广泛的数据结构。然而,链表以其独特的方式被证明是有用的,而数组是笨拙的——或者至少可以说是昂贵的。
链表在大小可变的情况下,对于实现堆栈和队列非常有用。链表中的每个节点都可以被推送或弹出,而不会影响大多数节点。在中间插入/删除节点也是如此。然而,在数组中,所有元素都必须移动,这在执行时间方面是一项昂贵的工作。
二叉树、二叉搜索树、哈希表和try是其中的一些数据结构——至少在C语言中——你需要链表作为构建它们的基本成分。
但是,在期望链表能够通过其索引调用任何任意元素的情况下,应该避免使用链表。
使用链表对数组和多项式操作进行基数排序。
我做了一些基准测试,发现list类实际上比LinkedList随机插入更快:
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int count = 20000;
Random rand = new Random(12345);
Stopwatch watch = Stopwatch.StartNew();
LinkedList<int> ll = new LinkedList<int>();
ll.AddLast(0);
for (int i = 1; i < count; i++)
{
ll.AddBefore(ll.Find(rand.Next(i)),i);
}
Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);
watch = Stopwatch.StartNew();
List<int> list = new List<int>();
list.Add(0);
for (int i = 1; i < count; i++)
{
list.Insert(list.IndexOf(rand.Next(i)), i);
}
Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);
Console.ReadLine();
}
}
}
链表需要900毫秒,列表类需要100毫秒。
它创建后续整数的列表。每个新的整数被插入到一个已经在列表中的随机数之后。 也许List类使用了比数组更好的东西。
推荐文章
- 在每个列表元素上调用int()函数?
- 将Set<T>转换为List<T>的最简洁的方法
- Java 8流和数组操作
- 在Python中插入列表的第一个位置
- 在javascript中从平面数组构建树数组
- 在bash中传递数组作为参数
- Python数据结构按字母顺序排序
- 如何在c++中初始化一个向量
- 用any可以吗?'来检查数组是否为空?
- 如何获得字典中的键列表?
- 为什么我们使用数组而不是其他数据结构?
- 我如何在JavaScript压缩两个数组?
- 如何在列表中找到最大值的所有位置?
- console.log(result)输出[object对象]。我如何得到result。name?
- Java 8流反向顺序