LinkedList特點(diǎn)總結(jié)
- LinkedList實(shí)現(xiàn)List接口，使用雙向鏈表實(shí)現(xiàn)陆盘，元素可以是null
- 可以被當(dāng)作堆棧，隊(duì)列冒版，雙端隊(duì)列使用
- 因其使用鏈表實(shí)現(xiàn)，查詢需要遍歷O(n)時(shí)間復(fù)雜度逞姿，插入時(shí)不再需要復(fù)制移動(dòng)元素O(1)時(shí)間復(fù)雜度
- 類中的iterator()方法和listIterator()方法返回的iterators迭代器是fail-fast的：當(dāng)某一個(gè)線程A通過iterator去遍歷某集合的過程中辞嗡，若該集合的內(nèi)容被其他線程所改變了；那么線程A訪問集合時(shí)滞造，就會(huì)拋出ConcurrentModificationException異常续室，產(chǎn)生fail-fast事件
- 和ArrayList一樣，不是線程安全的谒养，可以使用Collections.synchronizedList()變成支持并發(fā)的容器
注 LinkedList是由一個(gè)雙向鏈表來維護(hù)的挺狰，對(duì)于增刪改查元素理解最清晰地理解就是畫一張圖
源碼分析
考慮到之前是直接拷貝jdk源碼在源碼上通過注釋的方式進(jìn)行解讀，這樣看起來會(huì)比較雜亂蝴光，所以這次采用分塊解讀的方式
- 節(jié)點(diǎn)類
因?yàn)椴捎面湵淼姆绞綄?shí)現(xiàn)，所以需要先定義一個(gè)結(jié)點(diǎn)類达址，源碼中使用靜態(tài)內(nèi)部類的方式定義Node
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
可以看到定義的是一個(gè)雙向鏈表的Node類蔑祟，next指向其下一個(gè)Node,prev指向其上一個(gè)Node
- LinkedList的成員變量
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
size是當(dāng)前List中的元素個(gè)數(shù)，first和last都是Node類型的變量沉唠，分別指向鏈表的第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)疆虚，這三個(gè)變量都是transient，說明不希望進(jìn)行序列化
- 構(gòu)造方法
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
第一個(gè)構(gòu)造方法創(chuàng)建了一個(gè)空的LinkedList，第二個(gè)構(gòu)造方法是通過一個(gè)Collection接口的實(shí)現(xiàn)類對(duì)象進(jìn)行初始化径簿，首先調(diào)用第一個(gè)構(gòu)造方法創(chuàng)建一個(gè)空的LinkedList然后將參數(shù)指向的Collection中的元素添加到LinkedList中罢屈，元素的順序是Collection的iterator返回的順序
- 增加元素
LinkedList提供了頭插入addFirst(E e)、尾插入addLast(E e)篇亭、add(E e)缠捌、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)译蒂、add(int index, E element)這些添加元素的方法
源碼中提供了幾種增加元素的方法
public boolean add(E e) {
linkLast(e);
return true;
}
首先看add方法曼月，add方法中調(diào)用了linkLast方法，可以看出來是在list的末尾添上一個(gè)Node柔昼，這個(gè)方法與源碼中的addLast方法效果是相同的,只是add方法是有返回的哑芹，凡是返回比較雞肋
public void addLast(E e) {
linkLast(e);
}
順藤摸瓜，我們來看一個(gè)linkLast方法
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;
else
l.next = newNode;
size++;
modCount++;
}
- 首先通過last指針找到list的最后一個(gè)node捕透，然后創(chuàng)建一個(gè)新的node聪姿，這個(gè)newNode的next指向null，prev指向鏈表的最后一個(gè)節(jié)點(diǎn)
- 將鏈表的last指向創(chuàng)建的newNode
- 判斷之前找到的last node 如果該node是null說明原來list中沒有元素乙嘀，將創(chuàng)建的newNode賦值給first表示新node是最后一個(gè)元素也是第一個(gè)元素末购，如果l不是null，表示原來的list中有元素乒躺，此時(shí)將l的next指向newNode
- 最后需要將size++ 表示list元素多了一個(gè)
除了在list的尾巴上添加元素招盲，jdk源碼中還提供了在鏈表頭上添加元素的方法
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
addFirst會(huì)直接調(diào)用linkFirst完成插入操作，和上面linkLast方法其實(shí)是相仿的
- 首先找到first指向的元素嘉冒，有可能是一個(gè)null
- 創(chuàng)建一個(gè)新的node曹货，其prev指向null，因?yàn)閚ewNode是鏈表的第一個(gè)元素
- first指向newNode
- 如果f指向null讳推，表示鏈表原先是沒有元素的顶籽，那么newNode就是當(dāng)前唯一的元素，last也要指向newNode银觅，如果f不是null礼饱，表示原先鏈表中就有元素，需要將f指向的（此時(shí)是鏈表的第二個(gè)元素）的prev指向newNode
LinkedList同時(shí)也提供了指定index插入元素
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
- 首先進(jìn)行index的檢查究驴，保證index在[0,size]之間镊绪，如果是非法的index就拋出一個(gè)異常
- 如果index==size 就是在鏈表的最后進(jìn)行添加
- 否則調(diào)用linkBefore方法,完成元素添加
Node<E> node(int index) {
// assert isElementIndex(index);
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;
}
}
node(int index)這個(gè)方法返回在鏈表index位置上的node，返回的node是一個(gè)不為null的node洒忧，// assert isElementIndex(index);被注釋掉是因?yàn)榍懊嬉呀?jīng)進(jìn)行index == size 判斷就不再這邊進(jìn)行判斷了蝴韭，此外需要注意的是這邊使用了一個(gè)小技巧
- 如果index屬于鏈表的前面一半 index < (size >> 1) 就從first指向的元素進(jìn)行遍歷
- 如果index屬于鏈表的后面一半元素 就從last指向的元素進(jìn)行遍歷
- 返回node
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
linkBefore方法是最終完成插入操作的方法，同樣succ熙侍！=null也被注釋掉了榄鉴，因?yàn)樯厦鎛ode方法返回的是一個(gè)不為null的node履磨，linkBefore其實(shí)是一個(gè)雙向鏈表的插入操作
- 首先找到succ這個(gè)node prev指針指向的node，即succ左手邊的一個(gè)node
- 創(chuàng)建一個(gè)新的node庆尘，這個(gè)newNode prev指向pred剃诅，next指向succ
- 因?yàn)閖dk中在add(index,e)中僅對(duì)index==size的情況做了特殊處理，并沒有對(duì)index==0的時(shí)候做出特殊處理驶忌，即在第一個(gè)位置進(jìn)行插入矛辕，此時(shí)pred會(huì)是null，當(dāng)pred == null時(shí)表示index == 0在第一個(gè)位置進(jìn)行插入了位岔，pred右手邊指針需要指向newNode如筛，其他情況下pred.next指向newNode即可
- 訪問元素
LinkedList提供了getFirst()、getLast()抒抬、contains(Object o)杨刨、get(int index)、indexOf(Object o)擦剑、lastIndexOf(Object o)這些查找元素的方法
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
首先進(jìn)行index檢查妖胀，然后通過node(index)獲取index下的元素，最后通過node.item獲取到值惠勒，需要注意index檢查的時(shí)候與add index檢查的方法存在一點(diǎn)點(diǎn)細(xì)微的區(qū)別:index >= 0 && index < size;這里index必須在[0,size-1]
jdk還提供了一些取特殊位置元素的方法
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
- 刪除元素
LinkedList提供了頭刪除removeFirst()赚抡、尾刪除removeLast()、remove(int index)纠屋、remove(Object o)涂臣、clear()這些刪除元素的方法
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
首先index檢查與上面get中的方式相同，然后調(diào)用找到index指向的元素售担，調(diào)用unlink完成刪除
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> 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;
}
因?yàn)閚ode(index)方法返回一個(gè)非null的node赁遗，所以這邊把 x != null注釋掉了，unlink是一個(gè)雙向鏈表刪除的操作
- 首先獲取x的值族铆，值作為最后的返回
- 分別獲取x next和prev指向的元素
- 如果prev==null 表示要?jiǎng)h除的是第一個(gè)元素岩四，同樣，如果next == null表示要?jiǎng)h除的是最后一個(gè)元素
- 如果prev==null 將first指向鏈表的第二個(gè)元素即next指向的元素哥攘，否則prev.next = next;x.prev = null;
- 如果next==null 表示要?jiǎng)h除的是最后一個(gè)元素剖煌，last = prev;表示將x前面的一個(gè)元素作為鏈表的最后一個(gè)元素，否則 next.prev = prev;x.next = null;
- 最后x.item = null size-- modCount++
注 最好的方式還是畫一張圖幫助理解
同樣的逝淹，jdk也提供了一些在特殊位置刪除元素的方法
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
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 GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
不詳細(xì)展開了耕姊，需要注意的是比如刪除第一個(gè)節(jié)點(diǎn)的時(shí)候需要注意鏈表只有一個(gè)元素的情況
- 修改元素的值
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
需要注意最后返回原先的值
- 其他常見操作
public int size() {
return size;
}
返回當(dāng)前鏈表中元素的個(gè)數(shù)
public boolean contains(Object o) {
return indexOf(o) != -1;
}
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
返回元素o在鏈表中的index，準(zhǔn)確說應(yīng)該是第一個(gè)o的index栅葡，與ArrayList中處理的方式是一樣的茉兰，遍歷的時(shí)候?qū)ull和non-null做了判斷
- Queue操作
Queue操作提供了peek()、element()妥畏、poll()邦邦、remove()、offer(E e)這些方法
//獲取但不移除此隊(duì)列的頭醉蚁；如果此隊(duì)列為空燃辖，則返回 null
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//獲取但不移除此隊(duì)列的頭；如果此隊(duì)列為空网棍，則拋出NoSuchElementException異常
public E element() {
return getFirst();
}
//獲取并移除此隊(duì)列的頭黔龟，如果此隊(duì)列為空，則返回 null
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//獲取并移除此隊(duì)列的頭滥玷，如果此隊(duì)列為空氏身，則拋出NoSuchElementException異常
public E remove() {
return removeFirst();
}
//將指定的元素值(E e)插入此列表末尾
public boolean offer(E e) {
return add(e);
}
Deque操作提供了offerFirst(E e)、offerLast(E e)惑畴、peekFirst()蛋欣、peekLast()、pollFirst()如贷、pollLast()陷虎、push(E e)、pop()杠袱、removeFirstOccurrence(Object o)尚猿、removeLastOccurrence(Object o)這些方法
//獲取但不移除此隊(duì)列的頭；如果此隊(duì)列為空楣富，則返回 null
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//獲取但不移除此隊(duì)列的頭凿掂；如果此隊(duì)列為空，則拋出NoSuchElementException異常
public E element() {
return getFirst();
}
//獲取并移除此隊(duì)列的頭纹蝴，如果此隊(duì)列為空庄萎，則返回 null
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//獲取并移除此隊(duì)列的頭，如果此隊(duì)列為空骗灶，則拋出NoSuchElementException異常
public E remove() {
return removeFirst();
}
//將指定的元素值(E e)插入此列表末尾
public boolean offer(E e) {
return add(e);
}
// Deque operations
//將指定的元素插入此雙端隊(duì)列的開頭
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//將指定的元素插入此雙端隊(duì)列的末尾
public boolean offerLast(E e) {
addLast(e);
return true;
}
//獲取惨恭，但不移除此雙端隊(duì)列的第一個(gè)元素；如果此雙端隊(duì)列為空耙旦，則返回 null
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//獲取脱羡，但不移除此雙端隊(duì)列的最后一個(gè)元素；如果此雙端隊(duì)列為空免都，則返回 null
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
//獲取并移除此雙端隊(duì)列的第一個(gè)元素锉罐；如果此雙端隊(duì)列為空，則返回 null
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//獲取并移除此雙端隊(duì)列的最后一個(gè)元素绕娘；如果此雙端隊(duì)列為空脓规，則返回 null
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
//將一個(gè)元素推入此雙端隊(duì)列所表示的堆棧（換句話說，此雙端隊(duì)列的頭部）
public void push(E e) {
addFirst(e);
}
//從此雙端隊(duì)列所表示的堆棧中彈出一個(gè)元素（換句話說险领，移除并返回此雙端隊(duì)列的頭部）
public E pop() {
return removeFirst();
}
//從此雙端隊(duì)列移除第一次出現(xiàn)的指定元素侨舆，如果列表中不包含次元素秒紧，則沒有任何改變
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
//從此雙端隊(duì)列移除最后一次出現(xiàn)的指定元素,如果列表中不包含次元素，則沒有任何改變
public boolean removeLastOccurrence(Object o) {
//由于LinkedList中允許存放null挨下，因此下面通過兩種情況來分別處理
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) { //逆向向前
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
- 遍歷方式
- 使用迭代器iterator遍歷
Iterator iter = list.iterator();
while (iter.hasNext())
{
System.out.println(iter.next());
}
- 使用listIterator遍歷
ListIterator<String> lIter = list.listIterator();
//順向遍歷
while(lIter.hasNext()){
System.out.println(lIter.next());
}
//逆向遍歷
while(lIter.hasPrevious()){
System.out.println(lIter.previous());
}
- 使用foreach遍歷
for(String str:list)
{
System.out.println(str);
}
