【java容器的刻意练习】【七】LinkedList增删查改
上一篇我们知道了LinkedList的数据结构是双向链表，所以优缺点与双向链表类似。国际惯例，先上结论。
增删查改的优缺点
优点：
add(E)、addFirst(E)、addLast(E)这三个添加元素函数，不需查找直接添加，时间复杂度O(1)，而且不需要自动扩容- 删除头尾效率高。remove()删除元素，后面的元素需要逐个移动，时间复杂度O(N)。
缺点：
- 按索引或者内容删除，都比较慢。
remove(int index)通过折半查找所需节点O(N/2)；remove(Object o)通过顺序查找所需节点O(N)。- 插入效率较低。
add(index, E)通过折半查找后再添加，时间复杂度O(N/2)。- 内容查找
get(index)折半查找查找，很慢，时间复杂度 O(N/2)。- 内容修改
set(index, o)折半查找查找再修改，很慢，时间复杂度 O(N/2)。
优缺点源码级解读
一、添加元素
add(E)在上一篇已经分析过了，调用了内部保护函数linkLast，直接添加到双向链表最后面。
来看看addFirst(E)。
public void addFirst(E e) {
linkFirst(e);
}
原来调用了内部私有函数linkFirst(E e)。
/**
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
功能和linkedLast类似，先用临时引用f保存上一次第一个节点，然后把双向链表头first引用指向新的节点，新节点与上一次的第一个节点相互前后指向，这样新节点就是第一个节点。上一次的第一个节点就变成第二个节点。
addLast(E)就是调用linkedLast，就不再详述了。
接下来看add(index, E)，指定位置的插入。
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
如果插入的位置是链表尾，就直接调用linkLast，否者就调用linkBefore。这个linkedBefore究竟做了啥，而且有一个参数是node(index)，看样子是通过index获取节点？
我们先看node(index)。
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
原来，从双向链表根据传进来的位置，从中间开始往前或者往后找到需要的节点，那么，时间复杂度就是O(N/2)，省略掉常数可以简单记忆为O(N)。
知道了node(index)是获取index对应的节点Node，然后传进linkBefore，把新元素插入到找到的节点前面。
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
现在我们知道，
add(E)、addFirst(E)、addLast(E)这三个添加元素函数，不需查找直接添加，时间复杂度O(1)，而且不需要自动扩容。而add(index, E)通过折半查找后再添加，时间复杂度O(N/2)，省略掉常数可以简单记忆为O(N)。
双向链表add
二、删除元素
先看remove()。
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
很简单，原来是把第一个节点传入unlinkFirst(f)删除掉。来看看``unlinkFirst(f)`。
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
// 临时节点引用指向待删除元素的下一个节点
final Node<E> next = f.next;
// 把该节点清空，方便JVM垃圾回收
f.item = null;
f.next = null; // help GC
// 按需改变头尾引用
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
到这里，我们知道，这个remove()删除双向链表第一个节点，非常快，时间复杂度O(1)。
再看remove(int index)和remove(Object o)。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
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;
}
remove(int index)和remove(Object o)都是把需要删除的节点传给unlink(Node<E> 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++;
return element;
}
现在我们知道，
remove()不用查找，直接删除第一个节点，时间复杂度O(1)。remove(int index)通过折半查找后再添加，时间复杂度O(N/2)。remove(Object o)通过顺序查找，时间复杂度为O(N)。
三、查找元素get(int index)
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
很简单，就是调用node(index)函数，那还是折半查找，时间复杂度为O(N/2)。就不再详述了。
四、修改元素set(int index, E element)
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
同样调用node(index)函数，那还是折半查找，时间复杂度为O(N/2)。就不再详述了。
