Data Structure - Doubly Linked List (Java)

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net 

package chimomo.learning.java.datastructure;

/**
 * @author Created by Chimomo
 */
public class DoublyLinkedList<AnyType> implements Iterable<AnyType> {

    private Node<AnyType> head;
    private Node<AnyType> tail;
    private int size;
    private int modificationCount = 0;

    /**
     * Construct an empty DoublyLinkedList.
     */
    public DoublyLinkedList() {
        clear();
    }

    /**
     * Change the size of this collection to zero.
     */
    private void clear() {
        head = new Node<>(null, null, null);
        tail = new Node<>(null, head, null);
        head.next = tail;

        size = 0;
        modificationCount++;
    }

    /**
     * Returns the number of items in this collection.
     *
     * @return The number of items in this collection.
     */
    public int size() {
        return size;
    }

    /**
     * Is doubly linked list empty or not.
     *
     * @return True if empty, false otherwise.
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * Adds an item to this collection, at the end.
     *
     * @param x Any object.
     * @return True.
     */
    public boolean add(AnyType x) {
        add(size(), x);
        return true;
    }

    /**
     * Adds an item to this collection, at specified position.
     * Items at or after that position are slid one position higher.
     *
     * @param x   Any object.
     * @param idx Position to add at.
     * @throws IndexOutOfBoundsException If idx is not between 0 and size(), inclusive.
     */
    public void add(int idx, AnyType x) {
        addBefore(getNode(idx, 0, size()), x);
    }

    /**
     * Adds an item to this collection, at specified position p.
     * Items at or after that position are slid one position higher.
     *
     * @param p Node to add before.
     * @param x Any object.
     * @throws IndexOutOfBoundsException If idx is not between 0 and size(), inclusive.
     */
    private void addBefore(Node<AnyType> p, AnyType x) {
        Node<AnyType> newNode = new Node<>(x, p.prev, p);
        newNode.prev.next = newNode;
        p.prev = newNode;
        size++;
        modificationCount++;
    }

    /**
     * Returns the item at position idx.
     *
     * @param idx The index to search in.
     * @throws IndexOutOfBoundsException If index is out of range.
     */
    public AnyType get(int idx) {
        return getNode(idx).data;
    }

    /**
     * Sets the item at position idx.
     *
     * @param idx    The index to change.
     * @param newVal The new value.
     * @return The old value.
     * @throws IndexOutOfBoundsException If index is out of range.
     */
    public AnyType set(int idx, AnyType newVal) {
        Node<AnyType> p = getNode(idx);
        AnyType oldVal = p.data;

        p.data = newVal;
        return oldVal;
    }

    /**
     * Gets the node at position idx, which must range from 0 to size() - 1.
     *
     * @param idx Index to search at.
     * @return Internal node corresponding to idx.
     * @throws IndexOutOfBoundsException If idx is not between 0 and size() - 1, inclusive.
     */
    private Node<AnyType> getNode(int idx) {
        return getNode(idx, 0, size() - 1);
    }

    /**
     * Gets the node at position idx, which must range from lower to upper.
     *
     * @param idx   Index to search at.
     * @param lower Lowest valid index.
     * @param upper Highest valid index.
     * @return Internal node corresponding to idx.
     * @throws IndexOutOfBoundsException If idx is not between lower and upper, inclusive.
     */
    private Node<AnyType> getNode(int idx, int lower, int upper) {
        Node<AnyType> p;

        if (idx < lower || idx > upper)
            throw new IndexOutOfBoundsException("Get node index: " + idx + "; size: " + size());

        if (idx < size() / 2) {
            p = head.next;
            for (int i = 0; i < idx; i++)
                p = p.next;
        } else {
            p = tail;
            for (int i = size(); i > idx; i--)
                p = p.prev;
        }

        return p;
    }

    /**
     * Removes an item from this collection.
     *
     * @param idx The index of the object.
     * @return The item was removed from the collection.
     */
    public AnyType remove(int idx) {
        return remove(getNode(idx));
    }

    /**
     * Removes the object contained in Node p.
     *
     * @param p The node containing the object.
     * @return The item was removed from the collection.
     */
    private AnyType remove(Node<AnyType> p) {
        p.next.prev = p.prev;
        p.prev.next = p.next;
        size--;
        modificationCount++;

        return p.data;
    }

    /**
     * Returns a string representation of this collection.
     */
    public String toString() {
        StringBuilder sb = new StringBuilder("[ ");

        for (AnyType x : this) {
            sb.append(x).append(" ");
        }
        sb.append("]");

        return new String(sb);
    }

    /**
     * Obtains an iterator object used to traverse the collection.
     *
     * @return An iterator positioned prior to the first element.
     */
    public java.util.Iterator<AnyType> iterator() {
        return new LinkedListIterator();
    }

    /**
     * This is the doubly-linked list node.
     */
    private static class Node<AnyType> {

        private AnyType data;
        private Node<AnyType> prev;
        private Node<AnyType> next;

        Node(AnyType data, Node<AnyType> prev, Node<AnyType> next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }

    }

    /**
     * This is the implementation of the LinkedListIterator.
     * It maintains a notion of a current position and of course the implicit reference to the DoublyLinkedList.
     */
    private class LinkedListIterator implements java.util.Iterator<AnyType> {

        private Node<AnyType> current = head.next;
        private int expectedModificationCount = modificationCount;
        private boolean okToRemove = false;

        public boolean hasNext() {
            return current != tail;
        }

        public AnyType next() {
            if (modificationCount != expectedModificationCount) {
                throw new java.util.ConcurrentModificationException();
            }
            if (!hasNext()) {
                throw new java.util.NoSuchElementException();
            }

            AnyType nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }

        public void remove() {
            if (modificationCount != expectedModificationCount) {
                throw new java.util.ConcurrentModificationException();
            }
            if (!okToRemove) {
                throw new IllegalStateException();
            }

            DoublyLinkedList.this.remove(current.prev);
            expectedModificationCount++;
            okToRemove = false;
        }

    }

    public static void main(String[] args) {
        // Construct a doubly linked list.
        DoublyLinkedList<Integer> lst = new DoublyLinkedList<>();

        // Is empty?
        System.out.println("Is empty? " + lst.isEmpty());

        // Insert.
        for (int i = 0; i < 10; i++) {
            lst.add(i);
        }
        for (int i = 20; i < 30; i++) {
            lst.add(0, i);
        }
        System.out.println("Is empty? " + lst.isEmpty());

        // Remove.
        lst.remove(0);
        lst.remove(lst.size() - 1);
        System.out.println(lst);

        // Iterate.
        java.util.Iterator<Integer> itr = lst.iterator();
        while (itr.hasNext()) {
            itr.next();
            itr.remove();
            System.out.println(lst);
        }
    }

}

/*
Output:
Is empty? true
Is empty? false
[ 28 27 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 27 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 21 20 0 1 2 3 4 5 6 7 8 ]
[ 20 0 1 2 3 4 5 6 7 8 ]
[ 0 1 2 3 4 5 6 7 8 ]
[ 1 2 3 4 5 6 7 8 ]
[ 2 3 4 5 6 7 8 ]
[ 3 4 5 6 7 8 ]
[ 4 5 6 7 8 ]
[ 5 6 7 8 ]
[ 6 7 8 ]
[ 7 8 ]
[ 8 ]
[ ]

*/