LinkedList源码

嗯 今天看下 LinkedList，这个 最后会总结写 ArrayList 的区别吧

image

• 先看下构造函数

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

// 咳咳 怎么说呢 没想到你是这样的构造函数 什么都不干

在看LinkedList 的增删改查之前 我们得有一个认知 就是LinkedList 的 数据结构是 链表（从名字就看出来了），他的每个 节点 都是存在一个 内部类中

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

Node 节点 可以看出 LinkedList 是 一个双向链表 存了他自己 和 next 和 prev

接下去我们就可以 真正开始看 增删改查了

老规矩看下 add

• 增 add() ，addAll()

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

void linkLast(E e) {
        final Node<E> l = last;
        // 构建 node 节点
        final Node<E> newNode = new Node<>(l, e, null);

        //将最新的add  放到 最后    
        last = newNode;

        // 如果尾节点为空 新加入的变成 头结点
        if (l == null)
            first = newNode;
        else// 否则 之前的last 的 next 连接到新加入的节点

            l.next = newNode;

        size++;// 数组size 变大

        modCount++; // 增加修改次数
    }

• 删 remove

根据对象

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

根据 对象删除 比较简答 直接去 equals()

根据 下 标删除

    public E remove(int index) {
        // 判断是否越界
        checkElementIndex(index);

        return unlink(node(index));
    }

// 这段代码用到了 二分法查找 出node 节点  
Node<E> node(int index) {
    // assert isElementIndex(index);
             //  有是size>>1  这个意思就是 size/2  （  >> 效率高）
            //    index list的左半部分的时候

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

// unlink 就是清楚所有 有关节点 的链接然后 删除连接 节点前后 的 next 和prev 在相互连接
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;
    // 如果当前节点的 prev 为空  则当前节点的next 变成头节点
    if (prev == null) {

        first = next;

    } else {//否则 prev的  next  连接  当前节点的next 

        prev.next = next;

        x.prev = null;

    }

    if (next == null) { //如果next 则 prev 变成last 

        last = prev;

    } else { // 否则 next  prev  连接  当前节点的prev

        next.prev = prev;

        x.next = null;
    }

    x.item = null;  // 当前节点 全部连接置空  （提醒jvm GC ）
    size--; // 减少 数据大小
    modCount++; //增加修改次数
    return element;  // 弹出 当前节点的值
}

• 改 set

    public E set(int index, E element) {

        checkElementIndex(index);
        // 查处 
        Node<E> x = node(index);
        // 
        E oldVal = x.item;
        // 修改
        x.item = element;
        //返回
        return oldVal;
    }

查 get

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

嗯 看起来都很简单的样子 从源码来说 让我看看其他的扩展

这得从昨天 贴的 最后一段代码 说起 ArrayList 和 LinkedList遍历的时候

从今天可以看出来 LinkedList get 是 二分法查找 而 ArrayList 的get 是 直接数组的下标取出来 当然是 ArrayList 遍历快

我们在比较下 remove

回忆一下 ArrayList 增 是 调用底层本地 native 方法 整个数组 拷贝 移动的数组位置 之后 数组向前移动一位

但是LinkedList 增 移动的时候 就很简单了 unlink 改变下 链表 移动元素 前后的 prev 和next 就好了 理论上来说 是Linked remove 快点

实验下：

static final int N=50000;
static long timeListByPrev(List list){
    long start=System.currentTimeMillis();
    Object o = new Object();
    for(int i=0;i<N;i++)
        list.add(0, o);
    return System.currentTimeMillis()-start;
}
static long timeListByLast(List list){
    long start=System.currentTimeMillis();
    Object o = new Object();
    for(int i=0;i<N;i++)
        list.add(i);
    return System.currentTimeMillis()-start;
}

public static void main(String[] args) {
    System.out.println("前置插入 ArrayList耗时："+timeListByPrev(new ArrayList()));
    System.out.println("前置插入 LinkedList耗时："+timeListByPrev(new LinkedList()));

    System.out.println("后置插入 ArrayList耗时："+timeListByLast(new ArrayList()));
    System.out.println("后置插入 LinkedList耗时："+timeListByLast(new LinkedList()));
}

out:
    前置插入 ArrayList耗时：288
    前置插入 LinkedList耗时：4
    后置插入 ArrayList耗时：4
    后置插入 LinkedList耗时：3

可以看出 差距很大 四舍五入 差100倍 （本机测试 不代表任何基准）