概述

LinkedList底層是基于鏈表實(shí)現(xiàn)。鏈表沒有長度限制，內(nèi)存地址不需要固定長度，也不需要是連續(xù)的地址來進(jìn)行存儲，只需要通過引用來關(guān)聯(lián)前后元素即可完成整個(gè)鏈表的連續(xù)。所以鏈表的優(yōu)點(diǎn)就是添加刪除元素比較快，只需要移動指針，并且不需要判斷擴(kuò)容。缺點(diǎn)就是因?yàn)闆]有索引，所以在查詢和遍歷元素時(shí)候比較慢。

使用場景：在增刪操作使用較多，查詢遍歷操作使用較少情況下比較適合去使用；例如：拿來當(dāng)棧使用。

數(shù)據(jù)結(jié)構(gòu)

繼承實(shí)現(xiàn)關(guān)系

1 public class LinkedList<E> 2 extends AbstractSequentialList<E> 3 implements List<E>, Deque<E>, Cloneable, java.io.Serializable

• AbstractSequentialList：本質(zhì)上面與繼承AbstractList 沒有什么區(qū)別，AbstractSequentialList完善了 AbstractList中沒有實(shí)現(xiàn)的方法。
• List：實(shí)現(xiàn)List接口。
• Deque：實(shí)現(xiàn)Deque隊(duì)列接口，擁有作為雙端隊(duì)列（隊(duì)列和棧）的功能。
• Cloneable：重寫clone()方法，通過創(chuàng)建新的LinkedList 對象，遍歷拷貝數(shù)據(jù)進(jìn)行對象拷貝。
• Serializable：重寫read/writeObject() 方法實(shí)現(xiàn)序列化。

靜態(tài)內(nèi)部類

為什么Node這個(gè)類是靜態(tài)的？答案是：這跟內(nèi)存泄露有關(guān)，Node類是在LinkedList類中的，也就是一個(gè)內(nèi)部類，若不使用static修飾，那么Node就是一個(gè)普通的內(nèi)部類，在java中，一個(gè)普通內(nèi)部類在實(shí)例化之后，默認(rèn)會持有外部類的引用，這就有可能造成內(nèi)存泄露（內(nèi)部類與外部類生命周期不一致時(shí)）。但使用static修飾過的內(nèi)部類（稱為靜態(tài)內(nèi)部類），就不會有這種問題?！精@取資料】

• 非靜態(tài)內(nèi)部類會自動生成一個(gè)構(gòu)造器依賴于外部類：也是內(nèi)部類可以訪問外部類的實(shí)例變量的原因。
• 靜態(tài)內(nèi)部類不會生成，訪問不了外部類的實(shí)例變量，只能訪問類變量。

