LinkedList源码解析（空间结构和特性、常用方法、双端队列特性、ArrayList和LinkedList的区别总结）

本文主要是介绍LinkedList源码解析（空间结构和特性、常用方法、双端队列特性、ArrayList和LinkedList的区别总结），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、概念

LinkedList是一个双向不循环链表，继承了AbstractSequentialList，实现了 List ，Deque, Cloneable, Serializable接口，所以他有List的相关功能、同时还有双向队列、复制和序列化等功能。他的底层是使用Node组成的链表实现的，所以增删起来比较快，而查询时相对较慢。由于LinkedList里面的方法没有使用synchronized修饰，所以不是线程安全的。

2、空间结构

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;}}

JDK1.7之前是双向循环链表，属性只有head和size。JDK1.7之后改成了双向链表，将head改成了first和last，支持从头部和尾部插入。
链表的节点个数
Node的个数

    transient int size = 0;

链表的头节点
指向头节点，必须满足的条件：(first == null && last == null) ||(first.prev == null && first.item != null)

    transient Node<E> first;

链表的尾节点
指向尾节点，必须满足的条件: (first == null && last == null) ||(last.next == null && last.item != null)

    transient Node<E> last;

计数器
用于记录对List的修改次数，这里涉及到一个fail-fast快速失败机制，单线程时迭代器遍历集合中remove元素和多线程中一个线程遍历另一个线程remove元素时都会抛出ConcurrentModificationException。因为迭代器遍历时候，内部会将modCount赋给expectedModCount ，当集合结构改变时，modCount会被修改，迭代器每次next()和hahNext()方法都会检查expectedModCount与modCount是否相等，被改变时，抛出ConcurrentModificationException。所以在对集合遍历操作时，建议大家在迭代器中增删元素，不要直接操作集合的remove。引出fail-safe是快速安全机制，在多线程中使用（ConcurrentHashMap中）。任何对集合结构的修改都会在一个复制的集合上进行，因此不会抛出ConcurrentModificationException，但无法保证最终读取的数据是正确的元素，且需要复制集合，开销大。

	protected transient int modCount = 0;

构造函数
LindedList提供了空的构造函数和传入集合的构造函数，一个是空的构造器，一个是传入集合的构造器，传入集合的构造器中调用了addAll方法，后面在添加操作中讲到。

    public LinkedList() {}public LinkedList(Collection<? extends E> c) {this();addAll(c);}

3、常用方法

添加元素
LinkedList添加元素支持头插、尾插、指定索引插入和插入集合。由于继承了Deque,还支持addFirst、addLast和push等添加方法。

	//不指定index时将元素添加到链表末尾public boolean add(E e) {linkLast(e);return true;}//将元素添加到指定位置public void add(int index, E element) {//检查位置是否在链表中checkPositionIndex(index);//如果在尾部调用linkLastif (index == size)linkLast(element);else//否则调用linkBeforelinkBefore(element, node(index));}//添加集合到链表中public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}//添加元素到链表头public void addFirst(E e) {linkFirst(e);}//添加元素到链表尾public void addLast(E e) {linkLast(e);}//获取某个index上的指针值Node<E> node(int index) {//先比较下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;}}//添加元素到链表头private void linkFirst(E e) {final Node<E> f = first;//声明一个node,前继节点为null，后继结点为头节点，值为e（刚开始一位Node的构造函数是值，前继节点，后继结点的顺序，看着这个node很蒙蔽）final Node<E> newNode = new Node<>(null, e, f);//新的头节点为当前节点first = newNode;//如果之前链表没有头节点，即如果是空链表，则第一个节点和最后一个节点都是newNodeif (f == null)last = newNode;else//否则就将该元素插入到头节点前面f.prev = newNode;size++;modCount++;}//添加元素到链表尾void linkLast(E e) {final Node<E> l = last;//声明一个前继节点为尾节点后继结点为空，值为e的节点final Node<E> newNode = new Node<>(l, e, null);//新的尾节点为当前节点last = newNode;//如果没有尾节点，即如果是空链表，则第一个节点和最后一个节点都是newNodeif (l == null)first = newNode;else//否则就将该元素插入到尾节点后面l.next = newNode;size++;modCount++;}//添加元素到succ节点之前void linkBefore(E e, Node<E> succ) {//将succ的前继节点赋给predfinal Node<E> pred = succ.prev;//创建一个节点存放succ.prev的前继节点为前继节点，succ作为后继结点final Node<E> newNode = new Node<>(pred, e, succ);//把succ的前继节点改为newNodesucc.prev = newNode;//pred为空，则表示succ之前就是头节点，所以相当于插入头节点if (pred == null)first = newNode;else//否则把pred的后继节点改为newNodepred.next = newNode;size++;modCount++;}//将集合元素添加到当前链表尾部public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}//将集合元素添加到指定index后面public boolean addAll(int index, Collection<? extends E> c) {//index是否在链表长度中checkPositionIndex(index);//将集合转换为Object[]数组对象Object[] a = c.toArray();int numNew = a.length;if (numNew == 0)return false;//找出插入位置的前继节点和后继节点Node<E> pred, succ;//插入节点在链表末尾if (index == size) {succ = null;pred = last;} else {//插入节点在链表中，前继节点就是index位置的节点，后继节点是index之前的前继节点succ = node(index);pred = succ.prev;}//将集合数据插入链表for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;Node<E> newNode = new Node<>(pred, e, null);//前继节点为空，即链表为空if (pred == null)first = newNode;elsepred.next = newNode;//由于是循环插入，所以每次要更新当前位置的前继节点pred = newNode;}//如果后继结点为空，则最后一个插入的节点为后继结点if (succ == null) {last = pred;} else {//如果是从中间插入，需要把之前的链表后面一段连接上，前面succ==Node(index);pred.next = succ;succ.prev = pred;}//修改链表大小size += numNew; //计数器+1modCount++; return true;}

