LinkedList 的 O(1) 复杂度的 add(int, E) 如何? [英] How is LinkedList's add(int, E) of O(1) complexity?

问题描述

来自 linked-list 标签维基摘录:

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?

所以我查看了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)));
}

addBefore(E, Entry 方法 只是指针重新分配，但也有 entry(int) 方法:

The addBefore(E, Entry<E> method is simply pointer reassignment, but there's also the entry(int) method:

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;
}

即使使用了一半大小的优化，这里的 for 循环(一个或另一个)在我看来是一个死的赠品，这个方法(因此 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 的 O(1) 复杂度的 add(int, E) 如何?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！