private static class Node<E> {E item;Node<E> next; // 后繼節(jié)點(diǎn)Node<E> prev; // 前置節(jié)點(diǎn)Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}

基本屬性

// 元素?cái)?shù)量 2 transient int size = 0; 3 // 頭結(jié)點(diǎn) 4 transient Node<E> first; 5 // 尾節(jié)點(diǎn) 6 transient Node<E> last;

構(gòu)造方法

1 public LinkedList() { 2 } 3 4 public LinkedList(Collection<? extends E> c) { 5 this(); 6 addAll(c); 7 }

主要方法解析

獲取元素

peek()：隊(duì)列的查，獲取隊(duì)頭元素。

public E get(int index) { // 根據(jù)索引獲取checkElementIndex(index);return node(index).item;}Node<E> node(int index) {// assert isElementIndex(index);// 利用二分法查找；小于中間數(shù)從頭結(jié)點(diǎn)開始找，否則從尾節(jié)點(diǎn)開始找//加入Java開發(fā)交流君樣：756584822一起吹水聊天if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}// 獲取隊(duì)頭元素 ，但是不刪除隊(duì)列的頭元素（雙端隊(duì)列Deque中的方法）public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;}// 獲取隊(duì)尾元素，但是不刪除隊(duì)列的尾元素（實(shí)現(xiàn)雙端隊(duì)列Deque中的方法）public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;}// 隊(duì)列的查。獲取隊(duì)頭元素。public E peek() {final Node<E> f = first;return (f == null) ? null : f.item;}

添加元素
　　offer()：隊(duì)列的增，添加隊(duì)尾元素，底層實(shí)現(xiàn)是調(diào)用add()->linkLast()。

push()：棧的增，把元素壓入棧中，添加對頭元素，底層實(shí)現(xiàn)是調(diào)用addFirst()->linkFirst()。

1 // 添加元素，默認(rèn)在鏈表尾部添加2 public boolean add(E e) {3 linkLast(e);4 return true;5 }//加入Java開發(fā)交流君樣：756584822一起吹水聊天6 // 指定索引添加元素7 public void add(int index, E element) {8 checkPositionIndex(index); // 檢驗(yàn)下標(biāo)是否越界9 10 if (index == size) // 如果要插入的索引等于現(xiàn)有元素長度，說明是要在尾部插入元素 11 linkLast(element); 12 else // 否則，獲取該索引節(jié)點(diǎn)，在該節(jié)點(diǎn)之前插入元素 13 linkBefore(element, node(index)); 14 } 15 16 public boolean addAll(Collection<? extends E> c) { 17 return addAll(size, c); 18 } 19 public boolean addAll(int index, Collection<? extends E> c) { 20 checkPositionIndex(index); // 檢驗(yàn)下標(biāo)是否越界 21 22 Object[] a = c.toArray(); 23 int numNew = a.length; 24 if (numNew == 0) 25 return false; 26 27 // pred:前置節(jié)點(diǎn)，在該節(jié)點(diǎn)之后插入元素。succ：該索引位節(jié)點(diǎn)。 28 Node<E> pred, succ; 29 if (index == size) { 30 succ = null; 31 pred = last; 32 } else { 33 succ = node(index); 34 pred = succ.prev; 35 } 36 // 將數(shù)組設(shè)置為鏈表 37 for (Object o : a) { 38 @SuppressWarnings("unchecked") E e = (E) o; 39 Node<E> newNode = new Node<>(pred, e, null); // 新建一個(gè)節(jié)點(diǎn)，指向前置節(jié)點(diǎn) 40 if (pred == null) // 如果前置節(jié)點(diǎn)為空，說明該鏈表為空。將頭節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn) 41 first = newNode; 42 else // 前置節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn) 43 pred.next = newNode; 44 pred = newNode; // 將當(dāng)前節(jié)點(diǎn)設(shè)置為前置節(jié)點(diǎn)，供后面需要插入的節(jié)點(diǎn)使用 45 }//加入Java開發(fā)交流君樣：756584822一起吹水聊天 46 47 if (succ == null) { 48 last = pred; 49 } else { 50 pred.next = succ; 51 succ.prev = pred; 52 } 53 54 size += numNew; 55 modCount++; 56 return true; 57 } 58 59 // 添加元素到頭結(jié)點(diǎn)（實(shí)現(xiàn)雙端隊(duì)列Deque中的方法） 60 public void addFirst(E e) { 61 linkFirst(e); 62 } 63 private void linkFirst(E e) { 64 final Node<E> f = first; // 原頭節(jié)點(diǎn) 65 final Node<E> newNode = new Node<>(null, e, f); // 新建一個(gè)節(jié)點(diǎn)，要添加的元素 66 first = newNode; // 將頭結(jié)點(diǎn)指向該新建的節(jié)點(diǎn) 67 if (f == null) // 如果原頭結(jié)點(diǎn)為空，說明原鏈表為空。這是添加的第一個(gè)元素，將尾結(jié)點(diǎn)也指向該新建的節(jié)點(diǎn) 68 last = newNode; 69 else // 如果原頭結(jié)點(diǎn)不為空，則將原頭結(jié)點(diǎn)的前置節(jié)點(diǎn)指向該新建的節(jié)點(diǎn) 70 f.prev = newNode; 71 size++; // 元素?cái)?shù)量+1 72 modCount++; // 修改次數(shù)+1 73 } 74 // 添加元素到尾結(jié)點(diǎn)（實(shí)現(xiàn)雙端隊(duì)列Deque中的方法） 75 public void addLast(E e) { 76 linkLast(e); 77 } 78 void linkLast(E e) { 79 final Node<E> l = last; // 原尾結(jié)點(diǎn) 80 final Node<E> newNode = new Node<>(l, e, null); // 新建一個(gè)節(jié)點(diǎn)，要添加的元素 81 last = newNode; // 將尾結(jié)點(diǎn)指向該新建的節(jié)點(diǎn) 82 if (l == null) // 如果尾頭結(jié)點(diǎn)為空，說明原鏈表為空。這是添加的第一個(gè)元素，將頭結(jié)點(diǎn)也指向該新建的節(jié)點(diǎn) 83 first = newNode; 84 else // 如果原尾結(jié)點(diǎn)不為空，則將原尾結(jié)點(diǎn)的后繼節(jié)點(diǎn)指向該新建的節(jié)點(diǎn) 85 l.next = newNode; 86 size++; // 元素?cái)?shù)量+1 87 modCount++; // 修改次數(shù)+1 88 } 89 90 // 隊(duì)列的添加方法 91 public boolean offer(E e) { 92 return add(e); 93 } 94 95 // 棧的添加方法 96 public void push(E e) { 97 addFirst(e); 98 }

刪除元素

poll()：隊(duì)列的刪，獲取對頭元素并且對頭元素刪除。

pop()：棧的刪，返回的是棧頂元素并將棧頂元素刪除。

1 public boolean remove(Object o) {2 if (o == null) {3 for (Node<E> x = first; x != null; x = x.next) {4 if (x.item == null) {5 unlink(x);6 return true;7 }8 }9 } else { 10 for (Node<E> x = first; x != null; x = x.next) { 11 if (o.equals(x.item)) { 12 unlink(x); 13 return true; 14 } 15 } 16 } 17 return false; 18 } 19 public E remove(int index) { 20 checkElementIndex(index); 21 return unlink(node(index)); 22 } 23 // 將該節(jié)點(diǎn)前置節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向該節(jié)點(diǎn)后繼節(jié)點(diǎn)，將該節(jié)點(diǎn)后繼節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)指向該節(jié)點(diǎn)前置節(jié)點(diǎn)。并將該節(jié)點(diǎn)置為空 24 E unlink(Node<E> x) { 25 // assert x != null; 26 final E element = x.item; 27 final Node<E> next = x.next; 28 final Node<E> prev = x.prev; 29 30 if (prev == null) { 31 first = next; 32 } else { 33 prev.next = next; 34 x.prev = null; 35 } 36 37 if (next == null) { 38 last = prev; 39 } else { 40 next.prev = prev; 41 x.next = null; 42 } 43 44 x.item = null; 45 size--; 46 modCount++; 47 return element; 48 } 49 // 將頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)設(shè)置為新的頭結(jié)點(diǎn)，并將原頭節(jié)點(diǎn)置為空 50 private E unlinkFirst(Node<E> f) { 51 // assert f == first && f != null; 52 final E element = f.item; 53 final Node<E> next = f.next; 54 f.item = null; 55 f.next = null; // help GC 56 first = next; 57 if (next == null) 58 last = null; 59 else 60 next.prev = null; 61 size--; 62 modCount++; 63 return element; 64 } 65 //加入Java開發(fā)交流君樣：756584822一起吹水聊天 66 // 將尾結(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)設(shè)置為新的尾結(jié)點(diǎn)，并將原尾節(jié)點(diǎn)置為空 67 private E unlinkLast(Node<E> l) { 68 // assert l == last && l != null; 69 final E element = l.item; 70 final Node<E> prev = l.prev; 71 l.item = null; 72 l.prev = null; // help GC 73 last = prev; 74 if (prev == null) 75 first = null; 76 else 77 prev.next = null; 78 size--; 79 modCount++; 80 return element; 81 } 82 83 public E remove() { 84 return removeFirst(); 85 } 86 87 // 隊(duì)列的刪除方法 88 public E poll() { 89 final Node<E> f = first; 90 return (f == null) ? null : unlinkFirst(f); 91 } 92 // 棧的刪除方法 93 public E pop() { 94 return removeFirst(); 95 }

最后，祝大家早日學(xué)有所成，拿到滿意offer

總結(jié)

以上是生活随笔為你收集整理的这次牛逼了，面试字节被问LinkedList原理了！手足无措啊的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。