几分钟手写一个双向链表

public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

public static void arraycopy(Object src, int srcOfs, Object dest,
      int destOfs, int len) {
    if (src == null || dest == null) {
      throw new NullPointerException();
    }

    Class<?> srcType = src.getClass();
    Class<?> destType = dest.getClass();
    if (!srcType.isArray() || !destType.isArray()) {
      throw new ArrayStoreException("Must be array types");
    }

    Class<?> srcComp = srcType.getComponentType();
    Class<?> destComp = destType.getComponentType();
    if (srcComp.modifiers != destComp.modifiers
        || (srcComp.isPrimitive() && !srcComp.equals(destComp))) {
      throw new ArrayStoreException("Array types must match");
    }
    int srclen = getArrayLength(src);
    int destlen = getArrayLength(dest);
    if (srcOfs < 0 || destOfs < 0 || len < 0 || srcOfs + len > srclen
        || destOfs + len > destlen) {
      throw new IndexOutOfBoundsException();
    }
    /*
     * If the arrays are not references or if they are exactly the same type, we
     * can copy them in native code for speed. Otherwise, we have to copy them
     * in Java so we get appropriate errors.
     */
    if ((!srcComp.isPrimitive() || srcComp.isArray())
        && !srcType.equals(destType)) {
      // copy in Java to make sure we get ArrayStoreExceptions if the values
      // aren't compatible
      Object[] srcArray = (Object[]) src;
      Object[] destArray = (Object[]) dest;
      if (src == dest && srcOfs < destOfs) {
        // TODO(jat): how does backward copies handle failures in the middle?
        // copy backwards to avoid destructive copies
        srcOfs += len;
        for (int destEnd = destOfs + len; destEnd-- > destOfs;) {
          destArray[destEnd] = srcArray[--srcOfs];
        }
      } else {
        for (int destEnd = destOfs + len; destOfs < destEnd;) {
          destArray[destOfs++] = srcArray[srcOfs++];
        }
      }
    } else {
      nativeArraycopy(src, srcOfs, dest, destOfs, len);
    }
  }

public void add(int index, E element) {
	checkPositionIndex(index);
	if (index == size)
		linkLast(element);
	else
		linkBefore(element, node(index));
}
    /**
     * Links e as last element.
     */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

    /**
     * Inserts element e before non-null Node succ.
     */
void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

/**
 * @author LouisShark
 * @mail mshark.louis@gmail.com
 */
public class LouisLinkedList<E> {

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



    public LouisLinkedList() {
    }


    public void add(E e) {
        linkLast(e);
    }


    public void add(int index, E e) {
        checkIndexValid(index);
        if (index == size) {
            linkLast(e);
        } else {
            linkBefore(e, node(index));
        }
    }


    /**
     * 在p之前插入
     */
    void linkBefore(E e, Node<E> p) {
        final Node<E> pred = p.prev;
        final Node<E> newNode = new Node<>(pred, e, p);
        p.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }

    /**
     * 查找的方法
     * @param index
     */
    public E get(int index) {
        checkIndexValid(index);
        return node(index).item;
    }

    /**
     * 删除节点的方法
     * 头尾节点的删除特殊对待
     * @param index
     * @return
     */
    public E remove(int index) {
        checkIndexValid(index);
        Node<E> target = node(index);
        return unlink(target);
    }

    private E unlink(Node<E> p) {
        final E old = p.item;
        /**
         * 记录删除节点的前驱和后继 防止后来的更改带来的破坏
         */
        final Node<E> pre = p.prev;
        final Node<E> next = p.next;
        if (pre == null) {
            //说明是头结点 直接将当前结点的后继赋值给头结点
            first = next;
        } else {
            //将节点的后继赋值给上个节点的后继 断开节点的前驱(设置为null)
            pre.next = next;
            p.prev = null;
        }


        if (next == null) {
            //声明是尾节点 直接将当前结点的前驱赋值给尾节点
            last = pre;
        } else {
            //将节点的前驱赋值给下个节点的前驱 断开节点的后继(设置为null)
            next.prev = pre;
            p.next = null;
        }
        p.item = null;
        size--;

        return old;
    }


    private void checkIndexValid(int index) {
        if (index >= size || index < 0) {
            throw new ArrayIndexOutOfBoundsException("index越界");
        }
    }

    /**
     * Returns the (non-null) Node at the specified element index.
     * 查找索引处节点的方法
     * 这里判断index在前一半还是后一半进行查找的优化(因为链表只能遍历查找，不像顺序表一样可以随机访问)
     */
    private Node<E> node(int index) {
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }
    /**
     * 尾部插入的方法
     * 尾部插入就是吧pre指向last，next指向null
     * 这里要注意是否插入的是第一个节点
     * @param e
     */
    private void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        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;
        }
    }


    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }
}