标签: linked-list

我想看看Java如何实现LinkedList.我应该去哪里查看源代码？

我之前关于此的帖子说:

对于LinkedList

• 得到的是O(n)
• 加是O(1)
• 删除是O(n)
• Iterator.remove是O(1)

对于ArrayList

• 得到的是O(1)
• add是O(1)摊销,但O(n)最坏情况,因为必须调整和复制数组
• 删除是O(n)

因此,通过观察这一点,我得出结论,如果我只是在我的集合中为5000000个元素执行顺序插入,那么LinkedList将会超出ArrayList.

如果我只是通过迭代来获取集合中的元素,即不在中间抓取元素,仍然LinkedList会超出`ArrayList.

现在要验证我的上述两个陈述,我在下面写了示例程序...但我很惊讶我的上述陈述被证明是错误的.

ArrayListLinkedlist在两个案件中都超过了.花费的时间少于LinkedList添加以及从Collection中获取它们所花费的时间.有什么我做错了,或有关初步陈述LinkedList和ArrayList尺寸为500万的收藏品不成立？

我提到了尺寸,因为如果我将元素数量减少到50000,那么LinkedList表现更好,初始语句也成立.

long nano1 = System.nanoTime();

List<Integer> arr = new ArrayList();
for(int i = 0; i < 5000000; ++i) {
    arr.add(i);
}
System.out.println( (System.nanoTime() - nano1) );

for(int j : arr) {
    ;
}
System.out.println( (System.nanoTime() - nano1) );

long nano2 = System.nanoTime();

List<Integer> arrL = new …

下面的函数试图寻找nth到最后一个单向链表的元素.

例如:

如果元素是8->10->5->7->2->1->5->4->10->10结果是 7th最后一个节点是7.

任何人都可以帮助我解释这段代码是如何工作的,还是有更好更简单的方法？

LinkedListNode nthToLast(LinkedListNode head, int n) {
  if (head == null || n < 1) {
    return null;
  }

  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
    if (p2 == null) {
      return null; // not found since list size < n
    }
    p2 = p2.next;
  }

  while (p2.next != …

如何检测单个链表是否有循环？如果它有循环,那么如何找到循环的起始点,即循环开始的节点.

在下面的博客中,有一个关于数组优于链表的优点的声明:

数组具有更好的缓存局部性,可以在性能上产生很大的差异.

那是什么意思？我不明白缓存本地如何提供巨大的性能优势.

我正在尝试创建一个链接列表,看看我是否可以,而且我无法理解它.有没有人有一个使用C#非常简单的链接列表实现的例子？到目前为止,我发现的所有例子都过分夸大了.

我在采访中被问到这个问题:"如何检测链表中的循环？",我解决了这个问题,但是面试官立刻问我如何删除链表中的循环.我摸索着.

那么关于如何解决这个问题的任何指针都可能是伪代码或方法定义？

我对Java很满意所以我在java下标记了这个问题.

对于实例,此链接列表具有循环

 0--->1---->2---->3---->4---->5---->6
                  ?                 |
                  |                 ?
                 11<—-22<—-12<—-9<—-8

在最近的Slashdot访谈中, Linus Torvalds给出了一个例子,说明一些人如何使用指针,表明他们并不真正理解如何正确使用它们.

不幸的是,由于我是他所谈论的人之一,我也不理解他的例子:

我见过太多人通过跟踪"prev"条目删除单链表项,然后删除条目,做类似的事情

if (prev)
    prev->next = entry->next;
else
    list_head = entry->next;

Run Code Online (Sandbox Code Playgroud)

每当我看到这样的代码时,我就会去"这个人不理解指针".而且很遗憾很常见.理解指针的人只使用"指向条目指针的指针",并使用list_head的地址初始化它.然后当他们遍历列表时,他们可以在不使用任何条件的情况下删除条目,只需执行即可

*pp = entry->next

Run Code Online (Sandbox Code Playgroud)

有人可以提供更多解释为什么这种方法更好,以及它如何在没有条件声明的情况下工作？

我最近刷了一些基础知识,发现合并排序链表是一个非常好的挑战.如果你有一个很好的实现,那么在这里展示它.

我已经看过一个问题,讨论在链表中查找循环的算法.我已经阅读了Floyd的循环寻找算法解决方案,在许多地方提到我们必须采取两个指针.一个指针(慢/龟)增加一个,其他指针(更快/野兔)增加2.当它们相等时我们找到循环,如果更快的指针到达null,则链表中没有循环.

现在我的问题是为什么我们将指针增加更快2.为什么不是别的呢？增加2是必要的,或者我们可以将它增加X来得到结果.如果我们将指针增加2,或者可能存在需要增加3或5或x的情况,我们是否有必要找到一个循环.