定义

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。

特点

• 不需要连续的内存空间。
• 有指针引用
• 三种最常见的链表结构：单链表、双向链表和循环链表

图形

从单链表图中，可以发现，有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们一般把第一个结点叫作头结点，把最后一个结点叫作尾结点。
其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。

• 双向链表：双向链表有两个指针域，一个指向性上一个节点，一个指向下一个节点，头节点的上一个节点为NULL
• 循环链表：循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。环链表的尾结点指针是指向链表的头结点。

数组和链表的区别

1. 数组结构使用的是连续的内存空间，可以借助cpu缓存的机制，预读数组中的数据
2. 链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法有效预读。
3. 数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。
4. 动态扩容：数组需再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容。
5. 时间复杂度：数组的访问为O(1),修改为O(n);链表的访问为O(n),修改为O(1)

这里也不是绝对的，如果数组和链表都是在尾部或者头部进行操作，那数组和链表的访问和修改都是O(1)，如栈和队列

手写一个LinkedList

public class MyLinkedList<E> implements MyList<E> {

    private int size;
    private Node<E> first;
    private Node<E> last;

    @Override
    public int size() {
        return size;
    }

    @Override
    public void add(E e) {
        Node<E> newNode = new Node<>(null, e, null);
        if (first == null) {
            first = newNode;
            last = newNode;
            size++;
            return;
        }
        last.next = newNode;
        newNode.pre = last;
        last = newNode;
        size++;
    }

    @Override
    public void add(E e, int index) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException();
        Node<E> newNode = new Node<>(null, e, null);
        if (index == size) {//加在末尾
            add(e);
            return;
        }
        Node<E> cur = node(index);
        newNode.next = cur;
        if (cur.pre == null) {//头
            cur.pre = newNode;
            first = newNode;
        } else {
            newNode.pre = cur.pre;
            cur.pre.next = newNode;
            cur.pre = newNode;
        }
        size++;
    }

    @Override
    public void remove(int index) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException();
        if (index == size) {
            last.pre.next = null;
            last = last.pre;
            size--;
            return;
        }
        Node<E> cur = node(index);
        if (cur.pre == null) {
            cur.next.pre = null;
            first = cur.next;
        } else {
            cur.pre.next = cur.next;
            cur.next.pre = cur.pre;
        }
        size--;
    }

    private Node<E> node(int index){
        Node<E> cur = null;
        if (index < (size >> 1)) {//插入位置小于链表的一半
            //从前遍历
            cur = first;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }//index=3 插入在第四个位置 cur为第4个链表元素

        } else {
            //从后遍历
            cur = last;
            for (int i = size - 1; i > index; i--) {
                cur = cur.pre;
            }//index=3 插入在第四个位置 cur为第4个链表元素 size =5 last.index=4
        }
        return cur;
    }
    @Override
    public void remove(E e) {
        remove(indexOf(e));
    }

    @SuppressWarnings("unchecked")
    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public Iterator<E> iterator() {
        return null;
    }

    @Override
    public int indexOf(E e) {
        Node<E> cur = first;
        for (int i = 0 ;i<size;i++){
            if(e.equals(cur.element)){
                return i;
            }
            cur = cur.next;
        }
        return -1;
    }

    private class Node<E> {
        private E element;
        private Node<E> pre;
        private Node<E> next;

        public Node(Node<E> pre, E element, Node<E> next) {
            this.pre = pre;
            this.element = element;
            this.next = next;
        }
    }