從列表中獲取/刪除第一個元素的有效方法？

我想取出並從列表中刪除第一個元素。我所看到的，我有兩個選擇：從列表中獲取/刪除第一個元素的有效方法？

第一種方法：

LinkedList<String> servers = new LinkedList<String>(); 
.... 
String firstServerName = servers.removeFirst();

第二種方法

ArrayList<String> servers = new ArrayList<String>(); 
.... 
String firstServerName = servers.remove(0);

我有很多我的列表中的元素。

我們應該使用哪一種偏好？
以上兩者有什麼區別？在性能上它們在技術上是否一樣？如果我們有很多元素，這裏涉及到的複雜性是什麼？

什麼是最有效的方法來做到這一點。

來源

2015-06-04 user1950349

一）定義的性能。有許多變量需要衡量，例如時間，效率，內存使用情況等。b）編寫一些測試代碼，使用秒錶（而不是物理）以及這種性質的事物來進行基準測試並找出結果。 –

「做這件事最有效的方法是什麼？」取決於你的情況。請參閱http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – Shar1er80

使用鏈表的速度要快得多。

LinkedList的

這將只是參考節點，這樣第一個消失。 enter image description here

的ArrayList

有了它具有所有元素向後移動一個點，以保持潛在的陣列正確的數組列表。

來源

2015-06-04 01:00:34

刪除ArrayList的第一個元素是O（n）。對於鏈接列表是O（1），所以我會去。

檢查的ArrayList documentation

大小，的isEmpty，獲取，設置迭代器和操作的ListIterator在固定時間內運行。添加操作以分攤的恆定時間運行，即，添加n個元素需要O（n）個時間。 所有其他操作運行線性時間（粗略地說）。常量因子與LinkedList實現的相比較低。

這傢伙竟然拿到了OpenJDK源碼link

來源

2015-06-04 01:05:01

O（n）？要麼是打字錯誤，要麼是我對list.remove（0）的理解不正確。你能解釋一下它是怎麼樣的O（n）？ – prabugp

@prabugp這不是一個錯字 –

@prabugp元素必須移位後。 –

如果「首先刪除」的比較是ArrayList和LinkedList類之間的LinkedList勝清楚。

從鏈接列表中刪除元素的成本爲O(1)，而對數組（數組列表）的成本爲O(n)。

來源

2015-06-04 01:08:56 PNS

確保您瞭解LinkedList和ArrayList之間的區別。 ArrayList是使用Array實現的。

LinkedList需要一段時間來移除一個元素。 ArrayList可能需要線性時間來刪除第一個元素（以確認我需要檢查實現，而不是java專家）。

另外我認爲LinkedList在空間方面更有效率。由於ArrayList不會（也不應該）在每次刪除元素時重新調整數組的大小，因此它佔用的空間超過了所需的空間。

來源

2015-06-04 01:09:28 Zlol

Java中的ArrayList不是雙端的，因此當您刪除第一個項目時，它需要移動所有內容。雖然LinkedList爲每個項目（值，下一個和前一個）使用3個引用，而ArrayList只需要每個項目一個引用加上未使用的空間，ArrayList對於大型列表比「LinkedList」更具空間效率。 – Raniz

@Raniz加上標記詞，再加上類指針，加上可能的填充... – immibis

不要忘記包裝對象佔用內存以及 – xTrollxDudex

正如其他人已經正確指出的那樣，LinkedList比ArrayList更快地將第一個元素從非常短的列表中移除。

但是，要在它們之間做出選擇，您需要考慮完整的操作組合。例如，如果您的工作負載在每次刪除第一個元素時都會對數百個元素列表進行數百萬次索引訪問，那麼ArrayList總體上會更好。

來源

2015-06-04 01:31:26

實際上，LinkedList#removeFirst更有效率，因爲它是通過雙向鏈表進行操作的，並且刪除第一個元素基本上只是將其從列表頭開始鏈接，並將下一個元素更新爲第一個元素：

public E remove(int index) { 
    rangeCheck(index); 

    modCount++; 
    E oldValue = elementData(index); 

    int numMoved = size - index - 1; 
    if (numMoved > 0) 
     System.arraycopy(elementData, index+1, elementData, index, 
         numMoved); 
    elementData[--size] = null; // clear to let GC do its work 

    return oldValue; 
}

另一方：

private E unlinkFirst(Node<E> f) { 
    // assert f == first && f != null; 
    final E element = f.item; 
    final Node<E> next = f.next; 
    f.item = null; 
    f.next = null; // help GC 
    first = next; 
    if (next == null) 
     last = null; 
    else 
     next.prev = null; 
    size--; 
    modCount++; 
    return element; 
}

ArrayList#remove上方這需要通過在子陣列複製shiftting所有subsequents元件的一個位置向左側的內部陣列操作手，LinkedList#get操作需要遍歷整個列表的一半來檢索指定索引處的元素 - 在最壞的情況下。 ArrayList#get將直接訪問指定索引處的元素，因爲它在數組上運行。

在這裏，我的大拇指效率的規則是：

使用LinkedList如果你做了很多的add/remove在比較檢索操作（例如：get）;
如果您與add/remove比較檢索操作做了很多，請使用ArrayList。

來源

2016-07-17 20:00:23 bhlangonijr

第三個方法。

它由java.util.Queue接口公開。 LinkedList是這個接口的一個實現。

Queue接口公開了E poll（）方法，該方法可以有效地移除List（隊列）的頭部。

在性能方面，poll（）方法與removeFirst（）相當。其實它是在引擎蓋下使用removeFirst（）方法。

來源

2016-07-17 20:28:08

我認爲你需要的是一個ArrayDeque（java.util中一個不公平的忽視類）。它的removeFirst方法在O（1）中執行，與LinkedList相同，但它通常顯示ArrayList更好的空間和時間特性。它被實現爲數組中的循環隊列。您應該很少使用LinkedList。作爲Java程序員，我曾在我17年中做過一次，並且對回想起來感到遺憾。

來源

2017-04-30 19:37:30

你也可以使用'List.subList（...）'，看我的回答https://stackoverflow.com/a/46211629/480894 – Roland

你可以@Roland。如果增加和移除都繼續下去，我不明白它是如何實際的。如果列表只填充一次，之後只刪除，'subList（）'應該沒問題。 –

在ArrayList除去第一要素的情況下具有複雜度爲O（n）的，所以作爲替代，你可以得到第一個元素，而不是刪除它只是調用 List.subList(int fromIndex, int toIndex)的：

final String firstServerName = servers.get(0); 
servers = servers.subList(1, servers.size());

來源

2017-09-14 06:01:34 Roland

從列表中獲取/刪除第一個元素的有效方法？

回答

相關問題