共计 870 个字符，预计需要花费 3 分钟才能阅读完成。
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。