关于Java的LinkedList类的问题

Question

我有一个关于 Java 中的 LinkedList 类的问题。 我有一个场景，其中我需要根据索引是否存在于链表中来添加或设置索引。我想要实现的伪代码是——

if index a exists within the linkedlist ll 
     ll.set(a,"arbit")
else
      ll.add(a,"arbit")

我确实浏览了 LinkedList 类的 Javadocs，但没有遇到任何相关的内容。

有什么想法吗？

谢谢 p1ng

Answer 1

为此使用 Map 怎么样：

Map<Integer, String> map = new HashMap<Integer, String>();

// ...

int a = 5;

map.put(a, "arbit");

甚至如果a已经存在，put将只替换旧的字符串。

Answer 2

在链表中搜索效率不高（O(n)）。您是否考虑使用不同的数据结构 - 例如 HashMap 会给您 O(1) 访问时间？

Answer 3

如果您需要顺序访问以及键控访问，您可能需要尝试 LinkedHashMap，从 1.4.2 开始可用
http://download.oracle.com/javase /1.4.2/docs/api/java/util/LinkedHashMap.html

Answer 4

Map绝对是一个很好的（最好的？）方法。

如果出于某种奇怪的原因需要，这里有一个选项可以保留 LinkedList 。它具有可怕的运行时性能并且不允许 null，因为 null 现在成为索引未被占用的指示符。

String toInsert = "arbit";
int a = 5;

//grow the list to allow index a
while ( a >= ll.size() ) {
   ll.add(null);
}

//set index a to the new value
ll.set(a, toInsert);

如果您打算走这条路，那么使用ArrayList可能会更好。

为什么这么糟糕？假设索引 100,000 处只有一个元素。此实现需要列表中有 100,000 个指向 null 的条目。这会导致可怕的运行时性能和内存使用。

Answer 5

LinkedList 内部不能有洞，所以你不能有列表 [1,2,3,4] 然后 ll.add(10,10)，所以我认为你的例子有问题。使用 Map 或搜索其他稀疏数组

Answer 6

看起来您正在尝试使用 a 作为键，并且不说明索引 i i 处是否有项目。一个。如果您在 ll.size() <= a 时运行代码，那么最终会出现 NullPointerException。

如果您在索引 a 处添加一个项目，则 a 处的前一个项目现在将位于 a+1 处。
在这种情况下，最好先删除 a 处的项目（如果存在），然后将项目 "arbit" 添加到 a 中。当然，上面的条件：ll.size() <=a在这里仍然适用。

如果结果的顺序很重要，则可以使用不同的方法使用 HashMap<Integer,String> 创建数据集，然后使用 HashMap<? 提取键,?>.getKeySet() 然后按自然顺序对它们进行排序（毕竟它们是数字），然后在迭代 keySet 时从映射中提取值。讨厌，但是做你想要的...或者创建你自己的 OrderedMap 类，它的作用是一样的...

你能详细说明为什么你需要使用 LinkedList 吗？结果的排序重要吗？