ArrayList和LinkedList有什么區(qū)別？

• ArrayList 是基于數(shù)組實(shí)現(xiàn)的，LinkedList 是基于鏈表實(shí)現(xiàn)的。
  
  二者用途有什么不同？

• 多數(shù)情況下，ArrayList更利于查找，LinkedList更利于增刪

  1. 由于 ArrayList 是基于數(shù)組實(shí)現(xiàn)的，所以 get(int index) 可以直接通過(guò)數(shù)組下標(biāo)獲取，時(shí)間復(fù)雜度是 O(1)；LinkedList 是基于鏈表實(shí)現(xiàn)的，get(int index) 需要遍歷鏈表，時(shí)間復(fù)雜度是 O(n)。
     當(dāng)然，get(E element) 這種查找，兩種集合都需要遍歷通過(guò) equals 比較獲取元素，所以時(shí)間復(fù)雜度都是 O(n)。

  2. ArrayList 如果增刪的是數(shù)組的尾部，直接插入或者刪除就可以了，時(shí)間復(fù)雜度是 O(1)；如果 add 的時(shí)候涉及到擴(kuò)容，時(shí)間復(fù)雜度會(huì)提升到 O(n)。

     但如果插入的是中間的位置，就需要把插入位置后的元素向前或者向后移動(dòng)，甚至還有可能觸發(fā)擴(kuò)容，效率就會(huì)低很多，O(n)。

     LinkedList 因?yàn)槭擎湵斫Y(jié)構(gòu)，插入和刪除只需要改變前置節(jié)點(diǎn)、后置節(jié)點(diǎn)和插入節(jié)點(diǎn)的引用就行了，不需要移動(dòng)元素。

     如果是在鏈表的頭部插入或者刪除，時(shí)間復(fù)雜度是 O(1)；如果是在鏈表的中間插入或者刪除，時(shí)間復(fù)雜度是 O(n)，因?yàn)樾枰闅v鏈表找到插入位置；如果是在鏈表的尾部插入或者刪除，時(shí)間復(fù)雜度是 O(1)。

• 注意，這里有個(gè)陷阱，LinkedList 更利于增刪不是體現(xiàn)在時(shí)間復(fù)雜度上，因?yàn)槎咴鰟h的時(shí)間復(fù)雜度都是 O(n)，都需要遍歷列表；而是體現(xiàn)在增刪的效率上，因?yàn)?LinkedList 的增刪只需要改變引用，而 ArrayList 的增刪可能需要移動(dòng)元素。

二者是否支持隨機(jī)訪問(wèn)呢？

• ①、ArrayList 是基于數(shù)組的，也實(shí)現(xiàn)了 RandomAccess 接口，所以它支持隨機(jī)訪問(wèn)，可以通過(guò)下標(biāo)直接獲取元素。
• ②、LinkedList 是基于鏈表的，所以它沒(méi)法根據(jù)下標(biāo)直接獲取元素，不支持隨機(jī)訪問(wèn)，所以它也沒(méi)有實(shí)現(xiàn) RandomAccess 接口。

二者的內(nèi)存占用有何不同？

• ArrayList 是基于數(shù)組的，是一塊連續(xù)的內(nèi)存空間，所以它的內(nèi)存占用是比較緊湊的；但如果涉及到擴(kuò)容，就會(huì)重新分配內(nèi)存，空間是原來(lái)的 1.5 倍，存在一定的空間浪費(fèi)。
• LinkedList 是基于鏈表的，每個(gè)節(jié)點(diǎn)都有一個(gè)指向下一個(gè)節(jié)點(diǎn)和上一個(gè)節(jié)點(diǎn)的引用，于是每個(gè)節(jié)點(diǎn)占用的內(nèi)存空間稍微大一點(diǎn)。

二者的使用場(chǎng)景有什么不同呢？

ArrayList 適用于：

• 隨機(jī)訪問(wèn)頻繁：需要頻繁通過(guò)索引訪問(wèn)元素的場(chǎng)景。
• 讀取操作遠(yuǎn)多于寫(xiě)入操作：如存儲(chǔ)不經(jīng)常改變的列表。
• 末尾添加元素：需要頻繁在列表末尾添加元素的場(chǎng)景。

LinkedList 適用于：

• 頻繁插入和刪除：在列表中間頻繁插入和刪除元素的場(chǎng)景。
• 不需要快速隨機(jī)訪問(wèn)：順序訪問(wèn)多于隨機(jī)訪問(wèn)的場(chǎng)景。
  • 在日志記錄處理的場(chǎng)景中，通常是按照日志產(chǎn)生的先后順序依次讀取和處理日志信息，不需要隨機(jī)訪問(wèn)某一條特定的日志。例如，從日志文件中逐行讀取日志內(nèi)容，對(duì)每一條日志進(jìn)行解析和分析。此時(shí)使用 LinkedList 存儲(chǔ)日志信息，通過(guò)迭代器進(jìn)行順序訪問(wèn)，可以高效地完成日志處理任務(wù)。

import java.util.Iterator;
import java.util.LinkedList;public class LogProcessingExample {public static void main(String[] args) {LinkedList<String> logList = new LinkedList<>();logList.add("Log entry 1");logList.add("Log entry 2");logList.add("Log entry 3");// 順序訪問(wèn)日志Iterator<String> iterator = logList.iterator();while (iterator.hasNext()) {String log = iterator.next();System.out.println("Processing log: " + log);}}
}

• 隊(duì)列和棧：由于其雙向鏈表的特性，LinkedList 可以高效地實(shí)現(xiàn)隊(duì)列（FIFO）和棧（LIFO）。
  • 1. 雙向鏈表在頭部和尾部進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度都是 ，所以 LinkedList 能夠高效地實(shí)現(xiàn)隊(duì)列。
  • 2. 同樣基于雙向鏈表的特性，LinkedList 可以方便地實(shí)現(xiàn)棧的操作。對(duì)于入棧操作，可以使用 addFirst(E e) 方法將元素添加到鏈表的頭部；對(duì)于出棧操作，可以使用 removeFirst() 方法將鏈表頭部的元素移除。在鏈表頭部進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度為 ，因此 LinkedList 能高效地實(shí)現(xiàn)棧。

鏈表和數(shù)組又有什么區(qū)別？

• 數(shù)組在內(nèi)存中占用的是一塊連續(xù)的存儲(chǔ)空間，因此我們可以通過(guò)數(shù)組下標(biāo)快速訪問(wèn)任意元素。數(shù)組在創(chuàng)建時(shí)必須指定大小，一旦分配內(nèi)存，數(shù)組的大小就固定了。
• 鏈表的元素（節(jié)點(diǎn)）存儲(chǔ)在內(nèi)存中的任意位置，每個(gè)節(jié)點(diǎn)通過(guò)指針（引用）指向下一個(gè)節(jié)點(diǎn)。鏈表不需要指定大小，可以在運(yùn)行時(shí)動(dòng)態(tài)變化。