线性表

1、顺序表

顺序表

a1是a2的前驱，ai+1 是ai的后继，a1没有前驱，an没有后继
n为线性表的长度 ，若n==0时，线性表为空表
优点：尾部插入数据效率高，支持随机访问(取数据很方便)
缺点：中间插入数据效率低，删除数据效率低
如：ArrayList

2、链式存储

链式存储

单链表

单链表

优点：插入，删除效率都很高
缺点：不支持随机访问，可以循环访问

双链表

双链循环链表
双链表的插入

1、s.prior = p; // step1
2、p.pre.next = s; //step2
3、s.next = p; //step3
4、p.pre = s; //step4

双链表的删除

1、p.prior.next = p.next;
2、p.next.prior = p.prior；
双链表：如 LinkedList
双链表的增删改查：

public class LinkedList<E> {
    Node<E> first;
    Node<E> last;
    int size;

    public LinkedList() {

    }

    /**
     * 队尾添加一个元素
     */
    public void add(E e) {
        linkLast(e);
    }

    /**
     * 在index的位置添加一个元素
     * @param index
     * @param e
     */
    public void add(int index,E e){
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
        if (index==size){
            linkLast(e);
        }else {
            Node<E> target = node(index);
            Node<E> prev = target.prev;
            Node<E> newNode = new Node<>(prev,e,target);
            target.prev = newNode;
            if (prev == null){
                first = newNode;
            }else {
                prev.next = newNode;
            }
            size++;
        }
    }

    public E get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
        return node(index).item;
    }

    /**
     * 删除一个元素
     * @param index
     */
    public void remove(int index){
        Node<E> target = node(index);
        unLinked(target);
    }
    private void unLinked(Node<E> p){
//        p.prev.next = p.next;
//        p.next.prev = p.prev;
        Node<E> prev = p.prev;
        Node<E> next = p.next;
        if (prev == null){
            //等价于删除第一个节点
            first = next;
        }else {
            prev.next = p.next;
            p.prev = null;
        }
        if (next ==null){
            //等价于删除最后一个元素
            last = prev;

        }else {
            next.prev = p.prev;
            p.next = null;
        }
        size--;
    }

    private Node<E> node(int index){
        //index处于链表的前半部分
        if (index<(size>>1)){
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        }else {
            //index处于链表的后半部分
            Node<E> node = last;
            for (int i= size-1;i>index;i--){
                node = node.prev;
            }
            return node;
        }
    }

    private void linkLast(E e) {
        Node<E> newNode = new Node<E>(last, e, null);
        Node<E> l = last;
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    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;
        }
    }

    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }
}