LinkedList中的新元素被添加到哪裏？在頭後還是在尾？

Question

我曾經在一些博客中看到新節點被添加到前面。但是當我檢查linkedList的源代碼時，它最後添加了node並且保持列表的地址不變，這應該是理想的行爲。

public boolean add(E e) { 
     linkLast(e); 
     return true; 
} 
void linkLast(E e) { 
     final Node<E> l = last; 
     final Node<E> newNode = new Node<>(l, e, null); 
     last = newNode; 
     if (l == null) 
      first = newNode; 
     else 
      l.next = newNode; 
     size++; 
     modCount++; 
} 

單節點和雙節點列表的節點添加行爲有任何區別嗎？

Answer 1

從the documentation：

添加（E E）

將指定元素到此列表的末尾。

（我的重點）

據我所知，這裏是在Java庫中沒有單鏈表。你可以創建你自己的。我認爲唯一的區別是：保存或不保存鏈接。

Answer 2

Java的LinkedList實現是雙鏈表。所以你可以使用它的所有功能。如果你看看你可以使用的方法，有一個addLast和addFirst，它的名字就是這麼說的。而List接口的add方法的doc說回落到addLast。 這應該回答你的問題。

在單個鏈表中通常addLast是O（n），並且在雙鏈表中它是O（1），因爲您也有對尾部的引用。 AddFirst始終是O（1）。