双端队列的插入方法，实际上是语法糖，调用的原本的add方法。

    public boolean offer(E e) {return add(e);}public boolean offerFirst(E e) {addFirst(e);return true;}public boolean offerLast(E e) {addLast(e);return true;}public void push(E e) {addFirst(e);}

获取元素
包括获取头节点和获取尾节点，由于有first和last指针，这两个操作都比较容易。获得某个节点时，就需要遍历指针。

	//获取某个节点值public E get(int index) {checkElementIndex(index);return node(index).item;}//获取某个index上的指针值Node<E> node(int index) {//先比较下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;}}

双端队列获取节点的方法。

//获取头节点值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;}//获取头节点值，当值为null时候不抛出异常而是返回nullpublic E peek() {final Node<E> f = first;return (f == null) ? null : f.item;}//获取头节点值，当值为null时候不抛出异常而是返回nullpublic E peekFirst() {final Node<E> f = first;return (f == null) ? null : f.item;}//获取尾节点值，当值为null时候不抛出异常而是返回nullpublic E peekLast() {final Node<E> l = last;return (l == null) ? null : l.item;}

删除操作
删除操作包括删除头节点、尾节点删除指定元素，删除第一次出现的元素、删除最后一次出现的元素和双端队列的删除方法。

	//删除头节点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);}//删除指定值的节点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;}//获取删除某个索引下的节点，unlink在get操作中讲到。public E remove(int index) {checkElementIndex(index);return unlink(node(index));}//删除头节点public E remove() {return removeFirst();}//删除元素第一次出现的指针，就是默认的removepublic boolean removeFirstOccurrence(Object o) {return remove(o);}//删除元素最后一次出现的指针，从尾节点向前面遍历。public boolean removeLastOccurrence(Object o) {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;}//删除头节点private E unlinkFirst(Node<E> f) {final E element = f.item;final Node<E> next = f.next;//头节点值赋为空f.item = null;//头节点的后继结点赋为空f.next = null; //后继结点作为头节点first = next;//如果后继结点为空，即为空链表。if (next == null)last = null;else//将头节点的前继节点设为空next.prev = null;size--;modCount++;return element;}//删除尾节点，思路跟删除头节点一样private E unlinkLast(Node<E> l) {final E element = l.item;final Node<E> prev = l.prev;l.item = null;l.prev = null; last = prev;if (prev == null)first = null;elseprev.next = null;size--;modCount++;return element;}//删除指定值的节点E unlink(Node<E> x) {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;}

