我使用了很多列表和数组,但我还没有遇到一个场景,数组列表不能像链表一样容易使用,如果不是更容易的话。我希望有人能给我一些例子,说明什么时候链表明显更好。
当前回答
这个问题的简单答案可以用以下几点来给出:
当需要类似类型的数据元素集合时,将使用数组。而链表是混合类型数据链接元素(称为节点)的集合。 在数组中,可以在O(1)时间内访问任何元素。然而,在链表中,我们需要遍历整个链表,从头到所需的节点,花费O(n)时间。 对于数组,需要在初始时声明特定的大小。但是链表的大小是动态的。
其他回答
如果您需要在中间插入项,并且不想开始调整数组大小和移动内容,则列表的优势就会显现出来。
你是对的,通常情况下并非如此。我遇到过一些非常具体的案例,但不是很多。
我做了一些基准测试,发现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类使用了比数组更好的东西。
嗯,我猜数组列表可以用在以下情况下:
您无法确定将会出现多少个元素 但是您需要通过索引随机访问所有元素
例如,您需要导入并访问联系人列表中的所有元素(您不知道其大小)
1)如上所述,与ArrayList(O(n))相比,在LinkedList中插入和删除操作具有良好的性能(O(1))。因此,如果应用程序需要频繁的添加和删除,那么LinkedList是最好的选择。
2)搜索(get方法)操作在Arraylist (O(1))中是快速的,但在LinkedList (O(n))中不是,所以如果有更少的添加和删除操作和更多的搜索操作要求,Arraylist将是你最好的选择。
到目前为止,数组是使用最广泛的数据结构。然而,链表以其独特的方式被证明是有用的,而数组是笨拙的——或者至少可以说是昂贵的。
链表在大小可变的情况下,对于实现堆栈和队列非常有用。链表中的每个节点都可以被推送或弹出,而不会影响大多数节点。在中间插入/删除节点也是如此。然而,在数组中,所有元素都必须移动,这在执行时间方面是一项昂贵的工作。
二叉树、二叉搜索树、哈希表和try是其中的一些数据结构——至少在C语言中——你需要链表作为构建它们的基本成分。
但是,在期望链表能够通过其索引调用任何任意元素的情况下,应该避免使用链表。
推荐文章
- 在每个列表元素上调用int()函数?
- 将Set<T>转换为List<T>的最简洁的方法
- Java 8流和数组操作
- 在Python中插入列表的第一个位置
- 在javascript中从平面数组构建树数组
- 在bash中传递数组作为参数
- Python数据结构按字母顺序排序
- 如何在c++中初始化一个向量
- 用any可以吗?'来检查数组是否为空?
- 如何获得字典中的键列表?
- 为什么我们使用数组而不是其他数据结构?
- 我如何在JavaScript压缩两个数组?
- 如何在列表中找到最大值的所有位置?
- console.log(result)输出[object对象]。我如何得到result。name?
- Java 8流反向顺序