LinkedList

• 介绍
  内部是个双向循环链表来实现的

transient int size = 0; 
transient Link<E> voidLink;      头结点
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;
    }
}

增： 插入结点

@Override
public void add(int location, E object) {
    if (location >= 0 && 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();
    }
}

批量增加

@Override
public boolean addAll(int location, Collection<? extends E> collection) {
    if (location < 0 || location > size) {
        throw new IndexOutOfBoundsException();
    }
    int adding = collection.size();
    if (adding == 0) {
        return false;
    }
    Collection<? extends E> elements = (collection == this) ?
            new ArrayList<E>(collection) : collection;

    Link<E> previous = voidLink;
    if (location < (size / 2)) {
        for (int i = 0; i < location; i++) {
            previous = previous.next;
        }
    } else {
        for (int i = size; i >= location; i--) {
            previous = previous.previous;
        }
    }
    Link<E> next = previous.next;
    for (E e : elements) {
        Link<E> newLink = new Link<E>(e, previous, null);
        previous.next = newLink;
        previous = newLink;
    }
    previous.next = next;
    next.previous = previous;
    size += adding;
    modCount++;
    return true;
}

删：

@Override
public E remove(int location) {
    if (location >= 0 && 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> next = link.next;
        previous.next = next;
        next.previous = previous;
        size--;
        modCount++;
        return link.data;
    }
    throw new IndexOutOfBoundsException();
}

查：

@Override
public E get(int location) {
    if (location >= 0 && 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;
            }
        }
        return link.data;
    }
    throw new IndexOutOfBoundsException();
}

改：

@Override
public E set(int location, E object) {
    if (location >= 0 && 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;
            }
        }
        E result = link.data;
        link.data = object;
        return result;
    }
    throw new IndexOutOfBoundsException();
}