LinkedList的O（1）复杂度的add(int，E)如何？
LinkedList的O（1）复杂度的add(int，E)如何？
提问于 2018-05-16 04:32:29
如何将列表插入一个随机索引，其复杂度比简单地读取索引要低？
所以我查看了源代码java.util.LinkedList。add(int, E)方法是：
public void add(int index, E element) {
addBefore(element, (index==size ? header : entry(index)));
}
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;
}
回答 2
Stack Overflow用户
发布于 2018-05-16 12:56:09
他们确实支持在任意位置上进行常量插入 - 但只有当你碰巧有一个指向列表条目的指针后，或者在其之前插入某些东西。当然，如果你只有索引，这将不起作用，但这通常不是你通常在优化代码中做的。
在Java中，你也可以这样做，但只能使用列表迭代器。
链表的属性与arraylist等相比是最大的优势 。例如，如果你想从聊天室的用户列表中删除用户，则可以在用户的用户列表中存储用户位置指针，以便，当他想离开房间时，可以将其作为O(1)手术来实施。
Stack Overflow用户
发布于 2018-05-16 13:38:13
这是因为你正在阅读的文章被视为“获取该索引”作为单独的操作。本文假定你已经在你想要执行的索引add（int，E）。
总结：
插入或删除操作= O（1）
在第 n 个索引处寻找节点= O（n）
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/-100008490
复制相关文章
相似问题