Java中LinkedList的实时效率 [英] The real time efficiency of LinkedList in Java

问题描述

我们知道，如果您已经在要插入的位置之前或之后找到节点，则Double LinkedList数据结构具有在O（1）时间内插入节点的优势。 （例如，如果您有一个双向链接列表：ABCD，如果您已经有了节点C，则只需花费O（1）时间在节点C之前或之后插入一个新Node。）

We know the Double LinkedList Data Structure has an advantage of inserting a node in O(1) time if you already got the node before or after the location you want to insert. (e.g. if you have a double linked list: A-B-C-D, if you already got the node C, then it only takes O(1) time to insert a new Node before or after the node C).

如果您在Java / C ++中手动构造一个双链表，这很容易理解，但是我最近对Java中的LinkedList库感兴趣，它是Java中提供的双链表数据结构。实用程序。如果要使用java提供的库LinkedList，如何执行第一段中提到的O（1）插入或删除操作？我进行了一些研究，您可以创建LinkedList的ListIterator，该ListIterator可以前后移动，然后插入和删除前节点或后节点。但是它仍然需要遍历。如果我已经有了节点C，又该如何在O（1）时间内直接获得相应的迭代器？

If you manually construct a double linked list in Java/C++, it is fairly easy to understand, but I recently am interested in the LinkedList library in Java which is a double linked list data structure offered in java.util. If I want to use the library LinkedList provided by java, how could I perform O(1) insertion or deletion like I mentioned in the 1st paragraph? I did some research, you can create a ListIterator of the LinkedList which can traverse forward and back then insert and delete the former or after node. But it still needs traverse. If I already have the node C and how could I directly get the corresponding Iterator in O(1) time?

推荐答案

code> LinkedList 类提供了遍历过程中或列表开头/末尾的O（1）插入/删除时间。这并不意味着您可以在列表的中间获取一个随机节点，然后在O（1）时间删除它或在其旁边插入一个节点。

The LinkedList class provides O(1) insertion/deletion time during traversing or at the beginnig/end of the list. This doesn't mean that you can take a random node in the middle of the list and delete it or insert some node next to it in O(1) time.

这篇关于Java中LinkedList的实时效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！