LinkedList双向链表的实现

 每个节点有由三个组成

private static final class Link<ET> {

        ET data;

        Link<ET> previous, next;

        Link(ET o, Link<ET> p, Link<ET> n) {

            data = o;

            previous = p;

            next = n;

        }

    }

 

  public boolean add(E object) {

         Link<E> oldLast = voidLink.previous;//获得最后一个节点

        Link<E> newLink = new Link<E>(object, oldLast, voidLink);// 生成一个新的节点

        voidLink.previous = newLink;

        oldLast.next = newLink;

        size++;

        modCount++;

        return true;

    }

 

  public void addFirst(E object) {

        Link<E> oldFirst = voidLink.next;//获得第一个节点

        Link<E> newLink = new Link<E>(object, voidLink, oldFirst);

        voidLink.next = newLink;

        oldFirst.previous = newLink;

        size++;

        modCount++;

    }

 

  public void add(int location, E object) {

        if (0 <= location && location <= size) {

            Link<E> link = voidLink;

            if (location < (size / 2)) {

                for (int i = 0; i <= location; i++) {

                    link = link.next;

                }

            } else {

                for (int i = size; i > location; i--) {

                    link = link.previous;

                }

            }

            Link<E> previous = link.previous;

            Link<E> newLink = new Link<E>(object, previous, link);

            previous.next = newLink;

            link.previous = newLink;

            size++;

            modCount++;

        } else {

            throw new IndexOutOfBoundsException();

        }

    }

 

/**     * Constructs a new empty instance of {
    @code LinkedList}.     */    public LinkedList() {        voidLink = new Link
     
      (null, null, null);        voidLink.previous = voidLink;        voidLink.next = voidLink;    }