java循環之continue，java linkedlist 更新_Java填坑系列之LinkedList

前言

java循環之continue。今天我們通過分析LinkedList的源碼，來學習一下它內部是如何添加、查詢以及刪除元素的。同時在閱讀源碼時，也要思考以下幾個問題。

LinkedList的底層數據結構是什么？

java import？與ArrayList有什么區別？

LinkedList是線程安全的嗎？

JAVAlist。繼承關系

public class LinkedList

extends AbstractSequentialList

implements List, Deque, Cloneable, java.io.Serializable

{

//......

}

復制代碼

首先我們來看一下LinkedList的繼承關系，可以看出它繼承自AbstractSequentialList。并且實現List、Deque、Cloneable以及Serializable接口，然后我們再來看一下它的核心字段。

核心字段

//表示LinkedList內部的元素數量

transient int size = 0;

//表示頭結點

transient Node first;

//表示尾節點

transient Node last;

復制代碼

從源碼中可以看出LinkedList中存在兩個特殊的節點，分別是頭結點和尾節點。那我們是不是就能猜到LinkedList底層結構是一個雙向循環鏈表？到底是不是，我們慢慢分析。

構造方法

//創建了一個空列表

public LinkedList() {

}

//這個構造方法傳入一個集合，然后將該集合的元素全部添加的鏈表中

public LinkedList(Collection extends E> c) {

this();

addAll(c);

}

復制代碼

可以看出構造方法比較簡單，我們再來看一下Node類。

Node

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節點類是LinkedList中一個私有的靜態內部類，包含元素、前節點和后節點。

添加

添加一個節點

public boolean add(E e) {

linkLast(e);

return true;

}

void linkLast(E e) {

//l為尾節點

final Node l = last;

//創建一個以l節點為前節點，數據為e，后節點為null的Node節點，此時newNode為尾節點

final Node newNode = new Node<>(l, e, null);

//更新尾節點

last = newNode;

if (l == null)

first = newNode;

else

l.next = newNode;

size++;

modCount++;

}

復制代碼

從源碼中可以看出LinkedList添加一個元素是從鏈表尾部進行添加，添加步驟如下：

將尾節點賦值l節點

創建一個以l節點為前節點，數據為e，后節點為null的Node節點

更新尾節點

判斷l節點是否為空

size++、modCount++

通過指定index添加

public void add(int index, E element) {

//判斷index是否越界

checkPositionIndex(index);

if (index == size)

//此時表示在鏈表尾部添加

linkLast(element);

else

linkBefore(element, node(index));

}

void linkBefore(E e, Node succ) {

// succ表示index對應的節點，pred表示succ前節點

final Node pred = succ.prev;

//newNode的前節點為pred，后節點為succ

final Node newNode = new Node<>(pred, e, succ);

//succ的前節點為newNode

succ.prev = newNode;

//如果pred為null，說明succ原來是頭結點，而現在succ的前節點為newNode，所以現在頭結點是newNode

if (pred == null)

first = newNode;

else

//pred的后節點為newNode

pred.next = newNode;

size++;

modCount++;

}

復制代碼

修改

首先我們來看通過指定索引來修改Node數據，源碼如下

public E set(int index, E element) {

//檢查是否數組越界

checkElementIndex(index);

//通過node方法來獲得對應得Node節點

Node x = node(index);

//保存舊數據

E oldVal = x.item;

//賦值新數據

x.item = element;

//返回舊數據

return oldVal;

}

復制代碼

可以看出修改數據主要分為以下幾步：

獲得index對應的Node節點

保存Node節點舊數據

賦值新數據

獲取

public E get(int index) {

checkElementIndex(index);

return node(index).item;

}

復制代碼

可以看出get()方法內部只有兩行代碼，我們分別來看一下都是做了什么操作。

checkElementIndex(index)

private void checkElementIndex(int index) {

if (!isElementIndex(index))

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

private boolean isElementIndex(int index) {

return index >= 0 && index < size;

}

復制代碼

可以看出checkElementIndex()方法主要是來判斷index是否數組越界，如果越界就拋出對應的異常。

node(index)

Node node(int index) {

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;

}

}

復制代碼

可以看出node()方法通過判斷index是處于前半段還是后半段，來查找對應的Node節點。通過折半查找提升了一定的效率。

刪除

刪除指定索引對應的節點

public E remove(int index) {

checkElementIndex(index);

//傳入index對應的Node節點

return unlink(node(index));

}

E unlink(Node x) {

//獲取Node節點數據

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;

}

//將節點數據置為null

x.item = null;

size--;

modCount++;

return element;

}

復制代碼

然后我們再來簡單看下LinkedList中其他remove()方法，具體如下：

//刪除第一個節點數據

public E removeFirst() {

final Node f = first;

if (f == null)

throw new NoSuchElementException();

return unlinkFirst(f);

}

//刪除最后一個節點數據

public E removeLast() {

final Node l = last;

if (l == null)

throw new NoSuchElementException();

return unlinkLast(l);

}

復制代碼

總結

通過分析LinkedList的源碼，我們可以知道LinkedList在插入和刪除上有著比較大的優勢，這也符合鏈表的特性。而且通過判斷index在前半段還是后半段，使用折半查找的方法來獲得對應的Node節點，提升了一定的效率。

參考資料