LinkedList中查询(contains)和删除(remove)源码分析
一、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。
二、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<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> 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<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> 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的过程中，除了学习知识为我所用，也要避免闭门造车，多查看源码和其他优秀的项目程序，参考优秀的编程习惯和思想，从而积累经验，提高自己的水平。