链表：ArrayList, LinkedList

定义

List就是元素的有序存储结构，需要指出的是：这个有序指的是逻辑上的有序，而不特指实际物理存储形式。

它规定了这样的一组存储规则，A0就是第一个元素，A(n-1)就是最后一个元素，n便是List的长度，Ai一定在A(i-1)的后面，在A(i+1)的前面。

ADT

ArrayList

基于Array实现的链表，是最简单的一种实现方式。

1. printList 和find是需要依次遍历的，线性复杂度。

2. findKth 是O(1)的，又叫随机读取

3. insert和remove代价很高，因为存储位置代表了逻辑顺序，因此需要移动元素的位置。

存在扩容问题，适用于findKth比较多的场景，效率高，对于频繁插入、删除是不擅长的。

LinkedList

基于非连续内存实现，体现逻辑上的顺序，而不是存储上的前后顺序。

1. printList 和find是需要依次遍历的，线性复杂度。

2. findKth 是线性的

3. insert和remove是高效的，只需要修改指针即可

适用于频繁插入、删除比较多的场景，效率高，对于频繁的查询是不擅长的。

移除元素只需要修改指向

插入元素也不难

DoubleLinkedList

维护next的同时，维护previous元素的指针

Collection、List、ArrayList、LinkedList

Collection

add用于追加元素到末尾

addAll用于批量追加元素到末尾

clear清空链表

contains判断元素是否存在于链表中

containsAll用于批量判断

isEmpty判断是否包含元素

iterator是迭代器，用于遍历链表

remove用于移除指定的元素

removeAll用于批量删除

retainAll用于取交集

size常用于获取数据长度，便于遍历

toArray用于转换为数组，常用toArray(T[])

迭代器

迭代器主要包含三个方法：

hasNext判断是否还有元素

next用于获取下一个元素

remove是移除上一个迭代获取到的元素。

增强for循环的本质也是迭代器

Collection接口也有一个remove方法，我们是比较倾向于使用迭代器的remove方法的。

因为，

1. 迭代器中是迭代到这个元素才会删除，避免了Collection删除不存在元素的问题

2. 当存在迭代器进行遍历集合元素时，如果集合调用了add，remove，clear操作，会导致迭代器抛出并发修改异常。

3. 迭代器自带remove方法更安全，更灵活

4. 迭代器remove的是上一次调用next方法返回的值

List

List接口继承自Collection，所以包含Collection的所有方法，与此同时还进行了重写和扩展：

get方法用于获取指定位置上的元素

set用于设置指定位置上的元素

add用于追加元素

这里的remove不同于Collection的remove，这里是删除指定位置上的元素，注意Integer类型的使用

listIterator是独有的迭代器

ArrayList

ArrayList是基于数组的实现，get和set的性能都很高，但是insert和remove的性能很差，涉及数组元素的移动。

LinkedList

LinkedList在数据的插入和删除上具备很大的优势，在addFirst, addLast, removeFirst, removeLast, getFirst, getLast各个方法的性能很高，但是get(int index)会很慢，因为需要挨个遍历。

性能对比

追加元素都差不多：

插入元素：

求和

如果改用迭代器或增强for，性能无差别。

二者在contains和remove(V value)上没有区别，都是线性复杂度。

ArrayList在使用时，注意扩容问题，如果已知数据量的大小，可以通过ensureCapacity方法设置容量，避免一次次扩容。当全部数据填充完毕后，也可以使用trimToSize去除多余的空间。

remove的使用性能问题

我们来看一个简单的问题，我们删除链表中的偶数。

我们来看第一个实现：

对于ArrayList，get方法是高效的，但是调用remove方法，涉及到数组元素的搬移，性能较差。

对于LinkedList，get方法是低效的，因为需要遍历，同时这里的remove是按索引删除的，因此效率也很低。

基于此，我们使用增强for来解决问题：

这里使用迭代器依次获取元素，没什么区别，性能都是线性的。但是这里我们使用的是Collection的remove方法，依然需要遍历。与此同时，这个代码是无效的，因为增强for使用的迭代器，在Collection进行删除时，会产生异常。

基于此，我们彻底使用迭代器：

这次使用迭代器删除元素，没有上述问题了。对于LinkedList效率很高，删除当前的元素速度很快，但是对于ArrayList，删除元素还是需要移动其他元素的位置的。

ListIterator

ListIterator多出了几个方法：

previous获取前一个元素，用于反向遍历

hasPrevious类比于hasNext

add用于当前位置插入元素

set用于设置新值，替换的是next或者previous刚刚获取到的那个值

这里的add和set方法对LinkedList都是很有好的，性能很高。

自定义MyArrayList的实现

1. 使用数组存储数据，有容量，有当前的存储元素数量

2. 可以扩容，新增一个数组，将元素拷贝过去

3. 提供get和set的实现

4. 提供size，isEmpty，clear，remove，add方法的实现，add可能涉及扩容问题

5. 实现迭代器，提供next，hasNext，remove，iterator方法

