源码分析Android题库

LinkedList

2022-02-24  本文已影响0人  Alsan_L3

实现:

基于链表的数据结构实现,实现了List和Deque接口,有List和队列的特性,底层实现是一个双端链表,内部有个私有类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;
        }
    }

增删改查都是通过操作该类中item(当前节点)、prev(前驱节点)、next(后继结点)实现。

特性:

  1. 插入和删除效率比较高
  2. 继承了队列的先进先出以及拥有栈的先进后出特性
  3. 保存了next和prev指针,浪费空间
  4. 线程不安全

源码解析:

我们先来看一下LinkedList的内部结构图,方便我们更好的理解源码,如下: 结构

每个节点都保存了上/下节点的指针,第一个节点的prev和最后一个节点的next都为空,这就是LinkedList内部的结构。

接下来我们从源码角度分析add流程,get和remove这里不分析,与add是类似的。
通过Ctrl+鼠标左键进入到LinkedList源码中,搜索add(index, E element)方法,先看该方法:

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

调用checkPositionIndex,去检查index是否合法,不合法直接抛出异常,然后判断index是不是最后一个元素,如果是,调用linkLast(element)方法,否则调用linkBefore(element, node(index))将该元素插入index前。

我们来看LinkLast(element)源码:

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

先用一个局部变量l保存当前表中最后一个元素last,然后新建一个节点newNode,将l当成newNode的prev节点,next节点为空(请参考上面链表结构图),然后将newNode指向last,完成最后一个节点的插入,如果l是空的,说明该链表之前就是个空列表,first节点也应该为newNode,如果不是,则需要更新l.next的指向,将l.next指向newNode,关联上链表,最后size加1.

接着看linkBefore(element, node(index))方法,我们先看他的第2个参数,需要通过index去查找到要插入的Node节点,这里通过node(index)去查找,看源码:

    Node<E> node(int index) {
        // assert isElementIndex(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在哪个区间,提升了一点效率。
接下来我们再看linkBefore(element, succ)方法本身,上源码:

    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

这里我们先将要插入节点的succ.prev保存到pred中,然后创建一个新节点newNode,该节点就是要插入的节点,所以该新节点的前驱节点就是pred,当前节点就是element,后继结点就是succ本身,将newNode放到succ.prev中,节点就插入进去了,然后判断pred是不是为null,如果是,说明列表之前是空的,first节点就是newNode,如果不是,需要指定pred.next节点为newNode。
这样就完成了一个Node插入到指定的位置中,其他操作基本都是这样实现的。

上一篇 下一篇

猜你喜欢

热点阅读