在Java中插入LinkedList的中间

Question

想象一下你有一个LinkedList插入元素{A,B,C,D,E,F},这些操作都是O(1)现在我想回到开头添加{G,H,I}所以最终的LinkedList会看起来像:{G,H,I,A,B,C,D,E,F}.

我可以使用list.add(index, content),但这是非常低效的,因为每个操作将是O(N).后来我想继续加尾.我确信有一种方法可以在O(1)时间内完成所有这些操作,而不需要创建我自己的链表,我只是不知道如何.

编辑:所以我真的想知道Java是否有一些排序迭代器/指针,i,其中a可以从那里插入O(1),例如i = 3 {A,B,C,^ D,E,F },插入{G},{H},{I}会使列表看起来像{A,B,C,G,H,I,D,E,F}. list.addAll有效,但我必须先创建一个列表.如果存在这样的方法,我不想在不知情的情况下继续进行.

最后我问这个问题来解决这个Uva判断问题,我知道如何解决它,但如果不能推广其他场景我什么都不学.

Answer 1

根据Javadoc:

List和Deque接口的双链表实现.

对于双向链表,所有操作都可以预期.索引到列表中的操作将从开头或结尾遍历列表,以较接近指定索引为准.

关于你的关注:

我可以使用list.add(索引,内容)来做到这一点,但是由于每个操作都是O(N),因此效率非常低.后来我想继续加尾.

这不是真的.在列表的开头或结尾插入元素的设计具有O(1)运行时间.因此没有什么可担心的.

编辑:在阅读UVa问题描述后,我上面的答案仍然存在.此外,我想补充一点,解决问题的一个好方法是一次添加整个文本字符串,而不是一次添加一个字符.两个家庭/结束按键之间的所有字符应被视为单个不可破解的字符串.然后我们将这些字符串添加到a的开头或结尾LinkedList<String>,而不是LinkedList<Character>.仍然没有必要担心插入中间,也没有必要有一个假想的插入迭代器.