public class MyArrayList<AnyType> implements Iterable<AnyType> {// 默认容量10private static final int DEFAULT_CAPACITY = 10;//当前元素数量private int theSize;// 泛型数组用于存储数据private AnyType[] theItems;// 构造器public MyArrayList() { doClear(); }// 清空public void clear() { doClear(); }// 元素数量重置，容量重置private void doClear(){ theSize = 0; ensureCapacity(DEFAULT_CAPACITY); }// 元素数量public int size() { return theSize; }// 是否空的public boolean isEmpty() { return size() == 0; }// 移除无用空间public void trimToSize() { ensureCapacity(size()); }public AnyType get(int idx) {if(idx < 0 || idx >= size())throw new ArrayIndexOutOfBoundsException();return theItems[idx]; }public AnyType set(int idx, AnyType newVal) {if(idx < 0 || idx >= size())throw new ArrayIndexOutOfBoundsException( );AnyType old = theItems[idx];theItems[idx] = newVal; return old;}public void ensureCapacity(int newCapacity) {if(newCapacity < theSize) return;AnyType[] old = theItems; theItems = (AnyType[]) new Object[newCapacity];for(inti=0;i<size();i++)theItems[i] = old[i];}public boolean add(AnyType x) {add(size(), x);return true; }public void add(int idx, AnyType x) {if(theItems.length == size()) ensureCapacity(size()* 2 + 1);for(int i=theSize; i>idx; i--) theItems[i] = theItems[i - 1];theItems[idx] = x;theSize++; }public AnyType remove(int idx) {AnyType removedItem = theItems[idx];for(int i=idx; i<= size()-1;i++)theItems[i] = theItems[i + 1];theSize--;return removedItem; }public java.util.Iterator<AnyType> iterator() { return new ArrayListIterator(); }private class ArrayListIterator implements java.util.Iterator<AnyType> {private int current = 0;public boolean hasNext(){ return current < size(); }public AnyType next() {if(!hasNext())throw new java.util.NoSuchElementException();return theItems[current++]; }public void remove() { MyArrayList.this.remove(--current); }}
}

自定义MyLinkedList的实现

1. 包含两端的指针，链表大小，一些方法。

2. Node节点存储数据、指针

3. 提供迭代器的实现。

public class MyLinkedList<AnyType> implements Iterable<AnyType> {private int theSize;private int modCount = 0;private Node<AnyType> beginMarker;private Node<AnyType> endMarker;public MyLinkedList() {doClear();}public void clear() { doClear();}private void doClear( ){beginMarker = new Node<AnyType>( null, null, null ); endMarker = new Node<AnyType>( null, beginMarker, null ); beginMarker.next = endMarker;theSize = 0; modCount++;}public int size() {return theSize;}public boolean isEmpty() {return size() == 0;}public boolean add(AnyType x) {add(size(), x);return true;}public void add(int idx, AnyType x) {addBefore(getNode(idx, 0, size()), x);}public AnyType get(int idx) {return getNode(idx).data;}public AnyType set(int idx, AnyType newVal) {Node<AnyType> p = getNode(idx);AnyType oldVal = p.data;p.data = newVal;return oldVal;}public AnyType remove(int idx) {return remove(getNode(idx));}private void addBefore(Node<AnyType> p, AnyType x) { Node<AnyType> newNode = new Node<>( x, p.prev, p); newNode.prev.next = newNode;p.prev = newNode;theSize++;modCount++;}private AnyType remove(Node<AnyType> p) { p.next.prev = p.prev;p.prev.next = p.next;theSize--; modCount++;return p.data;}private Node<AnyType> getNode(int idx) { return getNode(idx, 0, size() - 1 );}private Node<AnyType> getNode(int idx, int lower, int upper){Node<AnyType> p;if (idx < lower || idx > upper){throw new IndexOutOfBoundsException();}if (idx < size() / 2){p = beginMarker.next;for (int i = 0; i< idx; i++){p = p.next;}} else {p = endMarker;for (int i = size(); i > idx; i--){p = p.prev;}}return p;}public java.util.Iterator<AnyType> iterator() {return new LinkedListIterator();}// node private static class Node<AnyType> {public AnyType data;public Node<AnyType> prev;public Node<AnyType> next;public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) {data = d;prev = p;next = n;}}private class LinkedListIterator implements java.util.Iterator<AnyType> {private Node<AnyType> current = beginMarker.next; private int expectedModCount = modCount;private boolean okToRemove = false;public boolean hasNext(){ return current != endMarker; }public AnyType next(){if(modCount != expectedModCount)throw new java.util.ConcurrentModificationException(); if(!hasNext())throw new java.util.NoSuchElementException();AnyType nextItem = current.data; current = current.next; okToRemove = true;return nextItem;}public void remove(){if(modCount != expectedModCount)throw new java.util.ConcurrentModificationException();  if(!okToRemove)throw new IllegalStateException();MyLinkedList.this.remove(current.prev); expectedModCount++;okToRemove = false;}}}