我使用了很多列表和数组,但我还没有遇到一个场景,数组列表不能像链表一样容易使用,如果不是更容易的话。我希望有人能给我一些例子,说明什么时候链表明显更好。
当前回答
如果您需要在中间插入项,并且不想开始调整数组大小和移动内容,则列表的优势就会显现出来。
你是对的,通常情况下并非如此。我遇到过一些非常具体的案例,但不是很多。
其他回答
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)
数组列表适用于写一次读多次或追加程序,但不适用于从前面或中间进行添加/删除。
这完全取决于你在迭代时所做的操作类型,所有数据结构都在时间和内存之间进行权衡,我们应该根据需要选择正确的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中更好。
使用链表对数组和多项式操作进行基数排序。
这些是最常用的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)。
推荐文章
- 什么时候在数组/数组列表上使用链表?
- 如何做一个递归子文件夹搜索和返回文件在一个列表?
- Java的数组indexOf在哪里?
- 如何从c#数组中删除重复项?
- 如何转换逗号分隔的字符串列表在Python?
- std::vector比普通数组慢很多吗?
- Ruby中的数组切片:解释不合逻辑的行为(摘自Rubykoans.com)
- 如何分割一个带分隔符的字符串在Ruby和转换为一个数组?
- 字典:获取键列表的值列表
- 为什么这个用于初始化列表列表的代码明显地将列表链接在一起?
- 为什么ArrayDeque比LinkedList好
- 声明一个常量数组
- c#中比较数组的最简单方法
- Javascript reduce()在对象
- Java数组有最大大小吗?