LinkedList如何添加（int，E）O（1）复杂度？ [英] How is LinkedList's add(int, E) of O(1) complexity?

问题描述

来自 linked-list 标签wiki摘录：

From the linked-list tag wiki excerpt:

链表是一种数据结构，其中元素包含对下一个元素的
引用（以及可选的前一个）元素。链接的
列表提供 O（1）在任何位置插入和删除，O（1）列表
连接，O（1）访问在前面（并且可选地返回）
头寸以及O（1）下一个元素访问权限。随机访问具有O（N）
的复杂性，通常是未实现的。

A linked list is a data structure in which the elements contain references to the next (and optionally the previous) element. Linked lists offer O(1) insert and removal at any position, O(1) list concatenation, and O(1) access at the front (and optionally back) positions as well as O(1) next element access. Random access has O(N) complexity and is usually unimplemented.

^{（强调我的）}

我很惊讶地看到这个–如何将列表插入放在一个复杂度低于读取该索引的随机索引？

I was surprised to read this – how can the list insert at a random index with a lower complexity than simply reading that index?

所以我看了 <$的源代码C $ C> java.util.LinkedList中 。 add（int，E）方法是：

So I looked at the source code for java.util.LinkedList. The add(int, E) method is:

public void add(int index, E element) {
    addBefore(element, (index==size ? header : entry(index)));
}

<$c $ c> addBefore（E，Entry< E> 方法只是指针重新分配，但也有 entry（int）方法：

if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

即使是半尺寸优化，也是循环在这里（一个或另一个）似乎是一个死的赠品，这个方法（因此 add（int，E））在O（n）时间的最小最坏情况，当然不是恒定时间。

Even with the half-size optimization, the for loop in here (one or the other) seems to me a dead giveaway that this method (and thus add(int, E)) operates in a minimum worst-case scenario of O(n) time, and certainly not constant time.

我缺少什么？我是否误解了大O符号？

What am I missing? Am I misunderstanding the big-O notation?

推荐答案

嗯，他们确实支持在任意位置插入常量 - 但是只有当碰巧有一个指向列表条目的指针时，在该列表条目之后或之前要插入一些东西。当然，如果您只有索引，这将不起作用，但这不是您在优化代码中通常所做的。

Well, they do support constant-time inserts at arbitrary positions – but only if you happen to have a pointer to the list entry after which or in front of which you want to insert something. Of course, this won't work if you just have the index, but that's not what you usually do in optimized code.

在Java中，您也可以这样做，但仅使用列表迭代器。

In Java, you can do that, too, but only using a list iterator.

与arraylists相比，链接列表的这一属性是它们的最大优势 - 例如，如果你想删除一个用户从聊天室的用户列表中，您可以存储指向用户在用户列表中的位置的指针，以便当他想要离开房间时，可以实现为 O（1 ）操作。

This property of linked lists is their biggest advantage compared to arraylists or so – for example, if you want to remove a user from the user list of a chatroom, you can store a pointer to the user's position in the userlist in the user so that, when he wants to leave the room, that can be implemented as a O(1) operation.

这篇关于LinkedList如何添加（int，E）O（1）复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！