LinkedList实现

本节，我们提供一种LinkedList泛型类的实现，命名为MyLinkedList。我们计划实现一个双链表，因此我们需要获得头和尾的索引，考虑到这个设计我们需要三个类

1. MyLinkedList类本身，包括头尾以及各种方法
2. Node类，作为一个私有嵌套类。它包括数据和关联他的前置和后置的指针。
3. LinkedListIterator类，作为私有内部类实现Iterator接口，提供next、hasNext、remove方法

Iterator类存储了当前节点的索引，由于终端标记是一个无效的位置，因此需要在末尾创建一个额外的节点来表示终端标记。同时我们也可以创建一个头节点来表示头处标记。它们也常被称为“哨兵节点”，也称为头节点和尾节点。

/**
 * Copyright (C), 2015-2019, XXX有限公司
 * FileName: MyLinkedList
 * Author:   dalu
 * Date:     2019/7/16 22:45
 * Description:
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */

import org.omg.CORBA.Any;

/**
 * 〈一句话功能简述〉<br> 
 * 〈〉
 *
 * @author dalu
 * @create 2019/7/16
 * @since 1.0.0
 */
public class MyLinkedList <AnyType> implements  Iterable<AnyType> {
    private static class Node<AnyType> {
        public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) {
            data = d;
            prev = p;
            next = n;
        }
        
        public AnyType data;
        public Node<AnyType> prev;
        public Node<AnyType> next;

    }

    public MyLinkedList() {
        doClear();
    }

    public void clear(){
        doClear();
    }
    
    public void doClear() {
        beginMarker = new Node<AnyType>(null, null, null);
        endMarker = new Node<AnyType>(null, beginMarker, null);
        beginMarker.next = endMarker;
        
        theSize = 0;
        modCount++;
    }

    public int size() {
        return theSize;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public boolean add(AnyType x) {
        add(size(), x);
        return true;
    }

    public void add(int idx, AnyType x) {
        addBefore(getNode(idx, 0, size()), x);
    }

    public AnyType get(int idx) {
        return getNode(idx).data;
    }

    public AnyType set(int idx, AnyType newVal) {
        Node<AnyType> p = getNode(idx);
        AnyType oldVal = p.data;
        p.data = newVal;
        return oldVal;
    }

    public AnyType remove(int idx) {
        return remove(getNode(idx));
    }

    private void addBefore(Node<AnyType> p, AnyType x) {
        Node<AnyType> newNode = new Node<>(x, p.prev, p);
        newNode.prev.next = newNode;
        p.prev = newNode;
        theSize++;
        modCount++;

    }

    private AnyType remove(Node<AnyType> p) {
        p.next.prev = p.prev;
        p.prev.next = p.next;
        theSize--;
        modCount++;
        
        return p.data;

    }

    private Node<AnyType> getNode(int idx) {
        return getNode(idx, 0, size() - 1);

    }

    private Node<AnyType> getNode(int idx, int lower, int upper) {
        Node<AnyType> p;
        
        if(idx <lower || idx > upper) {
            throw new IndexOutOfBoundsException();
        }
        
        if (idx < size() / 2) {
            p = beginMarker.next;
            for (int i = 0; i < idx; i++) {
                p = p.next;
            }
        }
        else {
            p = endMarker;
            for (int i = size(); i > idx; i--) {
                p = p.prev;
            }
        }
        
        return p;

    }

    public java.util.Iterator<AnyType> iterator() {
        return new LinkedListIterator();
    }

    private class LinkedListIterator implements  java.util.Iterator<AnyType> {
        private Node<AnyType> current = beginMarker.next;
        private int expectedModCount = modCount;
        private boolean okToRemove = false;
        
        public  boolean hasNext() {
            return current != endMarker;
        }
        
        public AnyType next() {
            if(modCount != expectedModCount) {
                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(modCount != expectedModCount) {
                throw new java.util.ConcurrentModificationException();
            }
            if(!okToRemove) {
                throw new IllegalStateException();
            }
            
            MyLinkedList.this.remove(current.prev);
            expectedModCount++;
            okToRemove = false;
        }
        

    }

    private int theSize;
    private int modCount = 0;
    private Node<AnyType> beginMarker;
    private Node<AnyType> endMarker;
}

Stack

栈是一个限制插入和删除操作在特定位置的链表。insert类似于push，delete类似于pop，操作都是在链表的末端即栈的顶部。栈也通常被称为LIFO链表（后进，先出）。对于LinkedList，我们只需要实现其在头部的插入和删除即可。而更为流行的方法则是使用ArrayLinkedList维护一个topOfStack索引，当push时增加topOfStack，set相应的值；当pop时，返回当前theArray[topOfStack]并topOfStack减一。

Queue

队列也是一种链表，常规操作主要有入队和出队。类似于栈，任何一种链表都是可以实现队列的，同时都可以在O(1)时间内完成操作。以ArrayList为例，我们有一个数组theArray，两个位置front和back，同时跟踪队列的元素数量currentSize。进队则是theArray[back] = x,出队则是返回theArray[front]。当然为了防止空间的浪费，我们可以使用循环队列来解决。