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 释放节点。 还有其他方法这里就不一一列举了

四 总结

结合源码我们大致可以知道LinkList里维持了一个链表 每个链表单元是一个Node Node的prev指向前一个节点 next指向后一个节点 这样所有节点都串了起来 如图

有几点需要注意的是

• LinkedList的实现是基于双向链表的，且头结点中不存放数据
• LinkedList是基于链表实现的，因此不存在容量不足的问题，所以这里没有扩容的方法 不同与数组实现的ArrayList
• LinkedList是基于链表实现的，插入删除效率高，查找效率低

若经常查找又很少插入和删除 则推荐使用ArrayList 相反经常插入与删除 很少查找 则推荐使用LinkList 日常开发中，当然是ArrayList的使用频率更高些。下一篇准备讲解下Set系列...