LinkedList详解

LinkedList摘要

LinkedList是链表形式的List,由于ArrayList读取速度快,但插入和删除速度慢,而LinkedList插入和删除只需改动指针,所以LinkedList被引入。

LinkedList继承体系

LinkedList继承了AbstractSequentialList类,实现了List、Deque(由此可知LinkedList可以作为队列使用)、Cloneable、Serializable接口。继承体系如下。

LinkedList数据结构

LinkedList是基于双向链表实现的,如下图所示(可能有所差别),具体的链表部分请参考数据结构的相关章节,这里不再展开叙述。

LinkedList内部定义了一些成员变量,size为LinkedList逻辑长度,初始化为0;first引用第一个节点,而last引用最后一个节点。

transient int size = 0;

transient Node<E> first;

transient Node<E> last;

下面的代码为常规的定义LinkedList以及对其添加元素的过程,LinkedList初始化后,first和last都为空,而size为0,例如下图所示。

public static void main(String[] args) {
    List<Person> list = new LinkedList<Person>();
    list.add(new Person("张三", 20));
    list.add(new Person("李四", 21));
    list.add(new Person("王五", 22));
    list.add(new Person("赵六", 23));
}

我们再来看一下LinkedList定义的Node是何方神圣?这不就是双向链表的简单定义么,一个存储元素值,另外两个一个指向前一个节点,一个指向后一个节点。

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

我们继续查看一下add添加元素的方法,add方法只是调用了linkLast方法,当我们add一个张三时,具体操作流程看下方代码展示。

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

void linkLast(E e) {
    final LinkedList.Node<E> l = last;
    final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

添加张三后内存布局如下图所示。

当我们再添加“李四”这个节点时,代码部分执行流程如下。

void linkLast(E e) { // e是李四对象的引用
    final Node<E> l = last; // last已经是包含张三这个Person对象的Node引用,赋值给l
    final Node<E> newNode = new Node<>(l, e, null); // 包含Person张三的Node,Person李四作为参数创建Node
    last = newNode; // last赋值为新的newNode
    if (l == null)
        first = newNode;
    else
        l.next = newNode; // 由于l不为空,执行这一句,张三这个Node的next指向新的Node
    size++; // 长度加1
    modCount++; // 修改次数加1
}

添加李四后对象图如下所示。

继续添加王五、赵六后内存布局图如下。

ArrayList与LinkedList比较

顺序插入时,两者速度都很快,但ArrayList快于LinkedList,ArrayList是数组实现,数组是提前创建好的;而LinkedList需要不断的new出新节点。

LinkedList需要维护前后节点,更消耗内存。

LinkedList适合迭代遍历,ArrayList适合循环遍历;不要使用普通for循环遍历LinkedList,也不要使用迭代遍历ArrayList。



end
  • 作者:JJ(联系作者)
  • 发表时间:2021-02-17 23:29
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 转载声明:如果是转载博主转载的文章,请附上原文链接
  • 公众号转载:请在文末添加作者公众号二维码(公众号二维码见右边,欢迎关注)
  • 评论