双端队列中的删除方法，删除队头或队尾，也是语法糖，不多介绍。

   public E poll() {final Node<E> f = first;return (f == null) ? null : unlinkFirst(f);}public E pollFirst() {final Node<E> f = first;return (f == null) ? null : unlinkFirst(f);}public E pollLast() {final Node<E> l = last;return (l == null) ? null : unlinkLast(l);}public E pop() {return removeFirst();}

清空链表

	//一通null操作vans，剩下的事交给gcpublic void clear() {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++;}

返回元素索引位置
分为null和不是null遍历。

    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;}

对象克隆
集合中一般都是先了clone方法，继承了Object的clone方法，由于object中的clone是浅拷贝，只赋值对象本身，不复制里面的字段等等，所以，集合需要自己实现深拷贝。

    private LinkedList<E> superClone() {try {return (LinkedList<E>) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError(e);}}public Object clone() {//返回一个克隆好的空对象LinkedList<E> clone = superClone();初始化属性。clone.first = clone.last = null;clone.size = 0;clone.modCount = 0;//遍历当前链表，将所有制加入到克隆的对象中。for (Node<E> x = first; x != null; x = x.next)clone.add(x.item);return clone;}

集合序列化
由于LinkedList的空间是松散的，所以不需要考虑序列和时占用内存问题，直接遍历并写入/读取流。

    private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {s.defaultWriteObject();s.writeInt(size);for (Node<E> x = first; x != null; x = x.next)s.writeObject(x.item);}private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {s.defaultReadObject();int size = s.readInt();for (int i = 0; i < size; i++)linkLast((E)s.readObject());}

4、总结

1. LinkedList 底层基于Node链表实现的，所以查找元素时候要从头或者从尾开始遍历查找，速度较慢，插入或删除元素时不需要移动元素，适合增删多的操作。
2. LinkedList不需要默认容量，他在内存中的空间是零散开的，通过指针连接起来，所以比较节省整块的空间，但是由于LinkedList一个节点需要存储元素值、存储前继和后继节点，所以总体占用的空间会大一点。
3. LinkedList实现了Deque接口，可以作为双端队列，从链表的两端增删元素。
4. LinkedList不是线程安全的，所以有modCount的存在，直接修改集合时都会使modCount++，所以遍历LinkedList时删除元素时使用iterator的remove方法，该方法会同步modCount值，避免出现ConcurrentModificationException异常。

5、ArrayList和LinkedList的区别

看过了ArrayList和LinkedList的源码后，做个总结：

1. 顺序插入的速度ArrayList会快些，LinkedList的速度慢一些。因为ArrarList只是在指定的位置上赋值即可，而LinkedList则需要创建Node对象，并且需要建立前后关联，如果对象较大的话，速度回慢一些。
2. ArrayList空间是连续的，且容量可能冗余，会浪费一段内存。LinkedList一个节点需要存储元素值、存储前继和后继节点，所以总体占用的空间会大一点。
3. ArrayList遍历推荐使用for循环，而LinkedList则推荐使用foreach。因为LinkedList的迭代器对遍历时候next方法做了优化。
4. 插入、删除元素的快慢取决于该元素在集合中哪一部分，前半段时LinkedList的效率快于ArrayList，因为ArrayList将复制该元素后的所有元素；越往ArrayList需要复制的元素变少，速度也会加快。而LinkedList始终要先从前或者后寻址，再插入。如果你确定你插入的元素经常在后半段时也是可以使用ArrayList的，如果不确定那还是使用LinkedList吧。
5. LinkedList增删元素时要先遍历链表找到对应元素再执行增删操作，所以时间复杂度为O(n)。增删头/尾节点时不用遍历，时间复杂度为O(1)。查询指定元素时需要从头/尾节点遍历，所以时间复杂度为O(n)。查询头/尾节点时不用遍历，时间复杂度为O(1)。ArrayList增删元素时需要遍历数组，所以时间复杂度为O(n)。添加到尾部时不用遍历，时间复杂度为O(1)。数组查找指定元素下标时需要遍历数组，时间复杂度为O(n)，查找指定下标元素时不用遍历数组，所以时间复杂度为O(n)。

这篇关于LinkedList源码解析（空间结构和特性、常用方法、双端队列特性、ArrayList和LinkedList的区别总结）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---