本篇內(nèi)容介紹了“從面試角度怎么分析LinkedList源碼”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

在曲麻萊等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供做網(wǎng)站、成都網(wǎng)站制作 網(wǎng)站設(shè)計制作定制網(wǎng)站制作,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),高端網(wǎng)站設(shè)計,營銷型網(wǎng)站,外貿(mào)營銷網(wǎng)站建設(shè),曲麻萊網(wǎng)站建設(shè)費用合理。

注：本系列文章中用到的jdk版本均為java8

LinkedList類圖如下：

LinkedList底層是由雙向鏈表實現(xiàn)的。鏈表好比火車，每節(jié)車廂包含了車廂和連接下一節(jié)車廂的連接點。而雙向鏈表的每個節(jié)點不僅有指向下一個節(jié)點的指針，還有指向上一個節(jié)點的指針。

在LinkedList源碼中有一個Node靜態(tài)類，源碼如下：

private static class Node {     E item;     Node next;     Node prev;      Node(Node prev, E element, Node next) {         this.item = element;         this.next = next;         this.prev = prev;     } }

一個Node節(jié)點包含三個部分，分別是

• item：數(shù)據(jù)

• next：下一個節(jié)點的指針

• prev：上一個節(jié)點的指針

LinkedList的主要變量如下：

// 集合中的元素數(shù)量 transient int size = 0;  /**   * 首節(jié)點的指針.   * Invariant: (first == null && last == null) ||   *            (first.prev == null && first.item != null)   */ transient Node first;  /**   * 尾結(jié)點的指針.   * Invariant: (first == null && last == null) ||   *            (last.next == null && last.item != null)   */ transient Node last;

一、添加元素

LinkedList支持在任意節(jié)點位置添加元素，不僅提供了集合常用的add()方法，還提供了addFirst()和addLast()，add()方法默認(rèn)調(diào)用addLast()方法，也就是默認(rèn)是往鏈表尾部插入元素的。

add()方法源碼：

public boolean add(E e) {     linkLast(e);     return true; }

1.1 尾部插入元素

linkLast()源碼如下：

void linkLast(E e) {     final Node l = last;     final Node newNode = new Node<>(l, e, null);     last = newNode;     if (l == null)         first = newNode;     else         l.next = newNode;     size++;     modCount++; }

我們來畫張圖演示一下如何給鏈表尾部插入元素：

假如鏈表中沒有元素

對應(yīng)源碼中的if語句，如果沒有元素則新增的這個節(jié)點為鏈表中唯一的一個元素，既是首節(jié)點，又是尾結(jié)點，前一個元素的指針和后一個元素的指針都是null。這里注意head節(jié)點不是第一個節(jié)點，head節(jié)點只是標(biāo)識了這個鏈表的地址。

假如鏈表中有元素

對應(yīng)源碼中else語句。先將新增的元素當(dāng)成Last節(jié)點，然后將原來的Last節(jié)點的next指向新節(jié)點。

else     l.next = newNode;

一圖勝前言，畫個圖是不是什么都明白了。

1.2 頭部插入元素

linkFirst()源碼如下：

private void linkFirst(E e) {     final Node f = first;     final Node newNode = new Node<>(null, e, f);     first = newNode;     if (f == null)         last = newNode;     else         f.prev = newNode;     size++;     modCount++; }

還是根據(jù)上面的圖來解讀一下源碼，先將第一個節(jié)點賦值給中間變量f，將新節(jié)點newNode賦值給first節(jié)點。如果鏈表沒有元素，則Last節(jié)點和First節(jié)點都是新插入的節(jié)點newNode，否則，將原來的First節(jié)點的頭指針指向新節(jié)點。

二、刪除元素

LinkedList提供的刪除方法有根據(jù)索引和元素刪除，除此之外還提供刪除第一個元素和最后一個元素的方法，這里我們只分析一下根據(jù)索引刪除的方法。

public E remove(int index) {     checkElementIndex(index);     return unlink(node(index)); }

checkElementIndex(index)方法就是用來判斷傳輸?shù)乃饕凳欠窈戏?，不合法則拋出數(shù)組越界異常。重點來看一下unlink(node(index))方法是如何刪除元素的。

node(index)方法源碼：

node(index)方法就是根據(jù)索引獲取該索引位置的節(jié)點

Node node(int index) {     // assert isElementIndex(index);     // 如果指定下標(biāo) < 一半元素數(shù)量，則從首結(jié)點開始遍歷     // 否則，從尾結(jié)點開始遍歷     if (index < (size >> 1)) {         Node x = first;         for (int i = 0; i < index; i++)             x = x.next;         return x;     } else {         Node x = last;         for (int i = size - 1; i > index; i--)             x = x.prev;         return x;     } }

unlink(Nodex)源碼如下：

E unlink(Node x) {     // assert x != null;     final E element = x.item;     final Node next = x.next;     final Node prev = x.prev;      if (prev == null) {         first = next;     } else {         prev.next = next;         x.prev = null;     }      if (next == null) {         last = prev;     } else {         next.prev = prev;         x.next = null;     }      x.item = null;     size--;     modCount++;     return element; }

畫張圖分析一下刪除是如何進(jìn)行的：

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 假設(shè)刪除的是第一個元素：則它的prev==NULL，我們需要將他的后一個元素(圖中的second)作為第一個元素

3. 假設(shè)刪除的是最后一個元素，則它的next==null，我們需要將他的前一個元素(圖中的second)作為最后一個元素

4. 如果是中間的任意元素，則需要將它的前一個元素的next指針指向它的后一個元素，同時將它的后一個元素的prev指針指向它的前一個元素。

“從面試角度怎么分析LinkedList源碼”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！