是否有可能创建一个O(1)插入、删除和O(1)访问权限最小化的LinkedList实现？

文章/答案/技术大牛

发布

1回答

algorithm、data-structures、linked-list

假设你对这个问题有无限的空间复杂度。我相信我看到了解决方案，但我已经完全忘记了。如果我没记错的话，一个解决方案涉及一个堆栈来跟踪min，另一个涉及向LinkedList节点添加一个数据值。最小堆实现将导致Log(n)插入和删除，但是否有方法使其为O(1)？如果有可能的话，一个可以做到这一点的数据结构的

浏览 16提问于2020-12-27得票数 0

3回答

ArrayList或链表-如果同时执行插入/删除和查找操作，则使用哪个集合

java、arraylist

众所周知，链表是用来快速插入、删除的，数组列表是用来快速查找的我应该使用哪个集合?原因是什么？或者我应该使用我自己创建的集合？

浏览 0提问于2016-02-26得票数 2

2回答

LinkedList对List<T>

c#、performance、list、linked-list

可能重复：假设我有N个实例。在LinkedList中插入和删除只会是o(1)运算，在列表中它可以是O( n )，但是由于它优化了，所

浏览 0提问于2011-05-03得票数 1

回答已采纳

4回答

在( List<T> )库中使用LinkedList<T>和c#有什么区别？

c#、performance、list、linked-list

可能重复：如果我不希望对我的数据结构使用按索引的访问权限，那么使用LinkedList over List可以节省多少？如果我不能100%确定我永远不会使用access by索引，我想知道两者的区别。假设我有N个实例。在LinkedList中插入和删除只会是o(1)运

浏览 15提问于2011-05-04得票数 4

回答已采纳

11回答

ArrayList和LinkedList的性能差异

java、arraylist、doubly-linked-list

是的，这是一个古老的话题，但我仍然有些困惑。 List =新的ArrayList()；list.add("a")；l

浏览 31提问于2012-05-18得票数 76

回答已采纳

8回答

是否有已知的索引链接列表的实现？

language-agnostic、list、indexing、linked-list

我的直觉告诉我，没有很好的方法来实现这一点，但是，不像斯蒂芬·科尔伯特先生，我宁愿相信一个开发人员社区，也不愿相信我的直觉。是否有一种已知的方法可以有效地实现“两个世界中最好的”列表，它可以像链接列表一样通过索引和 O(1)插入/删除来提供随机访问？我预见到两个可能的</em

浏览 10提问于2009-11-11得票数 21

回答已采纳

1回答

从ArrayDeque获取元素的时间复杂度

java、data-structures、time-complexity

我在一些地方读到，LinkedList在Java中添加和删除元素的时间复杂度是O(1)，而O(n)是获取元素的时间复杂度。ArrayList有O(1)来获取元素，O(n)可以添加和删除元素。我有一个程序，它必须做许多涉及插入和从列表中恢复元素的操作。因此，我

浏览 0提问于2018-11-27得票数 2

回答已采纳

6回答

为什么链表删除和插入操作具有O(1)的复杂性？不是应该是O(n)吗？

java、data-structures、collections、linked-list、time-complexity

据说，LinkedList删除和添加操作的复杂性是O(1)的。如果是ArrayList，则是O(n)。因此，删除或插入在最后将给我最好的表现(如N~ M)，删除或插入在开始将是最差的(如N~ 1)。现在大小为"M“的LisnkedList :由于我们不能直接到达LinkedList中

浏览 5提问于2017-03-17得票数 23

回答已采纳

15回答

什么时候在数组/数组列表上使用链表？

arrays、list、arraylist、linked-list

我使用了很多列表和数组，但是我还没有遇到过一个场景，在这种场景中，数组列表不能像链表一样容易使用，如果不是更容易的话。我希望有人能给我一些例子，说明链表在什么情况下更好。

浏览 2提问于2008-12-26得票数 223

回答已采纳

3回答

您什么时候使用java.util.LinkedList？

java

可能重复：据我所知，由于java.util.LinkedList不支持随机访问，获得第n个元素的唯一方法是跳过从1跳到(n-1)或使用那么，为什么要使用LinkedList呢？在大多数情况下，除非您想使用ArrayList迭代来自双方的集合，否则ListIterator将起很大的作用。

浏览 2提问于2012-03-19得票数 8

回答已采纳

