List接口、ArrayList类和LinkedList类
1.List
List接口继承自Collection接口，其中常用的较为重要的方法如下：
public interface List<AnyType> extends Collection<AnyType>{
int size();
boolean add(E e);
boolean remove(Object o);
E get(int index);
E set(int index, E element);
}get和set使得用户可以访问或改变通过由位置索引index给定的表中指定位置上的项。索引0位于表的前端，索引size()-1代表表中的最后一项。
List有两种流行的实现方式，ArrayList和LinkedList。
ArrayList、LinkedList
ArrayList类提供了List的一种可增长数组的实现.使用ArrayList的优点在于，对get和set的调用花费常数时间。其缺点是新项的插入和现有项的删除代价昂贵，除非变动是在ArrayList的末端进行。
LinkedList则提供了List的双向链表实现。使用LinkedList的优点在于，新项的插入和现有项的删除均开销很小，这意味着在表的前端进行添加和删除都是常数时间的操作，由此LinkedList更提供了方法addFirst和removeFirst、addLast和removeLast等方法可以有效的添加、删除和访问表两端的项。使用LInkedList的缺点是它不容易作索引，因此对get的调用是昂贵的，除非调用非常接近表的端点。
首先，我们在表的末端添加一项来构造list：
public static void makeList1(List<Integer> lst, int N) {
lst.clear();
for (int i = 0; i < N; i++) {
lst.add(i);
}
}不管ArrayList还是LinkedListlist作为参数进行传递，makeList1的运行时间都是o(N)，因此对add的每次调用都是在表的末端进行从而花费常数时间。
如果我们从表的前端构造一个List：
public static void makeList2(List<Integer> lst, int N) {
lst.clear();
for (int i = 0; i < N; i++) {
lst.add(0, i);
}
}那么，对于LinkedList它的运行时间是O(N)，但是对于ArrayList其运行时间则是O(N2)，因为在ArrayList中，在前端进行添加是一个O(N)操作。
下一个例子是极端List中的数的和：
public static int makeList3(List<Integer> lst, int N) {
int total = 0;
for (int i = 0; i < N; i++) {
total += lst.get(i);
}
return total;
}这里ArrayList的运行时间是O(N)，但是对于LinkedList来说，其运行时间则是O(N2)，因为在LinkedList中，对get的调用为O(N)操作。
如果使用一个增强的for循环，那么它对任意List的运行时间都是O(N)，因为迭代器将有效地从一项到下一项推进。
将list表中所有偶数值删除：
因为ArrayList删除效率地下，所以在涉及需要进行删除操作时，我们应该构建LinkedList表。但是在LinkedList中，由于对get调用的效率不高，因此也会花费较多时间，所以remove的效率同样低下，代码如下：
public static void removeEvenVer1(List<Integer> lst){
int i = 0;
while (i<lst.size()){
if(lst.get(i)%2==0){
lst.remove(i);
}else {
i++;
}
}
}如果我们不使用get()方法去获取数据，而是使用迭代器，会不会变得高效一点呢
public static void removeEvenVer2(List<Integer> lst){
for (Integer x:lst){
if(x%2==0){
lst.remove(x);
}
}
}但是我们运行这个程序，会产生一个异常，因为当一项被删除时，由增强的for循环所使用的基础迭代器是非法的。
迭代器使用：
在迭代器找到一个偶数值项之后，我们可以使用该迭代器来删除这个它刚看到的值。对于一个LinkedList，对该迭代器的remove方法的调用只花费常数时间，因为该迭代器位于被删除的节点。因此，对于LinkedList，整个程序花费线性时间，而不是二次时间。对于ArrayList，因为数组的删除伴随着数组项的移动，所以花费的还是二次时间。
public static void removeEvensVer3(List<Integer> lst){
Iterator<Integer> itr = lst.iterator();
while (itr.hasNext()){
if(itr.next()%2 == 0){
itr.remove();
}
}
}ArrayList类的实现
package collections.list;
import java.util.Iterator;
import java.util.function.Consumer;
/** * Created with IntelliJ IDEA. * * @Author crazyang * @Desciption: * @Date 2018-6-8 17:04 */
public class MyArrayList<AnyType> implements Iterator<AnyType> {
private static final int DEFAULT_CAPACITY = 10;
private int theSize;
private AnyType[] theItems;
public MyArrayList(){
doClear();
}
public void clear(){
doClear();
}
public 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 index){
if(index<0||index>=size()){
throw new ArrayIndexOutOfBoundsException();
}
return theItems[index];
}
public AnyType set(int index,AnyType newVal){
if(index<0||index>=size()){
throw new ArrayIndexOutOfBoundsException();
}
AnyType old = theItems[index];
theItems[index] = newVal;
return old;
}
public void ensureCapacity(int newCapacity){
if(newCapacity<theSize){
return;
}
AnyType [] old = theItems;
theItems=(AnyType[])new Object[newCapacity];
for(int i =0;i<size();i++){
theItems[i] = old[i];
}
}
public boolean add(AnyType x){
add(size(),x);
return true;
}
public void add(int index,AnyType x){
if(theItems.length == size()){
ensureCapacity(size()*2+1);
}
for(int i = theSize;i>index;i--){
theItems[i] = theItems[i-1];
}
theItems[index] = x;
theSize++;
}
public AnyType remove(int index){
AnyType removeItem = theItems[index];
for(int i = index;i<size()-1;i++){
theItems[i] = theItems[i+1];
}
theSize--;
return removeItem;
}
private int current=0;
@Override
public boolean hasNext() {
return current<size();
}
@Override
public AnyType next() {
if(!hasNext()){
throw new java.util.NoSuchElementException();
}
return theItems[current++];
}
@Override
public void remove() {
MyArrayList.this.remove(--current);
}
}
LinkedList类的实现
LinkedList将作为双向链表来实现，而且我们还需要保持该表两端的引用。
设计：
1、MyLinkedList类本身，它包含到两端的链、表的大小以及一些方法。
2、Node类，它可能是一个私有的嵌套类。一个节点包含数据以及到前一个节点的链和到下一个节点的链，还有一些适当的构造方法。
3、LinkedListIterator类，该类抽象了位置的概念，是一个私有类，并实现接口Iterator。它提供了next、hasNext和remove的实现。
package collections.list;
import java.util.Iterator;
/** * Created with IntelliJ IDEA. * * @Author crazyang * @Desciption: * @Date 2018-6-8 17:29 */
public class MyLinkedList<AnyType> implements Iterable<AnyType> {
private int theSize;
private int modCount = 0;
private Node<AnyType> beginMarker;
private Node<AnyType> endMarker;
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;
}
}
public int size() {
return theSize;
}
public boolean add(AnyType x) {
add(size(), x);
return true;
}
public void add(int index, AnyType x) {
addBefore(getNode(index, 0, size()), x);
}
public void addBefore(Node<AnyType> p, AnyType x) {
Node newNode = new Node<>(x, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
modCount++;
}
public Node<AnyType> getNode(int index) {
return null;
}
public Node<AnyType> getNode(int index, int lower, int upper) {
return null;
}
@Override
public Iterator<AnyType> iterator() {
return null;
}
}