深入Java集合系列之二:LinkedList-阿里云开发者社区

开发者社区> 安全> 正文
登录阅读全文

深入Java集合系列之二:LinkedList

简介:

前言

LinkedList底层使用的双端链表,即每个节点既包含指向其后继的引用也包括指向其前驱的引用,LinkedList实现了List接口,继承了AbstractSequentialList类,在频繁进行插入以及删除的情况下效率较高。

LinkedList使用较多的是add、get和remove,源码的分析也将对这三个方法进行分析。

add方法

先看add方法:

public boolean add(E e) {
    //把e放在链表的最后一个位置
    linkLast(e);
    return true;
}
void linkLast(E e) {
    //last是链表最后一个节点的引用,现在l也指向最后一个节点
    final Node<E> l = last;
    //调用Node(Node<E> prev, E element, Node<E> next)构造方法
    final Node<E> newNode = new Node<>(l, e, null);
    //last节点指向newNode
    last = newNode;
    //如果l为空,则链表为空,直接把newNode链接在首节点后面即可,否则把newNode链接//在l节点的后面
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    //链表的元素个数增加1
    size++;
    //modCount是链表发生结构性修改的次数(结构性修改是指发生添加或者删除操作)
    modCount++;
}

可以看出,插入一个节点非常快,直接找到该位置的节点,修改节点的前驱以及后继的引用即可

get方法

下面看看get方法:

public E get(int index) {
    //检查index是否合法
    checkElementIndex(index);
    //如果合法就返回该节点位置的值
    return node(index).item;
}
//获取index位置上的节点
Node<E> node(int index) {
    //断言index在链表中
    // assert isElementIndex(index);
    //从第一个节点开始寻找直到index位置,然后返回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;
    }
}
//检查index值的合法性
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//判断index是否存在于链表中
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

可以看出获取index节点的值要从头或尾遍历链表,当数据量很大的时候,效率无疑是低下的

remove方法

最后看看remove操作:

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
E unlink(Node<E> x) {
    // assert x != null;
    //保存x节点的值
    final E element = x.item;
    //保存x节点的后继
    final Node<E> next = x.next;
    //保存x节点的前驱
    final Node<E> prev = x.prev;
    //如果前驱为null,说明要移除的是第一个节点,把First指向下一个节点就行
    if (prev == null) {
        first = next;
    } else {//否则,把x节点前驱的后继指向x的后继,并把x的前驱设置为null
        prev.next = next;
        x.prev = null;
    }
    //如果后继为null则要移除的是最后一个节点,则把last的引用指向x节点的前驱就ok
    if (next == null) {
        last = prev;
    } else {//否则,把x节点的后继的前驱设置为x节点的前驱,并x节点的后继设为null
        next.prev = prev;
        x.next = null;
    }
    //把x节点的值设为null,这样x就没有任何引用了,gc处理
    x.item = null;
    //把链表的size减少1
    size--;
    //结构性修改的次数增加1
    modCount++;
    //返回x节点的值,在移除之前已经保存在element中了
    return element;
}

LinkedList小结

LinkedList是基于双向循环链表实现的,除了可以当做链表来操作外,还可以当做栈、队列和双端队列使用(⊙o⊙)哦。同样是非线程安全的。

  1. 基于双端循环链表,并且头节点不存放数据
  2. 在查找和删除元素的时候,分为元素null和不为null进行处理,允许元素为空
  3. 不存在容量不足的问题
  4. Entry entry(int index)方法返回制定位置处的节点,使用加速动作。源码中先将index与长度size的一半(size >> 2)比较,如果index更小,那么就从位置0开始遍历到inde处,否则从size位置往前遍历,这样可以减少一部分不必要的遍历。实际上提高的效率有限。
  5. LinkedList是基于链表实现的,插入删除效率比较高,查找效率低。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
+ 订阅

云安全开发者的大本营

其他文章