太极混元天尊 / 学习资料 / java集合框架之LinkedList 深度解析(二)

分享

   

java集合框架之LinkedList 深度解析(二)

2018-05-08  太极混元...

摘要:

LinkedList 和 ArrayList 一样,都实现了 List 接口,但其内部的数据结构有本质的不同。LinkedList 是基于链表实现的(通过名字也能区分开来),所以它的插入和删除操作比 ArrayList 更加高效。但也是由于其为基于链表的,所以随机访问的效率要比 ArrayList 差。

方法剖析

add(E e)
  1.   /**

  2.     * Appends the specified element to the end of this list.

  3.     *

  4.     *

    This method is equivalent to {@link #addLast}.

  5.     *

  6.     * @param e element to be appended to this list

  7.     * @return {@code true} (as specified by {@link Collection#add})

  8.     */

  9.    public boolean add(E e) {

  10.        linkLast(e);

  11.        return true;

  12.    }

该方法在LinkedList的末尾插入元素,因为有last指向链表末尾,在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可; 内部其调用了自己的方法 linkLast(E e)

  1.    /**

  2.     * Links e as last element.

  3.     */

  4.    void linkLast(E e) {

  5.        final NodeE> l = last;

  6.        final NodeE> newNode = new Node<>(l, e, null);

  7.        last = newNode;

  8.        if (l == null)

  9.        //如果是null说明这个链表为空,加入的节点指向头节点,同时也指向尾节点

  10.            first = newNode;

  11.        else

  12.            l.next = newNode;

  13.        size++;

  14.        modCount++;

  15.    }

该方法首先将 last 的 Node 引用指向了一个新的 Node(l),然后根据l新建了一个 newNode,其中的元素就为要添加的 e;而后,我们让 last 指向了 newNode。接下来是自身进行维护该链表。

add(int index, E element)
  1.   /**

  2.     * Inserts the specified element at the specified position in this list.

  3.     * Shifts the element currently at that position (if any) and any

  4.     * subsequent elements to the right (adds one to their indices).

  5.     *

  6.     * @param index index at which the specified element is to be inserted

  7.     * @param element element to be inserted

  8.     * @throws IndexOutOfBoundsException {@inheritDoc}

  9.     */

  10.    public void add(int index, E element) {

  11.        checkPositionIndex(index);//检查index是否越界

  12.        if (index == size)

  13.            linkLast(element);//在链表尾节点添加元素

  14.        else

  15.            linkBefore(element, node(index));//利用二分法查找添加位置

  16.    }

该方法是在指定 index 位置插入元素。如果 index 位置正好等于 size,则调用 linkLast(element) 将其插入末尾;否则调用 linkBefore(element, node(index))方法进行插入。

  1. private void checkPositionIndex(int index) {

  2.        if (!isPositionIndex(index))

  3.            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

  4.    }

  1.   /**

  2.     * Tells if the argument is the index of a valid position for an

  3.     * iterator or an add operation.

  4.     */

  5.    private boolean isPositionIndex(int index) {

  6.        return index >= 0 && index <> size;

  7.    }

优化查找链表的指定位置,利用二分法进行查找,方便更快的找到要添加元素的位置

  1.    /**

  2.     * Returns the (non-null) Node at the specified element index.

  3.     */

  4.    NodeE> node(int index) {

  5.        // assert isElementIndex(index);

  6. //size>>1等于size/2,就是链表的一半长度

  7.        if (index (size >> 1)) {

  8.            NodeE> x = first;

  9.            for (int i = 0; i index; i++)

  10.                x = x.next;

  11.            return x;

  12.        } else {

  13.            NodeE> x = last;

  14.            for (int i = size - 1; i > index; i--)

  15.                x = x.prev;

  16.            return x;

  17.        }

  18.    }

