在O（n）時間穿越LinkedList並刪除k個元素

我正在使用Java的LinkedList，據我所知，沒有LinkedList.next(int);，但有ListIterator.next()，它通過LinkedList.listIterator()進場。然而，正如我想到的：使用ListIterator來遍歷元素（這需要O（n）時間）將在您刪除所有元素之後失敗（對刪除本身進行常量操作，但O（n）到達元素）。在O（n）時間穿越LinkedList並刪除k個元素

試圖刪除某個k < = n個元素的簡單的方法，它是這樣的：

if (list.get(++index).equals(elementToRemove)) 
{ 
    list.remove(index); 
}

是爲O（n^2）操作中，當各第n get() S的是O（n ）。

有什麼辦法在線性時間內通過LinkedList並刪除應該去的元素？

來源

2015-10-03 Mike Warren

你必須使用迭代器的'remove'方法。 –

我很困惑，爲什麼不使用'ListIterator'？ –

我不知道ListIterator已經刪除（）！ –

使用Iterator.remove()：

for (Iterator<T> iterator = list.iterator(); iterator.hasNext();) { 
    T element = iterator.next(); 
    if (element.equals(elementToRemove)) { 
     iterator.remove(); 
    } 
}

來源

2015-10-03 21:29:48 Roman

如果你不關心就地處理，你可以只使用

public <T> T[] toArray(T[] a)

功能，然後遍歷表僅添加所需的項目新的列表

來源

2015-10-03 21:27:07

在O（n）時間穿越LinkedList並刪除k個元素

回答

相關問題