我一直在閱讀，因爲它是基於索引的，因此與LinkedList等其他數據結構相比，ArrayList搜索速度更快。我瞭解ArrayList內部使用Java array。以下是來自Java的ArrayList的代碼，該代碼將數據保存在array中。Java：什麼是基於索引的數組訪問以及它們爲什麼快速？
private transient Object[] elementData;
什麼是「基於索引的數據結構」爲什麼它更快？
此外，什麼是數組的內存模型（如何在數組的堆棧/堆組合），以便我可以理解爲什麼訪問數組中的元素更快？
ArrayList由數組支持。通常，通過索引來尋址某個事物被假定爲O(1)，即在恆定時間內。在彙編中，您可以在固定的時間內將內存位置索引，因爲除了基址外，還有一些指令採用可選的索引。數組通常在內存中分配在一個連續的塊中。例如，假設您的基地址爲0x1000（陣列開始），並且您提供的索引爲0x08。這意味着對於從0x1000開始的數組，您想要訪問位置爲0x1008的元素。處理器只需要添加基地址和索引，並在內存中查找該位置*。這可能會持續不斷。所以，假設你有在Java中的以下內容：
int a = myArray[9];
在內部，JVM就會知道myArray地址。就像我們的例子一樣，讓我們假設它在位置0x1000。然後它知道它需要找到9 th下標。所以基本上它需要找到的位置很簡單：
0x1000 + 0x09
這給了我們：
0x1009
使機器可以簡單地從那裏加載它。
在C中，這實際上更明顯。如果你有一個數組，你可以像訪問Java一樣訪問i的位置myArray[i]。但是你也可以通過指針運算來訪問它（一個指針包含指針指向的實際值的地址）！因此，如果您有指針*ptrMyArray，則可以通過執行*(ptrMyArray + i)來訪問i下標，這與我所描述的完全相同：base address plus subscript！
相比之下，訪問LinkedList中的位置的最壞情況是O(n)。如果您回想起您的數據結構，鏈接列表通常有一個head和一個tail指針，並且每個節點都有一個指向下一個節點的next指針。所以要找到一個節點，你必須從head開始，然後依次檢查每個節點，直到你找到正確的節點。你不能簡單地索引到一個位置，因爲不能保證鏈表的節點在內存中彼此相鄰;他們可能在任何地方。
*索引還必須考慮元素的大小，因爲您必須考慮每個元素佔用了多少空間。我提供的基本示例假定每個元素只佔用一個字節。但是如果你有更大的元素，公式基本上是BASE_ADDRESS + (ELEMENT_SIZE_IN_BYTES * INDEX)。在我們的例子中，我們假設大小爲1字節，公式簡化爲BASE_ADDRESS + INDEX。
+1，這正是我想了解的。謝謝！ 問題：當你說0x08時，它大致轉化爲Object o = arr [8];在代碼中的權利？ – PhantomReference
我不知道JVM的確切內部情況，這可能因VM到VM而有所不同，但基本上，陣列是內存中連續的插槽塊。
因此，訪問數組[1000]只需獲取內存中的數組地址，向其中添加1000，並獲取存儲在此位置的值。
用鏈表，你必須得到第一個節點的地址，然後得到這個引用引用的對象，然後得到第二個節點的地址等，直到第1000個元素，這使得它很多比較慢。整個事物存儲在緩存中的可能性也較小。
'arr [7] ='foo';'。那裏。基於索引的訪問。 –
ArrayList由Array支持，並且JVM優化了數組訪問。相反，鏈接列表沒有支持它的數組。 –
按照這個http://stackoverflow.com/questions/716597/array-or-list-in-java-which-is-faster –