JDK1.8 LinkedList源码剖析

类*享的变量和常用方法

1. int size：存放LinkedList的元素个数
2. Node first：存放第一个节点
3. Node last：存放最后一个节点
4. private static class Node ：内部类，有三个属性：E item，Node next，Node prev

类的实现

1. 构造方法有两种：
   
   1. 默认构造方法public LinkedList()，实例化一个空的链表list
   2. 带参构造方法public LinkedList(Collection<? extends E> c)，添加集合c中的所有元素到新LinkedList中
2. getFirst()、getLast()：直接返回first变量和last变量的item
3. public E removeFirst()：使用private E unlinkFirst(Node<E> f)方法移除linkedList第一个节点元素

final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
    last = null;
else
    next.prev = null;
size--;
modCount++;
return element;

4.public E removeLast()：与removeFirst方法类似
5.public void addFirst(E e)：使用private void linkFirst(E e)方法将e插入到第一个元素

final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
    last = newNode;
else
    f.prev = newNode;
size++;
modCount++;

6.public void addLast(E e)：方法与addFirst方法类似
7.public boolean contains(Object o)：使用public int indexOf(Object o)方法来判断linkedList中是否包含o，遍历LinkedList，若找到则返回index，未找到则返回-1：

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;

8.public boolean add(E e)：使用void linkLast(E e)方法在linkedList末尾增加元素

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

9.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;

E unlink(Node<E> x) {
    // assert x != null;
    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;
}

10.public boolean addAll(int index, Collection<? extends E> c)将集合c中的所有元素添加到linkedList中：

checkPositionIndex(index);

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

if (succ == null) {
    last = pred;
} else {
    pred.next = succ;
    succ.prev = pred;
}

size += numNew;
modCount++;
return true;

11.public void clear()清空LinkedList：

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

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

上述方法就是增删改查的基本方法，中间还有很多功能和上述方法相同，只是方法名不同的方法。

13.public Iterator<E> descendingIterator()：生成一个逆序迭代器

14.public Spliterator<E> spliterator()：生成一个并行迭代器，示例如下：

LinkedList<String> ll = new LinkedList<String>();
ll.add("xzc");
ll.add("qwe");
Spliterator<String> iterator = ll.spliterator();
iterator.forEachRemaining(ele -> System.out.print(ele));