1.表的数组实现

前驱元：表中的元素的前一个元素称为该元素的前驱元，第一个元素不定义前驱元。
后继元：表中的元素的后一个元素称为该元素的后继元，最后一个元素不定义后继元。
数组是一种大小固定的数据结构，对线性表的操作可以通过数组实现；虽然数组容量固定，但是可以通过创建一个容量更大的数组来替换当前数组，即数组的扩容（ArrayList类的底层实现就是通过数组扩容）。新建整型数组默认元素为0，字符型为null;

public class Array {
    public static void main(String[] args) {
        int arr [] = new int[3];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println(" ");
        //数组的扩容
        int Bigarr[] = new int [6];
        for (int i = 0; i < arr.length; i++) {
            Bigarr[i] = arr[i];
        }
        for (int i = 0; i < Bigarr.length; i++) {
            System.out.print(Bigarr[i]+" ");
        }
        String s[]=new String[3];
        System.out.println(s[1]);
    }
}

数组属于顺序存储结构，便于查找，但是插入和删除的开销大，复杂度为O(N);

2.链表

链表由一系列节点组成，每一个节点含有表元素和到该元素后继元的节点的链(link)，可以理解为后继元地址或后继元的引用。这些节点在内存中不一定相连，最后一个单元的next链引用null;

单向链表.png
双向链表.png

3.表在Java中的实现

3.1java中的容器

容器接口关系.png

要点1：Collection接口继承Iterable接口，实现Iterable接口的类需要实现forEach()方法，因此这些类可以拥有增强的for循环，即foreach语句，可遍历容器;

要点2：实现Iterable接口必须实现iterator()方法，该方法返回一个iterator对象，该对象实现iterator接口，该接口中定义了hasnext(),next()和remove()方法。可遍历容器。

要点3：普通for 循环，增强for循环和迭代器遍历容器的比较
普通for循环需要知道容器的内部结构，访问代码和集合本身是高度耦合的，无法将访问逻辑从集合类和客户端代码中分离出来。不同的集合会对应不同的遍历方法，客户端代码无法复用。
Iterator用同一种逻辑来遍历集合。使得客户端自身不需要来维护集合的内部结构，所有的内部状态都由Iterator来维护。
foreach依赖于Iterable接口返回的iterator对象，本质上，foreach就是在使用iterator。foreach代码简洁，但是不能获取下标。
注意：在使用iterator时，不能对正在被迭代的集合进行结构上的改变（即对该集合使用add,remove或clear方法），否则会出现ConcurrentModificationException异常。但是使用iterator自己的remove方法，该迭代器仍是合法的。
原因：迭代之前，迭代器已经被通过list.itertor()创建出来了，如果在迭代的过程中，又对list进行了改变其容器大小的操作，那么Java就会给出异常。因为此时Iterator对象已经无法主动同步list做出的改变，Java会认为你做出这样的操作是线程不安全的，就会给出善意的提醒（抛出ConcurrentModificationException异常）。
通过查看源码发现原来检查并抛出异常的是checkForComodification()方法。在ArrayList中modCount是当前集合的版本号，每次修改(增、删)集合都会加1；expectedModCount是当前迭代器的版本号，在迭代器实例化时初始化为modCount。我们看到在checkForComodification()方法中就是在验证modCount的值和expectedModCount的值是否相等，所以当你在调用了ArrayList.add()或者ArrayList.remove()时，只更新了modCount的状态，而迭代器中的expectedModCount未同步，因此才会导致再次调用Iterator.next()方法时抛出异常。但是为什么使用Iterator.remove()就没有问题呢？通过源码发现，在Iterator的remove()中同步了expectedModCount的值，所以当你下次再调用next()的时候，检查不会抛出异常。

