标签: doubly-linked-list

是的,这是一个古老的话题,但我仍有一些困惑.

在Java中,人们说:

1. 如果我随机访问其元素,ArrayList比LinkedList更快.我认为随机访问意味着"给我第n个元素".为什么ArrayList更快？

2. LinkedList比ArrayList更快删除.我理解这个.由于需要重新分配内部备份阵列,因此ArrayList较慢.代码说明:

   List<String> list = new ArrayList<String>();
   list.add("a");
   list.add("b");
   list.add("c");
   list.remove("b");
   System.out.println(list.get(1)); //output "c"
   

   Run Code Online (Sandbox Code Playgroud)

3. LinkedList比ArrayList更快插入.插入意味着什么？如果它意味着将一些元素移回然后将元素放在中间空白点,则ArrayList应该比LinkedList慢.如果插入仅意味着添加(对象)操作,那么这怎么可能很慢？

是否有可能在Haskell中有一个双向链表,实现它们的理想解决方案是什么？我正在实现一个场景图,其中每个小部件都有一个父节点和一个子节点,并且在图形中向上和向下查看都是有益的.

在CLRS的教科书"算法导论"中,有关于pg的这一段.258.

如果列表是双重链接,我们可以在O(1)时间内删除一个元素.(注意,CHAINED-HASH-DELETE将元素x作为输入而不是其键k,因此我们不必首先搜索x.如果哈希表支持删除,则其链表应该双重链接,以便我们可以快速删除一个项目.如果列表只是单链接,那么要删除元素x,我们首先必须在列表中找到x,以便我们可以更新x的前一个属性的下一个属性.使用单链表,两个都删除并且搜索将具有相同的渐近运行时间).

让我感到困惑的是这个大家伙,我无法理解它的逻辑.有了双链表,还是要找到x才能删除它,这与单链表有什么不同？请帮我理解一下!

我听说可以在O(n)时间内在双向链表上实现二进制搜索.访问双向链表的随机元素需要O(n)时间,二进制搜索访问O(log n)个不同的元素,所以运算符不应该是O(n log n)吗？

为什么双链表(O(1))中节点删除的时间复杂度比单链表(O(n))中的节点删除更快？

根据Bjarne Stroustrup 在他的Going Native 2012主题演讲中的幻灯片,在现代硬件中插入和删除是非常低效的:std::list

矢量节拍列表大量插入和删除

如果确实如此,还有什么用例std::list？那不应该被弃用吗？

我不明白双端链接和双链接列表之间的区别.

这两者有什么主要区别？

我有一些degenerate tree(它看起来像数组或双链表).例如,就是这棵树:

每个边缘都有一些重量.我想找到所有相等的路径,它们从每个顶点开始.

换句话说,我想得到所有元组(v1,v,v2),其中v1和v2是任意的祖先和后代,这样c(v1, v) = c(v, v2).

让边具有以下权重(这只是示例):

a-b = 3

b-c = 1

c-d = 1

d-e = 1

然后:

1. 顶点A没有任何相等的路径(左侧没有顶点).
2. 顶点B有一对相等.路径B-A等于路径B-E (3 == 3).
3. 顶点C有一对相等.路径B-C等于路径C-D (1 == 1).
4. 顶点D有一对相等.路径C-D等于路径D-E (1 == 1).
5. 顶点E没有任何相等的路径(右侧没有顶点).

我实现了简单的算法,它适用于O(n^2).但对我来说这太慢了.

我正在sys/queue.h从FreeBSD 学习,我有一个问题:

In sys/queue.h,LIST_ENTRY定义如下:

#define LIST_ENTRY(type)                        \
struct {                                \
    struct type *le_next;   /* next element */          \
    struct type **le_prev;  /* address of previous next element */  \
}

为什么会维持之前的下一个元素的地址(struct type **le_prev),而不是简单地以前elment样struct type *le_prev？

我有一个这样的列表列表:

    std::list<std::list<double> > list;

我在其中填充了一些带有双打的列表(实际上非​​常多,这就是为什么我没有使用向量.所有这些复制都需要花费很多时间.)

假设我想访问可以加入的元素,list[3][3]如果列表不是列表而是矢量或二维数组.我该怎么办？

我知道访问列表中的元素是通过使用迭代器完成的.我无法弄清楚如何摆脱双重.