資訊專欄INFORMATION COLUMN
摘要：表明該類是可以序列化的。與對比并沒有實現(xiàn)，而實現(xiàn)表明其支持快速通常是固定時間隨機訪問。此接口的主要目的是允許一般的算法更改其行為，從而在將其應用到隨機或連續(xù)訪問列表時能提供良好的性能。這是隨機訪問效率低的原因之一。指定節(jié)點不能為。
總覽 定義
public class LinkedList
extends AbstractSequentialList
implements List, Deque , Cloneable, java.io.Serializable
LinkedList
extends AbstractSequentialList
AbstractSequentialList 繼承自AbstractList，但AbstractSequentialList 只支持按次序訪問，而不像 AbstractList 那樣支持隨機訪問。這是LinkedList隨機訪問效率低的原因之一。
implements
List
Deque
Cloneable：表明其可以調用clone()方法來返回實例的field-for-field拷貝。
java.io.Serializable：表明該類是可以序列化的。
與ArrayList對比
LinkedList并沒有實現(xiàn)RandomAccess，而實現(xiàn)RandomAccess表明其支持快速（通常是固定時間）隨機訪問。此接口的主要目的是允許一般的算法更改其行為，從而在將其應用到隨機或連續(xù)訪問列表時能提供良好的性能。這是LinkedList隨機訪問效率低的原因之一。
LinkedList不是線程安全的，如果想使LinkedList變成線程安全的，可以調用靜態(tài)類Collections類中的synchronizedList方法：
List list=Collections.synchronizedList(new LinkedList(...));
LinkedList底層是雙向鏈表
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; } }
/**
* LinkedList節(jié)點個數(shù)
*/
transient int size = 0;
/**
* 指向頭節(jié)點的指針
*/
transient Node first;
/**
* 指向尾節(jié)點的指針
*/
transient Node last;
構造方法
LinkedList()
LinkedList(Collection c)
/**
* 構造一個空鏈表.
*/
public LinkedList() {
}
/**
* 根據(jù)指定集合c構造linkedList。先構造一個空linkedlist，在把指定集合c中的所有元素都添加到linkedList中。
*/
public LinkedList(Collection c) {
this();
addAll(c);
}
操作鏈表的底層方法
linkFirst(E e)
/**
* 在表頭添加指定元素e
*/
private void linkFirst(E e) {
final Node f = first;
//新建節(jié)點，節(jié)點的前指針指向null，后指針原來的頭節(jié)點
final Node newNode = new Node<>(null, e, f);
first = newNode;
//如果原來的頭結點為null，更新尾指針，否則使原來的頭結點f的前置指針指向新的頭結點newNode
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
linkLast(E e)
/**
* 在表尾插入指定元素e
*/
void linkLast(E e) {
final Node l = last;
//新建節(jié)點newNode，節(jié)點的前指針指向l，后指針為null
final Node newNode = new Node<>(l, e, null);
last = newNode;
//如果原來的尾結點為null，更新頭指針，否則使原來的尾結點l的后置指針指向新的頭結點newNode
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
linkBefore(E e, Node /**
* 在指定節(jié)點succ之前插入指定元素e。指定節(jié)點succ不能為null。
*/
void linkBefore(E e, Node succ) {
//獲得指定節(jié)點的前驅
final Node pred = succ.prev;
//新建節(jié)點newNode，前置指針指向pred，后置指針指向succ
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
//如果指定節(jié)點的前驅為null，將newTouch設為頭節(jié)點。否則更新pred的后置節(jié)點
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
unlink(Node /**
* 刪除指定節(jié)點，返回指定元素的值
*/
E unlink(Node x) {
// assert x != null;
// 保存指定節(jié)點的值
final E element = x.item;
//得到后繼節(jié)點
final Node next = x.next;
//得到前驅節(jié)點
final Node prev = x.prev;
if (prev == null) {
//如果刪除的節(jié)點是頭節(jié)點,令頭節(jié)點指向該節(jié)點的后繼節(jié)點
first = next;
} else {
//將前驅節(jié)點的后繼節(jié)點指向后繼節(jié)點
prev.next = next;
x.prev = null;
}
if (next == null) {
//如果刪除的節(jié)點是尾節(jié)點,令尾節(jié)點指向該節(jié)點的前驅節(jié)點
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
unlinkFirst(Node /**
* 刪除頭結點f，并返回頭結點的值.
*/
private E unlinkFirst(Node f) {
//保存頭結點的值
final E element = f.item;
// 保存頭結點指向的下個節(jié)點
final Node next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
//如果next為null，將尾節(jié)點置為null，否則將next的后置指針指向null
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
//返回被刪除的頭結點的值
return element;
}
unlinkLast(Node /**
* 刪除尾節(jié)點并返回尾節(jié)點的值
*/
private E unlinkLast(Node l) {
// 保存尾節(jié)點的值
final E element = l.item;
final Node prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
//如果新的尾節(jié)點為null，頭結點置為null，否則將新的尾節(jié)點的后置指針指向null
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
//返回被刪除的尾節(jié)點的值
return element;
}
添加
步驟：
先用一個變量l指向尾結點，
創(chuàng)建新結點
尾結點指向新的結點
判斷原來的尾結點（變量l指向的結點）是否為空，
如果為空說明是個空鏈表，將頭結點指向新的結點；
原來的尾結點不為空，將原來尾結點(l指向的結點)的prev指向新的結點
add(E e) /**
* 將元素添加到鏈表尾部
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 在表尾插入指定元素e
*/
void linkLast(E e) {
final Node l = last;
//新建節(jié)點newNode，節(jié)點的前指針指向l，后指針為null
final Node newNode = new Node<>(l, e, null);
last = newNode;
//如果原來的尾結點為null，更新頭指針，否則使原來的尾結點l的后置指針指向新的頭結點newNode
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
add(int index, E element)
/**
* 在指定位置添加元素
*/
public void add(int index, E element) {
//檢查索引是否處于[0-size]之間
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
addAll(Collection c)
步驟：
檢查index范圍是否在size之內
toArray()方法把集合的數(shù)據(jù)存到對象數(shù)組中
得到插入位置的前驅和后繼節(jié)點
遍歷數(shù)據(jù)，將數(shù)據(jù)插入到指定位置
/**
* 插入指定集合到鏈尾
*/
public boolean addAll(Collection c) {
return addAll(size, c);
}
/**
* 插入指定集合到鏈尾的指定位置
*/
public boolean addAll(int index, Collection c) {
//1:檢查index范圍是否在size之內
checkPositionIndex(index);
//2:toArray()方法把集合的數(shù)據(jù)存到對象數(shù)組中
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
//3：得到插入位置的前驅節(jié)點和后繼節(jié)點
Node pred, succ;
//如果插入位置為尾部，前驅節(jié)點為last，后繼節(jié)點為null
if (index == size) {
succ = null;
pred = last;
} else {
//否則，調用node()方法得到后繼節(jié)點，再得到前驅節(jié)點
succ = node(index);
pred = succ.prev;
}
// 4：遍歷數(shù)據(jù)將數(shù)據(jù)插入
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//創(chuàng)建新節(jié)點
Node newNode = new Node<>(pred, e, null);
//如果插入位置在鏈表頭部
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//如果插入位置在尾部，重置last節(jié)點
if (succ == null) {
last = pred;
}//否則，將插入的鏈表與先前鏈表連接起來
else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
addFirst(E e)
/**
* 在表頭插入指定元素.
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* 在表頭添加指定元素e
*/
private void linkFirst(E e) {
final Node f = first;
//新建節(jié)點，節(jié)點的前指針指向null，后指針原來的頭節(jié)點
final Node newNode = new Node<>(null, e, f);
first = newNode;
//如果原來的頭結點為null，更新尾指針，否則使原來的頭結點f的前置指針指向新的頭結點newNode
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
get方法
get(int index)
/**
* 返回指定索引處的元素
*/
public E get(int index) {
//檢查index范圍是否在size之內
checkElementIndex(index);
//調用node(index)去找到index對應的node然后返回它的值
return node(index).item;
}
/**
* 返回在指定索引處的非空元素
*/
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;
}
}
獲取頭節(jié)點（index=0）數(shù)據(jù)方法:
/**
* 返回鏈表中的頭結點的值.
*/
public E getFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
/**
* 獲取表頭節(jié)點的值，頭節(jié)點為空拋出異常
*/
public E element() {
return getFirst();
}
/**
* 返回頭節(jié)點的元素，如果鏈表為空則返回null
*/
public E peek() {
final Node f = first;
return (f == null) ? null : f.item;
}
/**
* 返回隊列的頭元素，如果頭節(jié)點為空則返回空
*/
public E peekFirst() {
final Node f = first;
return (f == null) ? null : f.item;
}
區(qū)別： getFirst(),element(),peek(),peekFirst() 這四個獲取頭結點方法的區(qū)別在于對鏈表為空時的處理，是拋出異常還是返回null。
getFirst() 和element() 方法將會在鏈表為空時，拋出異常
element()方法的內部就是使用getFirst()實現(xiàn)的。它們會在鏈表為空時，拋出NoSuchElementException
/**
* 返回鏈表中的尾結點的值.
*/
public E getLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
/**
* 返回隊列的尾元素，如果尾節(jié)點為空則返回空
*/
public E peekLast() {
final Node l = last;
return (l == null) ? null : l.item;
}
區(qū)別： getLast() 方法在鏈表為空時，會拋出NoSuchElementException，而peekLast() 則不會，只是會返回 null。
根據(jù)對象得到索引的方法 indexOf(Object o) /**
* 正向遍歷鏈表，返回指定元素第一次出現(xiàn)時的索引。如果元素沒有出現(xiàn)，返回-1.
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
//從頭遍歷
for (Node x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
//從頭遍歷
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
lastIndexOf(Object o)
/**
* 逆向遍歷鏈表，返回指定元素第一次出現(xiàn)時的索引。如果元素沒有出現(xiàn)，返回-1.
*/
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
//從尾遍歷
for (Node x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
//從尾遍歷
for (Node x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
刪除方法
remove() ,removeFirst(),pop(): 刪除頭節(jié)點
/**
* 刪除并返回棧頭元素
*/
public E pop() {
return removeFirst();
}
/**
* 刪除并返回頭節(jié)點，如果鏈表為空，拋出異常
*/
public E remove() {
return removeFirst();
}
/**
* 刪除并返回表頭元素.
*/
public E removeFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
removeLast(),pollLast(): 刪除尾節(jié)點
/**
* 刪除并返回表尾元素
*/
public E removeLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* 刪除并返回隊列的最后個元素，如果尾節(jié)點為空，則返回null.
*/
public E pollLast() {
final Node l = last;
return (l == null) ? null : unlinkLast(l);
}
區(qū)別： removeLast()在鏈表為空時將拋出NoSuchElementException，而pollLast()方法返回null。
remove(Object o) /**
* 正向遍歷鏈表，刪除出現(xiàn)的第一個值為指定對象的節(jié)點
*/
public boolean remove(Object o) {
//LinkedList允許存放Null
//如果刪除對象為null
if (o == null) {
//從頭開始遍歷
for (Node x = first; x != null; x = x.next) {
//找到元素
if (x.item == null) {
//從鏈表中移除找到的元素
unlink(x);
return true;
}
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
/**
* 刪除指定節(jié)點，返回指定元素的值
*/
E unlink(Node x) {
// assert x != null;
// 保存指定節(jié)點的值
final E element = x.item;
//得到后繼節(jié)點
final Node next = x.next;
//得到前驅節(jié)點
final Node prev = x.prev;
if (prev == null) {
//如果刪除的節(jié)點是頭節(jié)點,令頭節(jié)點指向該節(jié)點的后繼節(jié)點
first = next;
} else {
//將前驅節(jié)點的后繼節(jié)點指向后繼節(jié)點
prev.next = next;
x.prev = null;
}
if (next == null) {
//如果刪除的節(jié)點是尾節(jié)點,令尾節(jié)點指向該節(jié)點的前驅節(jié)點
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
其他方法
contains(Object o)
/**
* 判斷鏈表是否包含指定對象o
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
set(int index, E element)
/**
* 替換指定索引處的元素為指定元素element
*/
public E set(int index, E element) {
checkElementIndex(index);
Node x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
總結
LinkedList底層是雙向鏈表。
有序。
元素可重復。鏈表元素可重復。
隨機訪問效率低，增刪效率高。
參考資料：
https://segmentfault.com/a/11...
https://blog.csdn.net/panweiw...
https://github.com/Snailclimb...
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77696.html
摘要：介紹是線程不安全的，允許元素為的雙向鏈表。構造方法共有兩個構造方法，一個是創(chuàng)建一個空的構造函數(shù)，一個是將已有的添加到中。是將元素插入到的頭部。下一篇文章繼續(xù)分析上次分析了的結構和添加方法這次開始分析下面的。注意源碼版本為直接進入正題。 如果本文中有不正確的地方請指出由于沒有留言可以在公眾號添加我的好友共同討論。 1.介紹 LinkedList 是線程不安全的，允許元素為null的雙向鏈...
摘要：在次操作中其實即尾節(jié)點是共享資源，當多個線程同時執(zhí)行此方法的時候，其實會出現(xiàn)線程安全問題。同樣會出現(xiàn)并發(fā)安全問題，下面對此問題進行分析。 1.LinkedList源碼分析 LinkedList的是基于鏈表實現(xiàn)的java集合類，通過index插入到指定位置的時候使用LinkedList效率要比ArrayList高，以下源碼分析是基于JDK1.8. 1.1 類的繼承結構 LinkedLis...
摘要：它們會在鏈表為空時，拋出獲取尾節(jié)點數(shù)據(jù)方法兩者區(qū)別方法在鏈表為空時，會拋出，而則不會，只是會返回。 目錄： 0-1. 簡介 0-2. 內部結構分析 0-3. LinkedList源碼分析 0-3-1. 構造方法 0-3-2. 添加add方法 0-3-3. 根據(jù)位置取數(shù)據(jù)的方法 0-3-4. 根據(jù)對象得到索引的方法 0-3-5. 檢查鏈表是否包含某對象的方法 ...
摘要：一源碼分析本文分析雙向鏈表的查詢操作源碼實現(xiàn)。中源程序中，的查詢操作，通過函數(shù)實現(xiàn)。源程序中使用循環(huán)進行遍歷。表示鏈表元素索引，初值為。針對空元素的情況，用循環(huán)遍歷，查找元素為的節(jié)點，并返回索引。 一、contains源碼分析 本文分析雙向鏈表LinkedList的查詢操作源碼實現(xiàn)。jdk中源程序中，LinkedList的查詢操作，通過contains(Object o)函數(shù)實現(xiàn)。具體...
摘要：源碼分析是一個雙向鏈表的數(shù)據(jù)結構實現(xiàn)。對于支持隨機訪問數(shù)據(jù)的比如數(shù)組，應該優(yōu)先使用。一個有序的集合支持在頭和尾進行插入和刪除元素。的大多實現(xiàn)元素數(shù)量是沒有大小限制的。構造方法第一個是一個空的構造器，第二個構造器調用了方法。 LinkedList源碼分析 LinkedList是一個雙向鏈表的數(shù)據(jù)結構實現(xiàn)。 類的實現(xiàn)接口及繼承父類 public class LinkedList exten...
閱讀 2009·2021-11-24 09:39
閱讀 1878·2019-08-30 15:55
閱讀 2168·2019-08-30 15:53
閱讀 565·2019-08-29 13:16
閱讀 983·2019-08-26 12:20
閱讀 2379·2019-08-26 11:58
閱讀 3129·2019-08-26 10:19
閱讀 3296·2019-08-23 18:31
