我使用了很多列表和数组,但我还没有遇到一个场景,数组列表不能像链表一样容易使用,如果不是更容易的话。我希望有人能给我一些例子,说明什么时候链表明显更好。
当前回答
数组具有O(1)随机访问,但是向数组中添加或删除内容的代价非常高。
链表在任何地方添加或删除项目和迭代都非常便宜,但随机访问是O(n)。
其他回答
这些是最常用的Collection实现。
数组列表:
插入/删除在结尾一般O(1)最坏情况O(n) 中间插入/删除O(n) 检索任意位置O(1)
LinkedList:
在任何位置O(1)插入/删除(注意你是否引用了元素) 中间检索O(n) 检索第一个或最后一个元素O(1)
向量:不要用。它是一个类似于ArrayList的旧实现,但所有方法都是同步的。对于多线程环境中的共享列表,这不是正确的方法。
HashMap
在O(1)中按键插入/删除/检索
TreeSet 插入/删除/包含O(log N)
HashSet 在O(1)中插入/删除/包含/大小
这个问题的简单答案可以用以下几点来给出:
当需要类似类型的数据元素集合时,将使用数组。而链表是混合类型数据链接元素(称为节点)的集合。 在数组中,可以在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类使用了比数组更好的东西。
数组具有O(1)随机访问,但是向数组中添加或删除内容的代价非常高。
链表在任何地方添加或删除项目和迭代都非常便宜,但随机访问是O(n)。
如果您需要在中间插入项,并且不想开始调整数组大小和移动内容,则列表的优势就会显现出来。
你是对的,通常情况下并非如此。我遇到过一些非常具体的案例,但不是很多。
推荐文章
- 在JavaScript中根据键值查找和删除数组中的对象
- Python中方括号括起来的列表和圆括号括起来的列表有什么区别?
- 如何确定一个数组是否包含另一个数组的所有元素
- 给定一个数字数组,返回所有其他数字的乘积的数组(不除法)
- 多维数组如何在内存中格式化?
- TypeScript枚举对象数组
- 获取数组值的键名
- 检查ArrayList中是否存在值
- 如何规范化一个NumPy数组到一定的范围内?
- 如何计数列表中唯一值的出现
- 如何修剪空白的数组值在php
- 检查字符串是否包含字符串列表中的元素
- 如何有效地比较两个无序列表(不是集合)?
- 如何有效地从数组列表或字符串数组中删除所有空元素?
- 比较JUnit断言中的数组,简洁的内置方式?