[TOC]

Linkedlist

image
image

继承类：AbstractSequentialList<E>
实现接口：List<E>, Deque<E>
主要函数实现原理：

Add:

    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++;
    }
    
    /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

添加结点的函数主要分为三个：在链表头插入结点，在链表尾部插入节点，在一个非空元素前插入节点。 共同的操作有size++，还有就是与ArrayList相似的modcount++记录表结构修改的次数。
在链表头插入结点：新建一个node，如果第一个节点为空，则直接将新建的节点赋值给最后一个节点last，否则修改第一个节点的前节点为新节点。
在链表尾插入节点：同上，不通的只是将最后一个节点的后置节点设置为新创建的节点。
在一个非空元素前插入节点：在succ节点前面插入一个新节点，首先获得succ的前置结点pred，首先将succ的前置节点修改为新建的节点，然后判断pred是否为空，如果为空则将新节点设置为表头，非空则将pred的后置节点修改为新创建的节点。

Remove

/**
     * Removes the element at the specified position in this list.  Shifts any
     * subsequent elements to the left (subtracts one from their indices).
     * Returns the element that was removed from the list.
     *
     * @param index the index of the element to be removed
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }
    
    /**
     * Unlinks non-null node x.
     */
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

其实从名字可以看出来这个函数的功能是将一个非空的节点在删除，主要流程就是，获取要删除的节点x的前置节点prev，后置节点next,如果prev或者next为空，则修改first或者last，如果为非空，则修改pre的下个节点为next，next的上一个节点为prev，并且将x脱离链表，即将x.prev和x.next都置位空。

node

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

节点的定义

Deque

这个接口含有双向队列与栈的特性，其实现的函数也是实现双向队列与栈相关的功能。

ListItr

image

private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        public E previous() {
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();

            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }

        public int nextIndex() {
            return nextIndex;
        }

        public int previousIndex() {
            return nextIndex - 1;
        }

        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (modCount == expectedModCount && nextIndex < size) {
                action.accept(next.item);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

理解：
　　遍历类ListItr，是Linkedlist实现的内部类，属性lastReturned表示next()函数返回的节点，next表示当前返回的节点的下一个节点，构造函数会先设置好next节点的值，remove（）函数也是删除lastReturned节点。next()函数返回的是next的前一个节点。理解了这两个属性的含义其实就很好理解这几个遍历相关的函数了。　　
　　这里有一个问题，就是remove()函数为什么会出现next == lastReturned的情况，或许是为了保证函数的健壮性。