arraylist和linkedlist的時(shí)間復(fù)雜度？

首先一點(diǎn)關(guān)鍵的是，ArrayList的內(nèi)部實(shí)現(xiàn)是基于基礎(chǔ)的對(duì)象數(shù)組的，因此，它使用get方法訪問列表中的任意一個(gè)元素時(shí)(random access)，它的速度要比LinkedList快。LinkedList中的get方法是按照順序從列表的一端開始檢查，直到另外一端。對(duì)LinkedList而言，訪問列表中的某個(gè)指定元素沒有更快的方

基本上ArrayList的時(shí)間要明顯小于LinkedList的時(shí)間。因此在這種情況下不宜用LinkedList。二分查找法使用的隨機(jī)訪問(random access)策略，而LinkedList是不支持快速的隨機(jī)訪問的。對(duì)一個(gè)LinkedList做隨機(jī)訪問所消耗的時(shí)間與這個(gè)list的大小是成比例的。而相應(yīng)的，在ArrayList中進(jìn)行隨機(jī)訪問所消耗的時(shí)間是固定的。