JDK源码系列（1）----LinkedList 源码分析

LinkedList 源码分析

LinkedList 实现List、Deque接口，是列表的链式实现，可以存储列表数据，也可以用作栈和队列。

1.成员变量

transient int size = 0; // 存储节点个数 transient Node<E> first; // 存储首节点 transient Node<E> last; // 存储末尾节点

2.基本结构 - 双向链表

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

3.核心方法分析

3.1 add方法

添加一个元素到队尾。

public boolean add(E e) { linkLast(e); return true; } public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }

内部方法 linkLast构造一个Node节点，并将其链接到末尾，并根据情况修改first、last节点信息。

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

内部方法 linkBefore构造一个Node节点，并将其链接到succ节点之前，并根据情况修改first节点信息。

void linkBefore(E e, Node<E> succ) { 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++; }

3.2 remove方法

移除位于链表第index个的节点

public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } 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，获取节点x的前驱与后继，将前驱节点的后继设置为x节点的后继节点，将后继节点的前驱设置为x节点的前驱，根据节点x的所在位置是否为首节点或尾节点，调整first、last的值。

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

3.3 get 方法

get方法获取index位置的节点的值。

public E get(int index) { checkElementIndex(index); return node(index).item; }

node方法判断index位于前半段还是后半段，通过向前/向后遍历获取指定节点。

Node<E> node(int 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; } }

3.4 set方法

set方法修改index所指节点的值。

public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; }

3.5 Deque 方法

peek() : 获取队头元素值,不移除节点。poll() : 获取并移除队头节点，queue出队操作。offer() : 添加一个元素到链表末尾，queue入队操作。push() : 添加一个元素到队头，stack 压栈操作。pop() : 获取并移除队头元素，stack出栈操作。 public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } public boolean offer(E e) { return add(e); } public void push(E e) { addFirst(e); } public E pop() { return removeFirst(); }

4.ArrayList VS LinkedList

1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Node对象。

2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。

3．LinkedList不支持高效的随机元素访问。

4．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。