JDK源码阅读——LinkedList

2019-11-11 02:55:28

字体：大中小

来源：转载

供稿：网友

序

作为数据结构中最基础的两种结构，数组与链表，在java中都有对应的实现——ArrayList与LinkedList。本文主要分析一下LinkedList中的比较重要的源码。 LinkedList是实现了List与Deque的双向链表。他不是线程安全的，在多线程情况下需要用户手动保证线程安全性。系统推荐使用下面的方法来保证线程安全。

List list = Collections.synchronizedList(new LinkedList(...));

Field

transient int size = 0; //头结点 transient Node<E> first; //尾节点transient Node<E> last;//节点本身是一个内部类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; } }

构造器

//构造一个普通的新链表对象 public LinkedList() { } //构造一个新链表，并将入参集合append到新链表中 public LinkedList(Collection<? extends E> c) { this(); addAll(c); }//append的核心代码在这里public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); //需要新增的结点个数 int numNew = a.length; if (numNew == 0) return false; //声明头结点与尾节点 Node<E> pred, succ; //从尾部开始appedn if (index == size) { succ = null; pred = last; } else { //从中间开始append,如图1 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; else pred.next = newNode; pred = newNode; }

上述循环的作用就是链表的插入操作，如图2。不停的移动pred，把输入的集合全都append到链表尾部。