目錄

一、LinkedList的全面說明

二、LinkedList的底層操作機(jī)制

(一)LinkedList添加結(jié)點(diǎn)源碼

(二)LinkedList刪除結(jié)點(diǎn)源碼?

三、LinkedList常用方法

四、ArrayList與LinkedList的選擇?

---

一、LinkedList的全面說明

1. LinkedList底層實(shí)現(xiàn)了雙向鏈表和雙端隊列的特點(diǎn)
2. 可以添加任意元素(元素可以重復(fù))，包括null
3. 線程不安全，沒有實(shí)現(xiàn)同步和互斥

二、LinkedList的底層操作機(jī)制

1. LinkedList底層維護(hù)了一個雙向鏈表
2. LinkedList中維護(hù)了兩個屬性first和last，分別指向首節(jié)點(diǎn)和尾節(jié)點(diǎn)
3. 每個節(jié)點(diǎn)(Node對象)，里面又維護(hù)了prev、next、item三個屬性，其中通過prev指向前一個，通過next指向后一個節(jié)點(diǎn)。最終實(shí)現(xiàn)雙向鏈表
4. 所以LinkedList元素的添加和刪除，不是通過數(shù)組完成的，相對來說效率較高

(一)LinkedList添加結(jié)點(diǎn)源碼

1. LinkedList linkedList = new LinkedList();public LinkedList() {}
2. 這時 linkeList 的屬性 first = null  last = null
3. 執(zhí)行 添加public boolean add(E e) {linkLast(e);return true;}
4.將新的結(jié)點(diǎn)，加入到雙向鏈表的最后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;elsel.next = newNode;size++;modCount++;}

(二)LinkedList刪除結(jié)點(diǎn)源碼?

linkedList.remove(); // 這里默認(rèn)刪除的是第一個結(jié)點(diǎn)1. 執(zhí)行 removeFirstpublic E remove() {return removeFirst();}
2. 執(zhí)行public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}
3. 執(zhí)行 unlinkFirst, 將 f 指向的雙向鏈表的第一個結(jié)點(diǎn)拿掉private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}

三、LinkedList常用方法

????????因?yàn)長inkedList也繼承了Collection和List，所以List的方法也適用于LinkedList。

1. add()
2. remove()? ? // 默認(rèn)刪除第一個結(jié)點(diǎn)
3. removeFirst()
4. removeLast()
5. set(索引值,插入的元素)
6. get(索引值)

public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add(1);linkedList.add(2);linkedList.add(3);linkedList.add("");linkedList.add(" ");linkedList.add(' ');linkedList.add(null);linkedList.add(null);System.out.println("linkedList=" + linkedList);// linkedList=[1, 2, 3, ,  ,  , null, null]// remove默認(rèn)刪除第一個結(jié)點(diǎn)linkedList.remove();System.out.println("linkedList=" + linkedList);// linkedList=[2, 3, ,  ,  , null, null]// 修改某個結(jié)點(diǎn)對象linkedList.set(1, 999);System.out.println("linkedList=" + linkedList);// linkedList=[2, 999, ,  ,  , null, null]// 得到某個結(jié)點(diǎn)對象// get(1) 是得到雙向鏈表的第二個對象Object o = linkedList.get(1);System.out.println(o); // 999// 因?yàn)長inkedList 是 實(shí)現(xiàn)了List接口, 遍歷方式System.out.println("===LinkeList遍歷迭代器====");Iterator iterator = linkedList.iterator();while (iterator.hasNext()) {Object next = iterator.next();System.out.println("next=" + next);}// next=2// next=999// next=// next=// next=// next=null// next=nullSystem.out.println("===LinkeList遍歷增強(qiáng)for====");for (Object o1 : linkedList) {System.out.println("o1=" + o1);}// next=2// next=999// next=// next=// next=// next=null// next=nullSystem.out.println("===LinkeList遍歷普通for====");for (int i = 0; i < linkedList.size(); i++) {System.out.println(linkedList.get(i));}// 2// 999//////// null// null
}

四、ArrayList與LinkedList的選擇?

	底層結(jié)構(gòu)	增刪的效率	改查的效率
ArrayList	可變數(shù)組	較低；底層依賴數(shù)組擴(kuò)容	較高；根據(jù)數(shù)組索引查找
LinkedList	雙向鏈表	較高；底層通過鏈表追加	較低；在鏈表中從頭到尾遍歷

如何選擇ArrayList與LinkedList：

1. 如果改查的操作多，選擇ArrayList
2. 如果增刪的操作多，選擇LinkedList
3. 一般來說，80%-90%都是查詢，因此大部分情況下會選擇ArrayList
4. 根據(jù)業(yè)務(wù)靈活選擇，也可能一個模塊使用的是ArrayList，另一個模塊使用LinkedList。