java的LinkedList類中的元素是否有索引？

java的LinkedList類中的元素是否有索引？如果是那麼爲什麼它的性能o（n）在最差的情況下用於搜索操作時可以直接使用該對象的索引進行搜索？如果沒有那麼我們如何使用void add(int index, Object item)方法在鏈表中插入一個對象？java的LinkedList類中的元素是否有索引？

來源

2015-07-19 pavan

它們有一個邏輯索引，是的 - 實際上是從頭開始迭代到達該節點之前需要迭代的次數。

這不像說「它可以直接使用對象的索引進行搜索」 - 因爲它不能。

通常，O（1）通過索引訪問是通過使用數組查找來執行的，並且在鏈接列表的情況下不是數組 - 只有一連串節點。要訪問索引爲N的節點，您需要從頭開始，沿着鏈N走，這是一個O（N）操作。

來源

2015-07-19 07:14:17

所以如果我有100000個對象，並且需要插入一個新對象在第99998個位置，那麼哪一個更好ArrayList或LinkedList ??? – pavan

@ user3275663：不幸的是，使用LinkedList提供的API，ArrayList肯定會成爲贏家。在其他API中，您可以從末尾開始*向後*（只有2個位置），然後在該位置便宜地插入。 –

你能否提一下我們可以向後工作並插入對象的API？ – pavan

LinkedList中的元素不包含任何索引信息，也沒有從索引到元素的映射。

如果請求個位置（通過調用add(int index, Object item)），這將需要在LinkedList的從它的開始或從它的端部的元素迭代將元素添加到i」（取決於它們中的哪一個更接近所請求的索引），直到達到所請求的索引。

來源

2015-07-19 07:14:11 Eran

他們*做*有一個索引，這就是爲什麼你可以使用'indexOf'，'get（index）'等。這只是它不映射到「數組中的索引」。他們可能沒有一個名爲'index'的字段，但這並不意味着您無法找到它們在列表中出現的位置。 –

@JonSkeet如果你有一個索引你的意思是有一個命令，那麼是的，你可以說他們有一個索引。使用這個邏輯，你可以說SortedSet中的元素也有一個索引。 – Eran

顯然*是從索引到元素的映射：'LinkedList.get（index）'。以什麼方式*不是*從索引到元素的映射？（實際上，我認爲對於* Sorted * Set而不是其他集合，也有一個合理的索引，但通常不會這樣看）。 –

java的LinkedList類中的元素是否有索引？

回答

相關問題