![]()
說?下ArrayList和LinkedList區別
- 具體區別
1.1. ?先，他們的底層資料結構不同，ArrayList底層是基于陣列實作的，LinkedList底層是基于鏈表實作的
1.2. 由于底層資料結構不同，他們所適?的場景也不同，ArrayList更適合隨機查找，
LinkedList更適合洗掉和添加，查詢、添加、洗掉的時間復雜度不同
1.3. 另外ArrayList和LinkedList都實作了List接?，但是LinkedList還額外實作了Deque接?，所以
LinkedList還可以當做佇列來使?
2.類結構
2.1.ArrayList實作了List介面 public class ArrayList<E> extends AbstractList<E> implements List<E>{...}
2.2.LinkedList實作了List和Deque介面，所以LinkedList可以當做雙端佇列來進行使用：因為Deque介面中有addFirst/addLast/getFirst/getLast等操作 public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>{...}
3.效率問題
3.1 查詢：arrayList的速率會更快，因為arrayList底層是基于陣列，所以獲取是通過陣列下標進行獲取！
但是linkedList.getFirst()/getLast()速率也是很快的，因為linkedList會有兩個屬性專門標注第一個元素和最后一個元素
1.arrayList.get(1); 底層代碼：基于下標獲取 public E get(int index) { rangeCheck(index); return elementData(index); } 2.linkedList.get(1); 底層代碼:基于鏈表的操作，所以獲取在底層是進行回圈獲取的！ public E get(int index) { ... Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; ... }
3.2 添加操作
1.arrayList的添加 1.1添加元素：需要考慮底層陣列的擴容，效率較慢 arrayList.add(1); 1.2：在指定的位置1，添加元素1：底層涉及到陣列的移動，因為1位置后的資料都得往后移動，效率較慢 arrayList.add(1,1); 2.linkedList的添加 2.1添加元素：在末尾添加元素，因為底層是鏈表，所以添加速度較快 linkedList.add(1); 2.2：在指定的位置1，添加元素1:因為底層是鏈表，需要先回圈找到要添加的位置， 如果下標數字過大，等于回圈次數越多，效率就會越慢 下標數字小，回圈次數小，效率快！所以此處的效率是決定于插入位置的數字大小 linkedList.add(1,1);
總結：
1.arrayList：查詢速率較快，但是增刪效率一般！
2.linkedList：查詢速率較慢，但是增刪效率比arrayList快！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/458206.html
標籤：Java