2.4、remove 方法
remove() 方法也有两个版本，一个是 remove(int index) 删除指定位置的元素；另一个是 remove(Object o)，通过 o.equals(elementData[index]) 来删除第一个满足的元素。
需要将删除点之后的元素向前移动一个位置。需要注意的是为了让 GC 起作用，必须显式的为最后一个位置赋 null 值。
- remove(int index) 方法
public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; //赋null值，方便GC回收 return oldValue; }
- remove(Object o) 方法
public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; }
03、LinkedList
“在上篇文章中，我们知道 LinkedList 同时实现了 List 接口和 Deque 接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。
LinkedList 底层通过双向链表实现，通过 first 和 last 引用分别指向链表的第一个和最后一个元素，注意这里没有所谓的哑元（某个参数如果在子程序或函数中没有用到，那就被称为哑元），当链表为空的时候 first 和 last 都指向 null。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { /**容量*/ transient int size = 0; /**链表第一个元素*/ transient Node<E> first; /**链表最后一个元素*/ transient Node<E> last; ...... }
/** * 内部类Node */ private static class Node<E> { E item;//元素 Node<E> next;//后继 Node<E> prev;//前驱 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
3.1、get 方法
get() 方法同样很简单，先判断传入的下标是否越界，再获取指定元素。
public E get(int index) { checkElementIndex(index); return node(index).item; } /** * 检查传入的index是否越界 */ private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
3.2、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; }
3.3、add 方法
同样的，add() 方法有两方法，一个是 add(E e)，另一个是 add(int index, E element)。
- add(E e) 方法
该方法在 LinkedList 的末尾插入元素，因为有 last 指向链表末尾，在末尾插入元素的花费是常数时间，只需要简单修改几个相关引用即可。
public boolean add(E e) { linkLast(e); return true; } /** * 添加元素 */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) //原来链表为空，这是插入的第一个元素 first = newNode; else l.next = newNode; size++; modCount++; }
- add(int index, E element)方法
该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。
具体分成两步，1.先根据 index 找到要插入的位置；2.修改引用，完成插入操作。
public void add(int index, E element) { checkPositionIndex(index); if (index == size) //调用add方法，直接在末尾添加元素 linkLast(element); else //根据index找到要插入的位置 linkBefore(element, node(index)); } /** * 插入位置 */ 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++; }
同样的，添加元素还有另外一个 addAll() 方法，addAll() 方法能够一次添加多个元素，根据位置不同也有两个方法，一个是在末尾添加的 addAll(Collection<? extends E> c) 方法，另一个是从指定位置开始插入的 addAll(int index, Collection<? extends E> c) 方法。
里面也 for 循环添加元素，addAll() 的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关，时间复杂度是线性增长！
3.4、remove 方法
同样的，remove() 方法也有两个方法，一个是删除指定下标处的元素 remove(int index)，另一个是删除跟指定元素相等的第一个元素 remove(Object o)。
两个删除操作都是，1.先找到要删除元素的引用；2.修改相关引用，完成删除操作。
- remove(int index) 方法
通过下表，找到对应的节点，然后将其删除
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }
- remove(Object o) 方法
通过 equals 判断找到对应的节点，然后将其删除
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; }
删除操作都是通过 unlink(Node<E> x) 方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。
/** * 删除一个Node节点方法 */ 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; }
04、Vector
Vector 类属于一个挽救的子类，早在 jdk1.0 的时候，就已经存在此类，但是到了 jdk1.2 之后重点强调了集合的概念，所以，先后定义了很多新的接口，比如 ArrayList、LinkedList，但考虑到早期大部分已经习惯使用 Vector 类，所以，为了兼容性， java 的设计者，就让 Vector 多实现了一个 List 接口，这才将其保留下来。
在使用方面，Vector 的 get、set、add、remove 方法实现，与ArrayList 基本相同，不同的是 Vector 在方法上加了线程同步锁 synchronized，所以，执行效率方面，会比较慢！
4.1、get 方法
public synchronized E get(int index) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); return elementData(index); }
4.2、set 方法
public synchronized E set(int index, E element) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }
4.3、add 方法
public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; }
4.4、remove 方法
public synchronized boolean removeElement(Object obj) { modCount++; int i = indexOf(obj); if (i >= 0) { removeElementAt(i); return true; } return false; }
05、Stack
在 Java 中 Stack 类表示后进先出（LIFO）的对象堆栈。栈是一种非常常见的数据结构，它采用典型的先进后出的操作方式完成的；在现实生活中，手枪弹夹的子弹就是一个典型的后进先出的结构。
在使用方面，主要方法有 push、peek、pop。
5.1、push 方法
push 方法表示，向栈中添加元素
public E push(E item) { addElement(item); return item; }
5.2、peek 方法
peek 方法表示，查看栈顶部的对象，但不从栈中移除它
public synchronized E peek() { int len = size(); if (len == 0) throw new EmptyStackException(); return elementAt(len - 1); }
5.3、pop 方法
pop 方法表示，移除元素，并将要移除的元素方法
public synchronized E pop() { E obj; int len = size(); obj = peek(); removeElementAt(len - 1); return obj; }
关于 Java 中 Stack 类，有很多的质疑声，栈更适合用队列结构来实现，这使得 Stack 在设计上不严谨，因此，官方推荐使用 Deque 下的类来实现栈！
06、总结
- ArrayList (动态数组结构)，查询快（随意访问或顺序访问），增删慢，但在末尾插入，速度与 LinkedList 相差无几！
- LinkedList（双向链表结构），查询慢，增删快！
- Vector（动态数组结构），相比 ArrayList 都慢，被 ArrayList 替代，基本不在使用。优势是线程安全（函数都是 synchronized），如果需要在多线程下使用，推荐使用并发容器中的工具类来操作，效率高！
- Stack（栈结构）继承于 Vector，数据是先进后出，基本不在使用，如果要实现栈，推荐使用 Deque 下的 ArrayDeque，效率比 Stack 高！
