java提高篇---LinkedList(二)
Entry e = new Entry((E) a[i], successor, predecessor);
//将插入位置前一个节点的下一个元素引用指向当前元素
predecessor.next = e;
//修改插入位置的前一个节点，这样做的目的是将插入位置右移一位，保证后续的元素是插在该元素的后面，确保这些元素的顺序
predecessor = e;
}
successor.previous = predecessor;
//修改容量大小
size += numNew;
return true;
}
复制代码
在addAll()方法中，涉及到了两个方法，一个是entry(int index)，该方法为LinkedList的私有方法，主要是用来查找index位置的节点元素。
复制代码
/**
* 返回指定位置(若存在)的节点元素
*/
private Entry entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
//头部节点
Entry e = header;
//判断遍历的方向
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
复制代码
从该方法有两个遍历方向中我们也可以看出LinkedList是双向链表，这也是在构造方法中为什么需要将header的前、后节点均指向自己。
如果对数据结构有点了解，对上面所涉及的内容应该问题，我们只需要清楚一点：LinkedList是双向链表，其余都迎刃而解。
由于篇幅有限，下面将就LinkedList中几个常用的方法进行源码分析。
2.4、增加方法
add(E e): 将指定元素添加到此列表的结尾。
public boolean add(E e) {
addBefore(e, header);
return true;
}
该方法调用addBefore方法，然后直接返回true，对于addBefore()而已，它为LinkedList的私有方法。
复制代码
private Entry addBefore(E e, Entry entry) {
//利用Entry构造函数构建一个新节点 newEntry，
Entry newEntry = new Entry(e, entry, entry.previous);
//修改newEntry的前后节点的引用，确保其链表的引用关系是正确的
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
//容量+1
size++;
//修改次数+1
modCount++;
return newEntry;
}
复制代码
在addBefore方法中无非就是做了这件事：构建一个新节点newEntry，然后修改其前后的引用。
LinkedList还提供了其他的增加方法：
add(int index, E element)：在此列表中指定的位置插入指定的元素。
addAll(Collection< extends E> c)：添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。
addAll(int index, Collection< extends E> c)：将指定 collection 中的所有元素从指定位置开始插入此列表。
AddFirst(E e): 将指定元素插入此列表的开头。
addLast(E e): 将指定元素添加到此列表的结尾。
2.5、移除方法
remove(Object o)：从此列表中移除首次出现的指定元素（如果存在）。该方法的源代码如下：
复制代码
public boolean remove(Object o) {
if (o==null) {
for (Entry e = header.next; e != header; e = e.next) {
if (e.element==null) {
remove(e);
return true;
}
}
} else {
for (Entry e = header.next; e != header; e = e.next) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}
复制代码
该方法首先会判断移除的元素是否为null，然后迭代这个链表找到该元素节点，最后调用remove(Entry e)，remove(Entry e)为私有方法，是LinkedList中所有移除方法的基础方法，如下：
复制代码
private E remove(Entry e) {
if (e == header)
throw new NoSuchElementException();
//保留被移除的元素：要返回
E result = e.element;
//将该节点的前一节点的next指向该节点后节点
e.previous.next = e.next;
//将该节点的后一节点的previous指向该节点的前节点
//这两步就可以将该节点从链表从除去：在该链表中是无法遍历到该节点的
e.next.previous = e.previous;
//将该节点归空
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}
复制代码
其他的移