转载

Java 集合之LinkList

在上一篇介绍了Java 集合之ArrayList主要讲解了ArrayList的一些方法和具体实现，ArrayList是基于数组来实现，当插入新元素时，其后面的元素的位置都需要移动，这显而易见是个影响性能的操作，数据量一大，再频繁的执行插入操作那...照例我们先看集合的结构图

2.结构

LinkList和ArrayList 同属于List接口的,看下详细的结构图实现类，那么两者的方法应该大致相同

AbstractSequentialList类是 AbstractList的一个子类，提供了一个基本的list接口实现，为了顺序访问的数据存储结构(链表)提供了最小化的实现。AbstractSequentiaList是在迭代器基础上实现的get、set、add等方法。

Deque接口继承Queue接口，两端都允许插入和删除元素，即双向队列。

实现了Cloneable，能被克隆,实现了Serializable，支持序列化

我们查看下LinkList类中的方法

顺便附上AbstractSequentiaList抽象类方法

通过查看源码发现AbstractSequentiaList是在迭代器基础上实现的get、set、add等方法，而这个迭代是在子类去实现

public abstract ListIterator<E> listIterator(int index);
复制代码

3.源码分析

一.成员变量

transient int size = 0;
transient Node<E> first;
transient Node<E> last;
复制代码

size 元素个数
first 指向头节点
last 指向尾节点

Node是个内部类

private static class Node<E> {
        E item; //结点的值
        Node<E> next;   //结点的后向指针
        Node<E> prev;   //结点的前向指针

        //构造方法中已完成Node成员的赋值
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;    //结点的值赋值为element
            this.next = next;       //后向指针赋值
            this.prev = prev;       //前向指针赋值
        }
    }

复制代码

二.构造方法

public LinkedList() {
    }

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

空构造方法构造了一个空的List 其中size为0 first和last都为null ,没有任何元素 LinkedList(Collection<? extends E> c)构造一个包含指定Collection中所有元素的列表该方法先调用空构造器然后addAll()把Collection中所有元素添加进去

三.常用方法

addAll

public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
 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;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {////for循环结束后，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;
}
复制代码

此方法较长主要操作就是检查index是否越界将collection转化成数组循环数组将数组里面的元素创建为节点并按照顺序连起来修改当前节点个数size

add

public boolean add(E e) {
        linkLast(e);
        return true;
    }
   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++;
    }    
复制代码

add 方法直接调用了 linkLast 方法，而 linkLast 方法是不对外开放的。该方法做了三件事情，新增一个节点，改变其前后引用，将 size 和 modCount 自增 1。其中 modCount 是记录对集合操作的次数。

remove

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(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 {
            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;
    }    
复制代码

检查下标是否越界，然后调用 unlink 释放节点。还有其他方法这里就不一一列举了