两个删除操作都要1.先找到要删除元素的引用，2.修改相关引用，完成删除操作。在寻找被删元素引用的时候remove(Object o)调用的是元素的equals方法，而remove(int index)使用的是下标计数，两种方式都是线性时间复杂度。在步骤2中，两个revome()方法都是通过unlink(Node<E> x)方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。
//unlink(Node<E> x)，删除一个Node E unlink(Node<E> x) { 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;//let GC work size--; return element; } |
get()
get(int index)得到指定下标处元素的引用，通过调用上文中提到的node(int index)方法实现。
public E get(int index) {
checkElementIndex(index);//index >= 0 & index < size;
return node(index).item;
}
set()
set(int index, E element)方法将指定下标处的元素修改成指定值，也是先通过node(int index)找到对应下表元素的引用，然后修改Node中item的值。
public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element;//替换新值 return oldVal; } |
操作系统
