简介
上次把ArryList源码浅析简单进行了下梳理，接下来咱们看下出自同一个List接口的LinkedList大概是什么样子的，它与ArrayList有什么相同和不同，它的优缺点是什么，咱们在文中都会涉及到。
继承层次
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList类实现了List接口和Deque接口，是一种链表类型的数据结构。
所有操作执行都与双向链表相似。操作索引将遍历整个链表，至于从头开始遍历还是从尾部开始遍历取决于索引的下标距离哪个比较近。
是否线程安全
非线程安全：同ArrayList一样，都是非线程安全，如果必须要同步使用，可通过添加synchronized 关键字或者使用（ConcurrentLinkedDeque高效的队列)
如何保证线程安全呢？
- 对使用LinkedList的方法进行synchronized修饰
- 可以使用JUC包下的ConcurrentLinkedDeque高效,因为这个底层采用的是CAS机制操作
数据结构
LinkedList链表结构
节点Node主要由三部分组成；pre：前驱引用，ele1：节点信息，next：后继引用。还有两个引用，分别指向头结点的first和指向尾结点的last。
首先，如果双端链表为空的时候，first 和last都必须为null
如果链表不为空，first的前驱引用一定是null，first的item一定不为null，同理，last的后继引用一定是null，last的item一定不为null
成员变量
/**
* 元素个数
*/
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
* 指向第一个节点
*/
transient LinkedList.Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
* 指向最后一个节点
*/
transient LinkedList.Node<E> last;
LinedList的字段比较少，多添加了两个引用first和last用来指向头尾节点，和一个size用来存储节点的个数，这样当计算元素个数的时候，只需要O(1)的时间复杂度。
构造函数
/**
* Constructs an empty list.
* 空的构造函数
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
* 集合构造函数，链表中的顺序按照集合中的元素顺序进行插入
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);//调用addAll方法，插入所有元素
}
两个构造函数，一个是初始化一个空的实例，另外一个是传入一个集合进行初初始化,在初始化的时候主要调用了addAll()方法，那么这个addAll()方法是怎么样添加元素的呢?
addAll操作
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the specified
* collection's iterator. The behavior of this operation is undefined if
* the specified collection is modified while the operation is in
* progress. (Note that this will occur if the specified collection is
* this list, and it's nonempty.)
*
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
* 插入指定集合的元素，从指定的index开始插入
*/
public boolean addAll(int index, Collection<? extends E> c) {
//检查是否数组越界 几乎所有的涉及到在指定位置添加或者删除或修改操作都需要判断传进来的参数是否合法
//checkPositionIndex(index)方法就起这个作用，方法后面会介绍
checkPositionIndex(index);
//集合转换为数组通过Object[] a存储
Object[] a = c.toArray();
// 数组长度
int numNew = a.length;
//如果添加的集合为空，则不后续进行，直接返回
if (numNew == 0) {
return false;
}
//succ 待添加节点的位置
//pred 待添加节点的前一个节点
LinkedList.Node<E> pred, succ;
if (index == size) {//如果插入的位置正好在LinkedList最后的位置或者第一次添加时
succ = null;//后继引用为空
pred = last;//前驱为last引用的尾节点
} else {
succ = node(index);//succ指向插入的节点位置 node（int index）方法后面分析
pred = succ.prev;//pred指向succ节点的前一个节点
}
//遍历数据中的元素，每次遍历，都新建一个节点，该节点的值就是数组中的对应值，pred用来存储pred节点
//next设置为空
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, null);
// 待插入节点pred为空，则代表插入第一个位置（头节点）
if (pred == null) {
first = newNode;
} else {//否则将当前节点的前一个节点next值设置为当前节点
pred.next = newNode;
}
//最后把pred节点指向当前节点
pred = newNode;
}
//新添加的节点位于元素的最后一个节点，将最后一个节点的pred指向last
if (succ == null) {
last = pred;
} else {//不为空时候，
pred.next = succ;//pred.next指向当前节点
succ.prev = pred;//pred 指向当前节点的prev
}
size += numNew;//size=size+数组长度
modCount++;//modCount（修改次数）自增
return true;
}
linkFirst 操作
/**
* Links e as first element.
* 把参数中的元素作为链表的第一个元素（addFirst 方法中调用）
*/
private void linkFirst(E e) {
LinkedList.Node<E> f = first;//因为我们需要把该元素设置为头节点，所以需要把头节点先存储起来
LinkedList.Node<E> newNode = new LinkedList.Node<>(null, e, f);//新建一个头节点，把next指向f，把自身设置为头节点
first = newNode;//将该元素赋值给frist节点
if (f == null) {//判断下f是否为空，如果为空，则代表LinkedList原为空，所以需要把新节点设置为尾节点
last = newNode;
} else {
f.prev = newNode;//如果LinkedList不为空，则原头节点的prev设置为新值
}
size++;//size++
modCount++;
}
linkLast 操作
/**
* Links e as last element.
* 把参数中的元素作为链表的最后一个元素(addLast 方法中调用)
*/
void linkLast(E e) {
LinkedList.Node<E> l = last;//因为我们需要添加该元素为尾节点，所以需要将尾节点临时存储
LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);// 新建一个节点，将该元素指向该节点，将原尾节点指向新节点的pred
last = newNode;//将last指向新节点
if (l == null) {//如果l为null，说明原来的linkedList为空，将新值指向头节点
first = newNode;
} else {//如果不为空，将原尾节点的next指向新值
l.next = newNode;
}
size++;//size和modCount自增
modCount++;
}
linkBefore 操作
/**
* Inserts element e before non-null Node succ.
* 指定的非空节点（succ）前添加一个节点（需要添加的节点，指定的节点）
*/
void linkBefore(E e, LinkedList.Node<E> succ) {
// assert succ != null;
LinkedList.Node<E> pred = succ.prev;// 新建变量，存储cucc节点的前一个节点，因为我们要在cucc前插入一个节点
LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);//接着新建一个节点，前驱设置为pred，后继设置succ
succ.prev = newNode;//将指定节点的prev设置为当前节点
if (pred == null) {//再判断一下f是否为空，如果为空的话，说明原来的LinkedList为空，所以同时也需要把新节点设
first = newNode;
} else {//将新节点的next设置为当前节点
pred.next = newNode;
}
size++;//size和modCount自增。
modCount++;
}
unlinkFirst 操作
/**
* Unlinks non-null first node f.
* 删除LinkedList中的第一个节点（该节点不为空（并且返回删除的节点的值） ）
* 私有方法，无法调用（在removeFirst 方法中调用）
*/
private E unlinkFirst(LinkedList.Node<E> f) {
// assert f == first && f != null;
E element = f.item;//新建一个变量，存储要删除节点的值
LinkedList.Node<E> next = f.next;//存储要删除的节点的下一个节点
f.item = null;//f节点设置为空
f.next = null; // help GC//f节点的下一个节点为空
first = next;//设置头节点为删除节点的下一个节点
if (next == null) {//下一个节点如果为空，last为空，
last = null;
} else {//下节点不为空，设置下节点的前驱为空，因为next为头节点
next.prev = null;
}
size--;//数量-
modCount++;//操作次数+1
return element;
}
unlinkLast操作
/**
* Unlinks non-null last node l.
* 删除LinkedList中的最后一个节点
*/
private E unlinkLast(LinkedList.Node<E> l) {
// assert l == last && l != null;
E element = l.item;//新建一个变量，存储要删除节点的值
LinkedList.Node<E> prev = l.prev;//获取删除节点的前一个节点
l.item = null;//设置删除节点为空
l.prev = null; // help GC//删除节点的前一个节点为空，有助于GC回收
last = prev;//设置最后一个节点为prev
if (prev == null) {//如果prev为空，则代表LinkedList为空，设置first节点为空
first = null;
} else {
prev.next = null;//如果不为空，前一个节点将为末节点，设置next为空
}
size--;//数量-
modCount++;//操作次数+
return element;
}
unlink 操作
/**
* Unlinks non-null node x.
* 删除该节点（不为空的节点）
* 三个变量 第
*/
E unlink(LinkedList.Node<E> x) {
// assert x != null;
E element = x.item;//第一个变量存储要删除节点的值，返回使用
LinkedList.Node<E> next = x.next;//第二个变量存储删除节点的下一个节点
LinkedList.Node<E> prev = x.prev;//三个变量存储删除节点的上一个节点
//完成与上个衔接
if (prev == null) {// 如果删除节点的前一个节点为空，则代表是头节点，将first设置为下一个节点
first = next;
} else {
prev.next = next;//不为空，上一个节点的next设置为下一个节点
x.prev = null;//删除节点的上一个节点设置null
}
//完成与下一个节点的衔接
if (next == null) {//如果删除节点的下一个节点为空，将前一个节点设置为尾节点
last = prev;
} else {//不为空，下一个节点的前节点设置为该删除节点的上一个节点，
next.prev = prev;
x.next = null;//删除节点的next设置为空
}
x.item = null;//删除节点值为null，
size--;//数量-
modCount++;//操作数量+
return element;//返回删除节点
}
Node操作(计算指定索引上的节点)
/**
* Returns the (non-null) Node at the specified element index.
* 查找指定索引的节点
*/
LinkedList.Node<E> node(int index) {
// assert isElementIndex(index);
// 判断当前索引值是否为集合总长度的前半部分
if (index < (size >> 1)) {
LinkedList.Node<E> x = first;
for (int i = 0; i < index; i++) {//遍历查找
x = x.next;
}
return x;
} else { // 判断当前索引值是否为集合总长度的后半部分
LinkedList.Node<E> x = last;
for (int i = size - 1; i > index; i--) {//遍历查找
x = x.prev;
}
return x;
}
}
学过折半的同学，有没有很熟悉😊，LinkedList进行了优化，不是全部遍历的查找，而是先比较一下index更靠近链表（LinkedList）的头节点还是尾节点。然后进行折半查找，获取相应的节点。
到目前大部分的私有方法全部讲完了，接下来的方法大多引用了上面的工具方法。
unlinkFirst 操作
/**
* Retrieves and removes the head (first element) of this list.
* 调用了unlinkedFirst
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
removeLast 操作
/**
* Removes and returns the last element from this list.
* 删除链表中的最后一个节点，并返回被删除节点的值上面一样调用了unlinkLast（Node last）方法。
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
LinkedList.Node<E> l = last;
if (l == null) {
throw new NoSuchElementException();
}
return unlinkLast(l);
}
contains 操作
/**
* Returns {@code true} if this list contains the specified element.
* More formally, returns {@code true} if and only if this list contains
* at least one element {@code e} such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return {@code true} if this list contains the specified element
* 是否包含此元素
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {//查找元素是否为空，为空则遍历查找空
for (LinkedList.Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
return index;
}
index++;
}
} else {//查找元素是否为空，不为空则遍历查找相等的值
for (LinkedList.Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
return index;
}
index++;
}
}
return -1;//找不到返回-1
}
LinkedList的大小
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return size;
}
添加一个新元素
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
从LinkedList中删除指定元素
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
查找同indexof差不多，查找到完毕后，调用nulink进行删除，就不一一赘述了。
清空LinkedList中的所有元素
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
直接遍历整个LinkedList，然后把每个节点都置空。最后要把头节点和尾节点设置为空，size也设置为空，但是modCount仍然自增.
设置对应index的节点的值
/**
* Replaces the element at the specified position in this list with the
* specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
//检查索引是否合法
checkElementIndex(index);
// 查找节点
LinkedList.Node<E> x = node(index);
//获取旧值
E oldVal = x.item;
//将新值赋值到item
x.item = element;
return oldVal;//返回旧值
}
在指定的位置上添加新的元素
public void add(int index, E element) {
//合法性检查
checkPositionIndex(index);
//判断添加位置是否是最后，如果是直接调用添加最后方法
if (index == size) {
linkLast(element);
} else {//不是，调用添加前方法
linkBefore(element, node(index));
}
}
优点在于删除和添加数据所消耗的资源较少，且比ArrayList效率高。
缺点：线程不安全，查找消耗的资源大，效率低，不能随机访问。
结束语
时间关系，没有把所有的方法进行一一诠释，回头慢慢补吧
由此可见如果数据量大，查询比较多，或者新增都是默认尾部新增，建议通过ArrayList
如果经常插入，或者删除不固定的顺序的值，建议使用LinkedList
网友评论