要点4：List接口的两个实现类的比较(从时间复杂度角度)：
ArrayList:可增长数组的实现
get,set花费常数时间
在前端添加花费O(N),在后端添加花费常数时间（忽略偶尔的扩展）
remove的使用，不管利用普通遍历还是迭代器都是O(N的平方)
LinkedList:双链表的实现
插入和删除的开销小，均是常数时间的操作；addFirst,addLast,removeFirst,removeLast,getFirst,getLast，add
get,set花费O(N)
remove的使用，利用迭代器会使得整个程序花费线性时间O(N)，普通循环却是O(N的平方)

要点5：ListIterator接口
ListIterator接口是对iterator接口的一个增强，但是仅适用List接口及其实现类，不适用Set，Map等集合。
ListIterator增加了previous和hasPrevious方法，能够实现逆向遍历（从后向前）
ListIterator增加了add方法，向当前集合插入元素，插入位置为当前迭代位置
ListIterator增加了set方法，更改迭代器看到的最后一个值
ListIterator增加了nextIndex和previousIndex，返回下（前）一元素的索引值

3.2ArrayList类的实现

保持基础数组，数组容量，当前元素数量；
可自动扩容；
get和set方法的实现；
add和remove方法的实现；

public class MyArrayList {
    private Object [] elementData;//基础数组，集合中所有元素均放在此数组中
    private int size;//集合所含元素个数
    private static final int DEFAULT_CAPACITY = 10;//数组容量，初始为10
    //无参构造，调用有参构造
    public MyArrayList() {
        this(DEFAULT_CAPACITY);
    }
    public MyArrayList(int initialCapacity) {
        if(initialCapacity > 0) {
            this.elementData = new Object[initialCapacity]; 
        }else {
            try {
                throw new Exception();
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
    }
    //返回集合中当前元素个数
    public int size() {
        return size;
    }
    public void ensureCapacity(int newCapacity) {
        if(newCapacity < size) {
            return;
        }
        Object [] old = elementData;
        elementData = new Object[newCapacity];
        for (int i = 0; i < size(); i++) {
            elementData[i] = old[i];
        }
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public void checkIndex(int index) {
        if(index < 0 || index >=size) {
            try {
                throw new Exception();
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
    }
    public void checkIndexforAdd(int index) {
        if(index < 0 || index >size) {
            try {
                throw new Exception();
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
    }
    public Object get(int index) {
        checkIndex(index);
        return elementData[index];
    }
    public Object set(int index,Object o) {
        checkIndex(index);
        Object old = elementData[index];
        elementData[index] = o;
        return old;
    }
    public void add(Object o) {
        //判断size是否超过数组长度
        if(size == elementData.length) {
            ensureCapacity(size*2+1);
        }
        elementData[size++] = o;
        
    }
    public void add(int index,Object o) {
        checkIndexforAdd(index);
        if(size == elementData.length) {
            ensureCapacity(size*2+1);
        }
        for (int i = index; i<size;i++) {
            elementData[i+1] = elementData[i];
        }
        elementData[index] = o;
        size++;
    }
    public void remove(int index) {
        checkIndex(index);
        for(int i = index;i <size-1;i++ ) {
            elementData[i] = elementData[i+1];
        }
        elementData[size-1] = null;
        size--;
    }

3.3LinkedList类的实现（双向链表）

1.存储数据的节点类Node的编写，采用嵌套类（静态内部类）的方式
2.头节点和尾节点，集合元素个数，集合版本号
3.常用方法的编写，add，remove，node等
4.迭代器的实现，LinkedListIterator内部类

package Day02;
import java.util.Iterator;
import java.util.List;
public class MyLinkedList<T> implements Iterable<T>{
    //通过节点存储数据，通过静态内部类定义节点，也可以在外部定义
    private static class Node<T>{
        private Node<T> prev;
        private Node<T> next;
        private T t;
        public Node(Node<T> prev, Node<T> next, T t) {
            super();
            this.prev = prev;
            this.next = next;
            this.t = t;
        }   
    }
    private Node<T> begin;//头节点
    private Node<T> end;//尾节点
    private int size;//当前集合中元素个数
    private int modCount;//版本，添加删除会+1
    public MyLinkedList() {
        doClear();
    }

    private void doClear() {
        begin = new Node<T>(null, null, null);
        end = new Node<T>(begin, null, null);
        begin.next = end;
        size = 0;
        modCount++;
    }
    //当前集合中元素个数
    public int size() {
        return size;
    }
    //判断是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    public void addBefore(Node<T> p,T t) {
        Node<T> newNode = new Node<>(p.prev, p, t);
        newNode.prev.next = newNode;
        p.prev = newNode;
        size++;
        modCount++;
    }
    public boolean addBefore(int index,T t) {
        Node<T> temp = node(index);
        addBefore(temp, t);
        return true;
    }
    public void addAfter(Node<T> p,T t) {
        Node<T> newNode = new Node<>(p, p.next, t);
        newNode.next.prev = newNode;
        p.next = newNode;
        size++;
        modCount++;
    }
    public boolean addAfter(int index,T t) {
        Node<T> temp = node(index);
        addAfter(temp, t);
        return true;
    }
    public void addFirst(T t) {
        Node<T> newNode = new Node<T>(begin, begin.prev, t);
        begin.next = newNode;
        newNode.next.prev = newNode;
        size++;
        modCount++;
    }
    public void addLast(T t) {
        Node<T> newNode = new Node<T>(end.prev, end, t);
        end.prev = newNode;
        newNode.prev.next = newNode;
        size++;
        modCount++;
    }
    public void add(T t) {
        addLast(t);
    }
    public void indexCheck(int index) {
            if(index < 0 || index >= size) {
                try {
                    throw new Exception();
                } catch (Exception e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
    }
    public Node<T> node(int index) {
        
        
        if(index < (size >> 1)) {
            Node temp = begin;
            for(int i = 0; i <= index; i++) {
                temp = temp.next;
            }
            return temp;
        }else {
            Node temp = end;
            for(int i = size-1; i >= index; i--) {
                temp = temp.prev;
            }
            return temp;
        }       
    }
    public T get(int index) {
        indexCheck(index);
        return node(index).t;
    }
    public T getFirst() {
        if(begin.next == end) {
            try {
                throw new Exception();
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        return begin.next.t;
    }
    public T getLast() {
        if(end.prev == begin) {
            try {
                throw new Exception();
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        return end.prev.t;
    }
    public T set(int index,T t) {
        indexCheck(index);
        Node<T> temp = node(index);
        T old = temp.t;
        temp.t = t;
        return old;
    }
    public boolean remove(T t) {
        for(Node<T> temp = begin; temp.next != end; temp = temp.next) {
            if(t.equals(temp.t)) {
                temp.prev.next = temp.next;
                temp.next.prev = temp.prev;
                size--;
                modCount++;
                return true;
            }
        }
        return false;
    }
    public boolean remove(int index) {
        indexCheck(index);
        Node<T> temp = node(index);
        temp.prev.next = temp.next;
        temp.next.prev = temp.prev;
        size--;
        modCount++;
        return true;
    }
    @Override
    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }
    //迭代器
    private class LinkedListIterator implements Iterator<T>{
        private Node<T> current = begin.next;
        private int expectedModCount = modCount;
        private boolean okToRemove = false;
        @Override
        public boolean hasNext() {
            return current != end;
        }
        @Override
        public T next() {
            if(modCount != expectedModCount) {
                try {
                    throw new Exception();
                } catch (Exception e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            if(! hasNext()) {
                try {
                    throw new Exception();
                } catch (Exception e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            T data = current.t;
            current = current.next;
            okToRemove = true;
            return data;
        }
        public void remove() {
            if(modCount != expectedModCount) {
                try {
                    throw new Exception();
                } catch (Exception e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            if(! okToRemove) {
                try {
                    throw new Exception();
                } catch (Exception e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            MyLinkedList.this.remove(current.prev.t);
            expectedModCount++;
            okToRemove = false;
        }
    }