Categories
程式開發

JAVA集合之LinkedList底層實現和原理


概述

LinkedList底層是基於雙向鍊錶(雙向鍊錶的特點)“,鍊錶在內存中不是連續的,而是通過引用來關聯所有的元素,所以鍊錶的優點在於添加和刪除元素比較快,因為只是移動指針,並且不需要判斷是否需要擴容,缺點是查詢和遍歷效率比較低。

LinkedList是基於雙向循環鍊錶實現的,除了可以當做鍊錶來操作外,實現了Deque接口,它還可以當做棧、隊列和雙端隊列來使用。 LinkedList同樣是非線程安全的,只在單線程下適合使用。 LinkedList實現了Serializable接口,因此它支持序列化,能夠通過序列化傳輸,實現了Cloneable接口,能被克隆。

數據結構

繼承關係

java.lang.Object
java.util.AbstractCollection
java.util.AbstractList
java.util.AbstractSequentialList
java.util.LinkedList

實現接口

Serializable, Cloneable, Iterable, Collection, Deque, List, Queue

基本屬性

transient int size = 0; //LinkedList中存放的元素个数
transient Node first; //头节点
transient Node last; //尾节点

/**
*LinkedList底层是双链表。
*实现了List接口可以有队列操作
*实现了Deque接口可以有双端队列操作
*实现了所有可选的List操作并且允许存储任何元素,包括Null

*所有的操作都提现了双链表的结构.
*索引进入List的操作将从开始或者结尾遍历List,无论任何一个指定的索引
*
*注意:这些实现(linkedList)不是同步的,意味着线程不安全
*如果有多个线程同时访问双链表,至少有一个线程在结构上修改list,那么就必须在外部加上同步操作(synchronized)(所谓的结构化修改
*操作是指增加或者修改一个或者多个元素,重新设置元素的值不是结构化修改),通常通过自然地同步一些对象来封装List来完成
*
*如果没有这样的对象存在,那么应该使用Collections.synchronizedList来封装链表。
*最好是在创建是完成,以访问意外的对链表进行非同步的访问。
*如:List list = Collections.synchronizedList(new LinkedList(...));
*
*此类的迭代器和迭代方法返回的迭代器是快速失败的:如果链表在迭代器被创建后的任何时间被结构化修改,除非是通过remove或者add方法操作的,
*否则将会抛出ConcurrentModificationException异常,因此,面对高并发的修改,迭代器以后快速而干净的失败以防承担
*冒着未确定的任意,非确定性行为的风险
*
*注意:迭代器快速失败的行为不能保证,一般来说,在存在并发修改的情况下不能确保任何的承诺,失败快速的迭代器
*尽最大努力抛出ConcurrentModificationException异常,因此,编写一个依赖于此的程序是错误的。
*正确性异常:迭代器的快速失败行为应该只用于检测错误
*
*
*
* @param
*/
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable

重要方法解析

添加方法

public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}

添加方法默認是添加到LinkedList的尾部,首先將last指定的節點賦值給l節點,然後新建節點newNode ,此節點的前驅指向l節點,data = e , next = null , 並將新節點賦值給last節點,它成為了最後一個節點,根據當前List是否為空做出相應的操作。若不為空將l的後繼指針修改為newNodw。 size +1 , modCount+1

刪除方法

public boolean remove(Object o) {
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;
}

刪除方法,先循環遍歷列表,找到item == o 的節點,在調用unlink()方法刪除