我使用了很多列表和数组,但我还没有遇到一个场景,数组列表不能像链表一样容易使用,如果不是更容易的话。我希望有人能给我一些例子,说明什么时候链表明显更好。
当前回答
1)如上所述,与ArrayList(O(n))相比,在LinkedList中插入和删除操作具有良好的性能(O(1))。因此,如果应用程序需要频繁的添加和删除,那么LinkedList是最好的选择。
2)搜索(get方法)操作在Arraylist (O(1))中是快速的,但在LinkedList (O(n))中不是,所以如果有更少的添加和删除操作和更多的搜索操作要求,Arraylist将是你最好的选择。
其他回答
如果您需要在中间插入项,并且不想开始调整数组大小和移动内容,则列表的优势就会显现出来。
你是对的,通常情况下并非如此。我遇到过一些非常具体的案例,但不是很多。
我做了一些基准测试,发现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类使用了比数组更好的东西。
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
数组列表适用于写一次读多次或追加程序,但不适用于从前面或中间进行添加/删除。
数组具有O(1)随机访问,但是向数组中添加或删除内容的代价非常高。
链表在任何地方添加或删除项目和迭代都非常便宜,但随机访问是O(n)。
我认为主要的区别在于你是否经常需要从列表顶部插入或删除内容。
对于一个数组,如果你从列表的顶部移除一些东西复杂度是o(n)因为数组元素的所有下标都要移位。
对于链表,它是o(1),因为您只需要创建节点,重新分配头,并将对next的引用分配为前一个头。
当经常在列表的末尾插入或删除时,数组是更可取的,因为复杂度将是o(1),不需要重新索引,但对于链表,它将是o(n),因为你需要从头到最后一个节点。
我认为在链表和数组中搜索都是o(log n)因为你可能会使用二分搜索。
推荐文章
- 在JavaScript中根据键值查找和删除数组中的对象
- Python中方括号括起来的列表和圆括号括起来的列表有什么区别?
- 如何确定一个数组是否包含另一个数组的所有元素
- 给定一个数字数组,返回所有其他数字的乘积的数组(不除法)
- 多维数组如何在内存中格式化?
- TypeScript枚举对象数组
- 获取数组值的键名
- 检查ArrayList中是否存在值
- 如何规范化一个NumPy数组到一定的范围内?
- 如何计数列表中唯一值的出现
- 如何修剪空白的数组值在php
- 检查字符串是否包含字符串列表中的元素
- 如何有效地比较两个无序列表(不是集合)?
- 如何有效地从数组列表或字符串数组中删除所有空元素?
- 比较JUnit断言中的数组,简洁的内置方式?