LinkedList中查询(contains)和删除(remove)源码分析

timger 发布于2019-08-16 15:15 / 864人阅读

摘要：一源码分析本文分析双向链表的查询操作源码实现。中源程序中，的查询操作，通过函数实现。源程序中使用循环进行遍历。表示链表元素索引，初值为。针对空元素的情况，用循环遍历，查找元素为的节点，并返回索引。

一、contains源码分析

本文分析双向链表LinkedList的查询操作源码实现。jdk中源程序中，LinkedList的查询操作，通过contains(Object o)函数实现。具体见下面两部分程序：
①

public boolean contains(Object o) {
    return indexOf(o) != -1;
}

②

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

indexOf函数查询对象o在链表中的索引位置。

源码首先将元素为null的情形多带带判读剥离，个人分析，应该是如果不多带带分析，null元素在下边的for循环中，不能执行o.equals操作（编译器输入null.，会自动将已有输入替换为NullPointerException.，提示空指针异常）。

由于链表不同于数组，在内存中并非连续存储，因此访问某个元素需要遍历。源程序中使用for循环进行遍历。index表示链表元素索引，初值为0。

1、针对空元素（null）的情况，用for循环遍历，查找元素为null的节点，并返回索引index。for循环初始条件为头指针（无元素），判断条件为节点不为null，自增表达式为x重赋值为下个节点（利用节点x的next指针实现，在java中next为node对象的属性成员）。每次自增，index+1。
2、针对非空元素，遍历操作同上。函数结束的判断条件变为o.equals(x.item)，这里equals方法为Object超类的方法，程序中元素类型非Object也可调用。

两种情形下，链表遍历完毕（仍为return），表明该元素o在链表中不存在，因此返回-1。

二、remove源码对比

通过查阅，发现remove方法和contains方法的源码实现非常相似，列出如下：

/**
 * Removes the first occurrence of the specified element from this list, 
 * if it is present.  If this list does not contain the element, it is
 * unchanged. 
 * @param o element to be removed from this list, if present
 * @return {@code true} if this list contained the specified element
 */

public boolean remove(Object o) {
    if (o == null) {
        for (Node x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

对比发现，和contains类似，remove操作首先也是查找Object o是否存在与表中。空节点元素和非空节点的循环判断基本相同，在找到Object o后，区别与contains的返回索引，remove需要删除节点link（LinkedList的删除需要对next链进行重配置引用）。

删除节点的方法unlink的源码如下：

//Unlinks non-null node x. 
E unlink(Node x) {
    // assert x != null;
    final E element = x.item;
    final Node next = x.next;
    final Node prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;  //注：已从结构上修改此列表的次数。AbstractList属性
    return element;
}

分析：
删除节点程序中，需要考虑节点在链表中的不同位置，进行不同的操作。

1、节点于链表首端

此时，特殊操作是需要将first指针（引用）指向其后的节点。

first = next;

2、节点于链表尾端

此时，需要将上一个节点的next指针指向null，即上个节点称为尾节点。

last = prev;

3、节点于链表中间情况

如果不仔细思考，我们在写程序时，会直接在两个if判断后，将剩余的相关操作写在一起。而源码并没有这么做，稍作分析，就能看出，如果前一个if中，条件是prev，因此可对该节点的prev进行相关操作。而后续的if语句，还需判断该节点的next引用，因此在第一个if-else语句体中，不对next进行操作，否则更改后，后学的next已经不是该节点的原next值。

因此，第一个if-else中：

prev.next = next;
x.prev = null;

第二个if-else中：

next.prev = prev;
x.next = null;

三、总结

从LinkedList的源码可以看到，源程序中相应方法代码简洁，逻辑清晰正确，在学习java的过程中，除了学习知识为我所用，也要避免闭门造车，多查看源码和其他优秀的项目程序，参考优秀的编程习惯和思想，从而积累经验，提高自己的水平。

超融合服务器服务器托管 LinkedList 查询删除域名即将删除域名查询将要删除域名查询

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73371.html

LinkedList源码解析

摘要：我们来看相关源码我们看到封装的和操作其实就是对头结点的操作。迭代器通过指针，能指向下一个节点，无需做额外的遍历，速度非常快。不同的遍历性能差距极大，推荐使用迭代器进行遍历。LinkedList类介绍上一篇文章我们介绍了JDK中ArrayList的实现，ArrayList底层结构是一个Object[]数组，通过拷贝，复制等一系列封装的操作，将数组封装为一个几乎是无限的容器。今天我们来介绍JD...

番茄西红柿 2019-05-23 16:08 评论0 收藏0
LinkedList源码解析

摘要：我们来看相关源码我们看到封装的和操作其实就是对头结点的操作。迭代器通过指针，能指向下一个节点，无需做额外的遍历，速度非常快。不同的遍历性能差距极大，推荐使用迭代器进行遍历。LinkedList类介绍上一篇文章我们介绍了JDK中ArrayList的实现，ArrayList底层结构是一个Object[]数组，通过拷贝，复制等一系列封装的操作，将数组封装为一个几乎是无限的容器。今天我们来介绍JD...

番茄西红柿 2019-05-23 16:08 评论0 收藏0
Java 常用List集合使用场景分析

摘要：常用集合使用场景分析过年前的最后一篇，本章通过介绍，，，底层实现原理和四个集合的区别。和都是线程安全的，不同的是前者使用类，后者使用关键字。面试官会认为你是一个基础扎实，内功深厚的人才到这里常用集合使用场景分析就结束了。 Java 常用List集合使用场景分析过年前的最后一篇，本章通过介绍ArrayList，LinkedList，Vector，CopyOnWriteArrayList...

godruoyi 2019-08-16 11:03 评论0 收藏0
容器之Collection、Iterable、List、Vector(Stack)分析(三)

摘要：容器相关的操作及其源码分析说明本文是基于分析的。通常，我们通过迭代器来遍历集合。是接口所特有的，在接口中，通过返回一个对象。为了偷懒啊，底层使用了迭代器。即返回的和原在元素上保持一致，但不可修改。容器相关的操作及其源码分析说明 1、本文是基于JDK 7 分析的。JDK 8 待我工作了得好好研究下。Lambda、Stream。 2、本文会贴出大量的官方注释文档，强迫自己学英语，篇幅...

liaosilzu2007 2019-08-15 14:38 评论0 收藏0