LinkedList源码分析

简介

在前面的一遍文章里，我们讲了ArrayLis。ArrayList内部为动态数组，内存是连续的，并且它的查找和添加的性能非常高，为O(1)，但插入和删除却花费了O(N)时间，效率并不高。今天让我们来看看另一种List:LinkedList

LinkedList是一个链表(关于链表，这里不作过多叙述，有小伙伴不懂的话，可以去看看这篇文章)，实现了Deque接口，可以作为队列、栈和双端队列使用。在实现原理上，LinkedList是一个双向链表，并维护了长度、头节点和尾节点，每个元素在内存都是单独存放的，元素之间通过地址值链接在一起。就比如，小朋友手拉手。

结构

上图是LinkedList与ArrayList的数据结构。

内部属性

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    
    transient int size = 0;   // 表示链表长度,默认为0
    transient Node<E> first;  // 指向头节点，默认为null
    transient Node<E> last;   // 指向尾节点，默认为null

    }

内部类：
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;
        }
    }

结构

实现Deque:双端队列/栈，扩展了Queue的一些方法，包括了栈的一些操作

  public interface Deque<E> extends Queue<E> {
  void addFirst(E e);
  void addLast(E e);
  boolean offerFirst(E e);
  ...等等还有其他方法。见名知意：xxxFirset：操作头部  xxxLast：操作尾部，其他方法就不在这里叙述了。

继承Queue：队列

实现Cloneable:支持克隆
实现Serializable:支持序列化

Queue

所谓的队列，类似于日常生活中的各种排队，特点就是先进先出，在尾部添加元素，从头部删除元素。

API

作用	方法1	方法2
尾部添加元素	add	offer
查看头部元素	element	peek
删除头部元素	remove	poll

尾部添加元素

add():如果队列满了，继续使用add()方法会抛出此异常IllegalStateException
offer():如果队列满了，返回false

查看头部元素

element():队列为空时，查找头部元素，会抛出异常NoSuchElementException
peek():如果队列为空，返回null

删除头部元素

remove():如果队列空，继续删除，抛出异常NoSuchElementException
poll():如果队列为空，返回null

简单使用

 @Test
    public void test01(){
        Queue<Integer> queue=new LinkedList<>();
        // offer():当队列满时，返回false；add()：当队列满时，抛出异常
        queue.add(100);
        queue.add(100);
        queue.add(100);
        // peek() element() 查看元素 前者找不到元素会返回null，后者找不到元素会抛出异常 
        while(queue.peek()!=null){
            // poll() remove() 删除元素  前者队列为空时返回null，后者队列为空时抛出异常
            System.out.println(queue.poll());
        }
    }

说到队列了，我们再来看看栈。

栈

栈也是一种常用的数据结构，它与队列相反，特点是先进后出，后进先出。比如生活中的行李箱，最后放进去的东西总是最先拿出来。

API

栈相关的方法包括在了表示双端队列的接口Deque中，方法如下：

方法名称	含义
push()	入栈，在头部添加元素，栈的空间可能是有限的，如果栈满了，push会抛出异常IllegalStateException
pop()	出栈，返回头部元素，并且从栈中删除此元素，如果栈为空，会抛出异常NoSuchElementException
peek()	查看栈头部元素，不修改栈，如果栈为空，返回null

简单使用

@Test
    public void test01(){
        Deque<String> deque=new LinkedList<>();
        deque.push("a");
        deque.push("b");
        deque.push("c");
        while(deque.peek()!=null){
            System.out.println(deque.pop());
        }
    }
// 结果为  c b a

Stack

Java中还有一个类为Stack，它继承于Vector，是Vector的子类，它也有栈的一些方法，push()、peek()、pop()。这些方法都被synchronized修饰，实现了线程安全。

简单使用

 @Test
    public void test02(){
        Stack<Integer> stack=new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
  // 结果为：3 2 1

while判断条件中，我写了一句stask.isEmpty()，这里是因为各自的peek()方法实现有所不同。

这是linkedList里面的peek方法，可以看出获取到头节点，判断是否为null。

public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

这是stack里面的peek方法，可以看出会随时更新len的值，如果代码中使用peek判断，会抛出异常。

public synchronized E peek() {
        int     len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

栈与队列

栈和队列都是在两端进行操作

栈只操作头部，头部进行添加删除查看操作
队列两端都要操作。队列头部只查看和删除，尾部只添加操作。

构造方法

 public LinkedList() {
    }

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

add()方法

public boolean add(E e) {
        linkLast(e);
        return true;
}

void linkLast(E e) {
        // 让l指向尾节点
        final Node<E> l = last;
        // 创建新节点
        final Node<E> newNode = new Node<>(l, e, null);
        // 尾节点指向这个新节点
        last = newNode;
        // 如果原来链表节点为null，说明此时链表没有元素，头节点等于新节点
        // 如果原来链表节点不为null，说明链表此时有元素，让前一个节点的next指向新节点
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        // 增加链表大小
        size++;
        // 跟ArrayList一样，记录修改次数，便于迭代中间检测结构性变化
        modCount++;
    }

添加案例

@Test
    public void test01(){
        List<String> list=new LinkedList<String>();
        list.add("a");
        list.add("b");
    }

当执行第一行时，此时结果如下：

当添加完一个元素后，此时结果如下：

当添加完两个元素后，此时结果如下：

add(int index,E element)插入方法

public void add(int index, E element) {
        // 检查索引，判断index是否为-1或者是否大于size元素数量
        checkPositionIndex(index);
        // 如果index==size，说明要插入到最后一个元素的后面
        if (index == size)
            linkLast(element);
        else
            // 如果index!=size，说明要插入last节点之前的某一个位置
            linkBefore(element, node(index));
    }
    
    
private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }
    
void linkLast(E e) {
        final Node<E> l = last;
        // 新元素指向前驱节点，这里的前驱节点就是此时链表的尾节点
        final Node<E> newNode = new Node<>(l, e, null);
        // 尾节点指向此时的新节点
        last = newNode;
        // 如果last为null，说明链表没有元素，头节点指向新节点
        if (l == null)
            first = newNode;
        else
        // 如果last不为null，说明链表中存在元素，将最后一个元素的后继节点指向新节点
            l.next = newNode;
        size++;
        modCount++;
    }

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        // 通过传入的index，找到所在位置的当前元素，获取到当前元素的前驱节点
        final Node<E> pred = succ.prev;
        // 新元素的前驱节点指向当前元素的前驱节点，新元素的后继节点指向当前元素
        final Node<E> newNode = new Node<>(pred, e, succ);
        // 当前元素的前驱节点指向新元素
        succ.prev = newNode;
        // 如果此时元素的前驱节点为null，说明要插入的位置是头节点，first指向新元素
        if (pred == null)
            first = newNode;
        else
        // 如果此时元素的前驱节点不为null，当前元素的后继节点指向新元素
            pred.next = newNode;
        size++;
        modCount++;
    }

插入案例

 @Test
    public void test01(){
        List<String> list=new LinkedList<String>();
        list.add("a");
        list.add("b");
        list.add(1,"c");
    }

当执行完后，此时结果如下：

get(int index)

public E get(int index) {
        // 检查索引是否越界
        checkElementIndex(index);
        // 遍历
        return node(index).item;
    }


private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

Node<E> node(int index) {
        // assert isElementIndex(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;
        }
    }

remove(int index)删除方法

public E remove(int index) {
        // 检查索引是否越界
        checkElementIndex(index);
        return unlink(node(index));
    }
    
private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

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 {
        // 如果当前元素的前驱节点不为null，当前元素的节点指向当前元素的后继节点
            prev.next = next;
          // 将当前的元素的前驱节点置为null
            x.prev = null;
        }
        // 如果后继节点为null，说明此时当前元素的位置为最后一个元素，所以last指向当前元素的前驱节点
        if (next == null) {
            last = prev;
        } else {
        // 当前元素的后继节点指向当前元素的前驱节点
            next.prev = prev;
            // 当前元素的后继节点置为null
            x.next = null;
        }

        x.item = null; // 当前节点置为null，等待垃圾回收
        size--; // 元素数量减1
        modCount++; // 结构被修改了，所以++
        return element;  // 返回这个被删除的元素
    }

案例

@Test
    public void test01(){
        List<String> list=new LinkedList<String>();
        list.add("a");
        list.add("b");
        list.remove(1);
    }