6回答

列表实现: LinkedList的表现真的比ArrayList和TreeList差吗？

java、collections、arraylist、linked-list、treelist

摘自获得添加插入迭代删除TreeList 3 5 1 2 1 ArrayList 1 40 1 40 LinkedList 5800 1 350 2 325它接着说： LinkedList很少是一个很好的实现选择。TreeList几乎总是一个很好的替代品，尽管它确实使用了更多

浏览 21提问于2009-11-11得票数 25

回答已采纳

2回答

在Java中实现LRU Cache

java、guava

问题:定义一个固定大小的LRU缓存，它支持对类型E的对象进行分期O(1)操作。每个对象都有一个唯一的id。此问题包含问题描述和几个解决方案：LRU cache in Java with Generics and O(1) operations 不起作用的可能解决方案:只创建一个链表和一个HashMap。维护<e

浏览 21提问于2021-01-16得票数 1

2回答

获取ith元素时FIFO实现的数据结构

java、performance、fifo

我想要一个数据结构，将固定的大小和将作为FIFO工作。我的意思是，如果尺寸超过第一个元素，就会被移除。另外，每次插入后，我想检查结构中的中间元素(即大小为21的第10个元素)。即得到第一个元素) 我将在一个耗时的过程中使用它，性能对我来说很重要。我建议的数据结构是什么？

浏览 8提问于2014-02-28得票数 1

回答已采纳

3回答

为什么Stack<T>和Queue<T>是用数组实现的？

c#、.net、stack、queue、linked-list

我正在阅读Albahari兄弟的C# 4.0，我发现了这一点：我不禁想知道为什么。LinkedList提供O(1)头尾插入和删除(这对于堆栈或队列来说应该很好)。一个可调整大小的数组具有O(1)分期插入(

浏览 4提问于2010-06-08得票数 28

回答已采纳

1回答

查找具有对前一个和下一个元素的访问权限的.Net排序集合

c#、.net、sorting、data-structures、sortedcollection

元素的删除应该是O(log count)，对于给定的元素e (无论是否已经在集合中)，我需要按排序顺序在e旁边的集合的前一个和下一个元素。SortedList<TKey, TValue>在插入和删除时有一个O(count)，因为它必须移动列表中的所有连续元素。但是，一旦我知道了O</e

浏览 4提问于2015-04-20得票数 2

回答已采纳

3回答

List<T>与LinkedList<T>的区别

c#、c#-4.0

每当我们需要一个列表时，我们都会使用列表。我注意到现在有一个LinkedList。我想知道这两个有什么不同，以及什么时候应该使用其中一个。

浏览 0提问于2010-11-26得票数 41

回答已采纳

1回答

使用数组Vs实现堆(ADT)。LinkedList

arrays、linked-list、heap、time-complexity、abstract-data-type

在我的数据结构课程中，我需要实现具有以下时间复杂性要求的二进制堆：现在，我想以以下方式使用数组来实现这一点Arri的孩子在Arr2i和Arr。通过这种实现，我将在O(1)中找到Max，在O(n)中删除</e

浏览 3提问于2016-04-15得票数 0

3回答

如何有效地从java LinkedList中删除元素

java、performance、collections、linked-list

我有一个算法，我以某种方式通过图中的节点，偶尔通过同一个节点几次，我需要形成一个传递节点的列表，这样一个节点就会出现一次，这是我最后一次传递它。然后，每次经过一个节点时，我都会从LinkedList中删除相应的节点，并将其再次插入到LinkedList的末尾，操作的复杂性将仅为O(1)。然而，

浏览 2提问于2013-12-25得票数 3

回答已采纳

2回答

哪个更快-在数组或链表的末尾插入元素

java、arrays、linked-list

在数组末尾插入元素和在链表中插入元素，哪个更快？

浏览 0提问于2017-05-08得票数 2

3回答

为什么数组列表比LIFO行为的链接列表更快？

java、arraylist、linked-list

我已经编写了一个算法，它在数据结构的末尾有很多附加和移除项(基本上是最后一次输出)。现在，由于某种原因，当我使用ArrayList执行此操作时，它比LinkedList快得多，即使是通过ArrayList，也需要重定位的开销。它甚至不会稍微快一点。快了几英里！为什么会这样呢？

浏览 7提问于2015-04-22得票数 4

回答已采纳

点击加载更多