集合--LinkedList

[TOC]

Linkedlist

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