LinkedList中查询(contains)源码分析

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<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> 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。