LinkedList中removeFirst()和remove(0)的区别是什么？

Question

我正在尝试从LinkedList中返回并删除第一个元素。以下是我能看到的两个选项。

第一种方法：

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

第二种方法

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

• 有没有任何偏好，我们应该使用哪一个？
• 上述两者有什么区别？从性能角度来看，它们是否是同一件事？这里涉及到什么复杂性？

在Java中，返回并删除链表中的第一个元素的最有效方法是什么？我需要更频繁地对我的LinkedList执行此操作。

- john

---

你尝试查看源代码了吗？你可以在这里检查https://dev59.com/Y3RC5IYBdhLWcg3wW_tk，以获取各种方法的O(x)比较。 - GhostCat

在这种情况下（删除第一个元素），它们基本上执行相同的工作并具有相同的性能，使用您更喜欢的任何一种。LinkedList 实现了几个接口，其中 remove(int) 继承自 java.util.List 接口，removeFirst 继承自 java.util.Deque 接口。如果您尝试将 LinkedList 用作队列，请考虑使用 Queue（或 Deque）接口访问它，以提高清晰度。 - weaknespase

Answer 1

removeFirst()：删除列表中的第一个元素。-> O（1）

remove(index)：从列表中删除给定位置的元素。-> O（n）

所以，在您的情况下，因为您只想删除第一个元素，您可以选择使用removeFirst()。

- Hector Montero

---

但是你怎么知道所有的事情呢？ - xsami

removeFirst()方法在列表为空时会抛出NoSuchElement异常，而remove(index)方法在列表为空时会抛出IndexOutOfBound异常。 - Chetan Hirapara

“remove（0）”仍然具有相同的时间复杂度“O（1）”，对吗？ - Sang Yun Park

这并不回答问题。 - Uri Loya

Answer 2

你可以从源代码中自己比较它们（例如在此处：http://developer.classpath.org/doc/java/util/LinkedList-source.html）。

removeFirst() 的实现如下：

 260:   /**
 261:    * Remove and return the first element in the list.
 262:    *
 263:    * @return the former first element in the list
 264:    * @throws NoSuchElementException if the list is empty
 265:    */
 266:   public T removeFirst()
 267:   {
 268:     if (size == 0)
 269:       throw new NoSuchElementException();
 270:     modCount++;
 271:     size--;
 272:     T r = first.data;
 273: 
 274:     if (first.next != null)
 275:       first.next.previous = null;
 276:     else
 277:       last = null;
 278: 
 279:     first = first.next;
 280: 
 281:     return r;
 282:   }

remove(int) 的实现方式如下：

575:   /**
 576:    * Removes the element at the given position from the list.
 577:    *
 578:    * @param index the location of the element to remove
 579:    * @return the removed element
 580:    * @throws IndexOutOfBoundsException if index < 0 || index > size()
 581:    */
 582:   public T remove(int index)
 583:   {
 584:     checkBoundsExclusive(index);
 585:     Entry<T> e = getEntry(index);
 586:     removeEntry(e);
 587:     return e.data;
 588:   }

 156:   /**
 157:    * Remove an entry from the list. This will adjust size and deal with
 158:    *  `first' and  `last' appropriatly.
 159:    *
 160:    * @param e the entry to remove
 161:    */
 162:   // Package visible for use in nested classes.
 163:   void removeEntry(Entry<T> e)
 164:   {
 165:     modCount++;
 166:     size--;
 167:     if (size == 0)
 168:       first = last = null;
 169:     else
 170:       {
 171:         if (e == first)
 172:           {
 173:             first = e.next;
 174:             e.next.previous = null;
 175:           }
 176:         else if (e == last)
 177:           {
 178:             last = e.previous;
 179:             e.previous.next = null;
 180:           }
 181:         else
 182:           {
 183:             e.next.previous = e.previous;
 184:             e.previous.next = e.next;
 185:           }
 186:       }
 187:   }

- Ori Lentz

Answer 3

如果您想仅删除第一个元素，请使用 LinkedList::remove()：

E remove()

这个方法检索并删除此列表的头部（第一个元素）。

因此，在您的情况下，最佳实践是：

String firstServerName = servers.remove();

- Jordi Castilla

---

remove()并不是很清晰。它是从末尾还是开头删除？它是LIFO还是FIFO结构？因此，作为最佳实践，我只会在容器声明为Queue而不是具体类型时使用remove()。否则，我更喜欢使用addLast/removeFirst来表达意图。 Java集合的API肯定可以改进。 - Markus Kull

你必须向 OP 提出这些问题，因为他没有澄清任何问题，所以 remove() 是他最好的选择，因为它确保删除第一个元素，无论列表是 LIFO、FIFO 还是其他方式声明，因此在我看来这是最佳实践。 - Jordi Castilla