Java ArrayList和LinkedList - 添加元素在結束時的實現細節

我理解爲什麼arraylist比鏈表更快是因爲使用arraylist你基本上只需要一個動作 - 更新結尾數組元素的引用，而使用鏈表你必須做更多的例如創建一個新節點，更新2個引用，通過鏈表並更新最後一個節點指向新的節點等。Java ArrayList和LinkedList - 添加元素在結束時的實現細節

但是我不確定java是如何實現這些的。 arraylist如何知道「last」元素的位置，它是否存儲最後一個元素的值，或者它是否遍歷數組，並在最後一個元素後面添加新元素？

和鏈表，它們是否存儲對列表中最後一個節點的引用，還是它們遍歷整個列表直到最後？

來源

2013-01-24 ddriver1

JDK附帶了源代碼。閱讀它們，你會發現。 –

看看源：

ArrayList：

public boolean add(E e) { 
    ensureCapacityInternal(size + 1); // Increments modCount!! 
    elementData[size++] = e; 
    return true; 
}

LinkedList：

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++; 
}

來源

2013-01-24 08:18:59 jlordo

您可以隨時查看java.*類的來源。

但是，回答特定的問題：在ArrayList類中有int字段，其中包含當前填充的內部數組區域的大小。當您在ArrayList對象中添加新值時，此字段將遞增，然後直接尋址到內部數組中的該元素。

來源

2013-01-24 08:18:34 Andremoniy

數組列表是僅在快某些操作。如果在數組中間添加元素，則數組列表需要基本上將所有數據複製到新數組中。只有當數據列表已經爲新數據分配空間時，在數據插入空白處（通常在最後）時它是快速的。通過索引讀取/更新非常快。

LinkedList在插入時速度很快，因爲它永遠不需要複製整個數組。但是訪問鏈表中的數據是很慢的，因爲你需要「走路」所有的元素，直到找到你想找的元素。

來源

2013-01-24 08:33:06 Roland

Java ArrayList和LinkedList - 添加元素在結束時的實現細節

回答

相關問題