上面代码中的node(int index)函数有一点小小的trick,因为链表双向的,可以从开始往后找,也可以从结尾往前找,具体朝那个方向找取决于条件index < (size="">> 1),也即是index是靠近前端还是后端。

  1.    /**

  2.     * Inserts element e before non-null Node succ.

  3.     */

  4.    void linkBefore(E e, NodeE> succ) {

  5.        // assert succ != null;

  6.        final NodeE> pred = succ.prev;

  7.        final NodeE> newNode = new Node<>(pred, e, succ);

  8.        succ.prev = newNode;

  9.        if (pred == null)

  10.            first = newNode;

  11.        else

  12.            pred.next = newNode;

  13.        size++;

  14.        modCount++;

  15.    }

remove(Object o)
  1.    /**

  2.     * Removes the first occurrence of the specified element from this list,

  3.     * if it is present.  If this list does not contain the element, it is

  4.     * unchanged.  More formally, removes the element with the lowest index

  5.     * {@code i} such that

  6.     * (o==null ? get(i)==null : o.equals(get(i)))

  7.     * (if such an element exists).  Returns {@code true} if this list

  8.     * contained the specified element (or equivalently, if this list

  9.     * changed as a result of the call).

  10.     *

  11.     * @param o element to be removed from this list, if present

  12.     * @return {@code true} if this list contained the specified element

  13.     */

  14.    public boolean remove(Object o) {

  15.        if (o == null) {

  16.            for (NodeE> x = first; x != null; x = x.next) {

  17.                if (x.item == null) {

  18.                    unlink(x);//删除节点操作

  19.                    return true;

  20.                }

  21.            }

  22.        } else {

  23.            for (NodeE> x = first; x != null; x = x.next) {

  24.                if (o.equals(x.item)) {

  25.                    unlink(x);

  26.                    return true;

  27.                }

  28.            }

  29.        }

  30.        return false;

  31.    }

以下代码是删除节点的源码,由于逻辑有点儿混淆,不好解释,请大家仔细思考,其实很简单的。

  1.    /**

  2.     * Unlinks non-null node x.

  3.     */

  4.    E unlink(NodeE> x) {

  5.        // assert x != null;

  6.        final E element = x.item;

  7.        final NodeE> next = x.next;

  8.        final NodeE> prev = x.prev;

  9.        if (prev == null) {//删除的是第一个元素

  10.            first = next;

  11.        } else {

  12.            prev.next = next;

  13.            x.prev = null;

  14.        }

  15.        if (next == null) {//删除的是最后一个元素

  16.            last = prev;

  17.        } else {

  18.            next.prev = prev;

  19.            x.next = null;

  20.        }

  21.        x.item = null;//通知垃圾回收器回收

  22.        size--;

  23.        modCount++;

  24.        return element;

  25.    }

E remove(int index)
  1.    /**

  2. * Removes the element at the specified position in this list.  Shifts any

  3. * subsequent elements to the left (subtracts one from their indices).

  4. * Returns the element that was removed from the list.

  5. *

  6. * @param index the index of the element to be removed

  7. * @return the element previously at the specified position

  8. * @throws IndexOutOfBoundsException {@inheritDoc}

  9. */

  10. public E remove(int index) {

  11.    checkElementIndex(index);//检查是否越界

  12.    return unlink(node(index));通过索引找到节点,最后删除节点

  13. }

``

两个删除操作都要1.先找到要删除元素的引用,2.修改相关引用,完成删除操作。在寻找被删元素引用的时候

  1. remove(Object o)

调用的是元素的

  1. equals

方法,而

  1. remove(int index)

使用的是下标计数,两种方式都是线性时间复杂度。在步骤2中,两个

  1. revome()

方法都是通过

  1. unlink(NodeE> x)

方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。

总结:

该篇文章主要讲解了 LinkedList的添加元素和删除元素的方法,通过源码分析了底层是如何实现的,同时也借助了部分图表的形式,或许有些部分没有解释得很清楚,希望大家能够理解,而且这个部分有一些是很抽象的,需要大家自己好好想明白才行,后续文章会持续讲解 LinkedList的其余部分方法。

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>