第3章 表、栈和队列

使用ArrayList的优点在于，对get和set的调用花费常数时间。其缺点是新项的插入和现有项的删除代价昂贵，除非变动是在ArrayList的末端进行。

使用LinkedList的优点在于，新项的插入和现有项的删除均开销很小，这里假设变动项的位置是已知的。使用LinkedList的缺点是它不容易作索引，因此对get的调用是昂贵的，除非调用非常接近表端点。

MyArrayList

import java.util.Iterator;

public class MyArrayList<AnyType> implements Iterable<AnyType>
{
    public static final int DEFAULT_CAPACITY = 10;

    public int theSize;
    public AnyType[] theItems;

    public MyArrayList()
    { doClear(); }

    public void clear()
    { doClear(); }

    public void doClear()
    { theSize = 0; ensureCapacity(DEFAULT_CAPACITY); }

    public int size()
    { return theSize; }
    public boolean isEmpty()
    { return size() == 0; }
    public void trimTosize()
    { ensureCapacity(size()); }

    public AnyType get(int idx)
    {
        if (idx < 0 || idx >= size())
            throw new ArrayIndexOutOfBoundsException();
        return theItems[idx];
    }

    public AnyType set(int idx, AnyType newVal)
    {
        if(idx < 0 || idx >= size())
            throw new ArrayIndexOutOfBoundsException();
        AnyType old = theItems[idx];
        theItems[idx] = newVal;
        return old;
    }

    public void ensureCapacity(int newCapacity)
    {
        if (newCapacity < theSize)
            return;

        AnyType[] old = theItems;
        theItems = (AnyType [])new Object[newCapacity];
        for (int i = 0; i < size(); i++)
            theItems[i] = old[i];
    }

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

    public void add(int idx, AnyType x)
    {
        if (theItems.length == size())
            ensureCapacity(size() * 2 + 1);
        for (int i = theSize; i > idx; i--)
            theItems[i] = theItems[i - 1];
        theItems[idx] = x;

        theSize++;
    }

    public AnyType remove(int idx)
    {
        AnyType removedItem = theItems[idx];
        for (int i = idx; i < size() - 1; i++)
            theItems[i] = theItems[i + 1];
        theSize--;
        return removedItem;
    }

    public void addAll(Iterable<? extends AnyType>items)
    {
        Iterator<? extends AnyType>iter = items.iterator();
        while (iter.hasNext())
        {
            add(iter.next());
        }
    }

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

    private class ArrayListIterator implements java.util.Iterator<AnyType>
    {
        private int current = 0;

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

        public AnyType next()
        {
            if (!hasNext())
                throw new java.util.NoSuchElementException();
            return theItems[current++];
        }

        public void remove()
        { MyArrayList.this.remove(--current); }
    }
}

MyLinkedList

import java.util.Iterator;

public class MyLinkedList<AnyType> implements Iterable<AnyType>
{
    private static class Node<AnyType>
    {
        public AnyType data;
        public Node<AnyType> prev;
        public Node<AnyType> next;

        public Node(AnyType d, Node<AnyType> p, Node<AnyType> n)
        { data = d; prev = p; next = n; }
    }

    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() - 1), 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 < (lower + upper) / 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;
        }
    }

    public boolean contains(AnyType x)
    {
        Node<AnyType>p = beginMarker.next;
        while (p != endMarker && !(p.data.equals(x)))
        {
            p = p.next;
        }
        return (p != endMarker);
    }

    public void removedAll(Iterable<? extends AnyType>items)
    {
        AnyType item, element;
        Iterator<? extends AnyType>iterItems = items.iterator();

        while (iterItems.hasNext())
        {
            item = iterItems.next();
            Iterator<? extends AnyType>iterList = items.iterator();
            while (iterList.hasNext())
            {
                element = iterList.next();
                if (element.equals(item))
                    iterList.remove();
            }
        }
    }

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

3,4 给定两个已排序的表L1和L2，只使用基本的表操作编写计算L1&L2的过程

    public static <AnyType extends Comparable<? super AnyType>>
    void intersection(List<AnyType>L1, List<AnyType>L2, List<AnyType>Intersect)
    {
        ListIterator<AnyType>iterL1 = L1.listIterator();
        ListIterator<AnyType>iterL2 = L2.listIterator();

        AnyType itemL1 = null, itemL2 = null;

        if (iterL1.hasNext() && iterL2.hasNext())
        {
            itemL1 = iterL1.next();
            itemL2 = iterL2.next();
        }

        while (itemL1 != null && itemL2 != null)
        {
            int compareResult = itemL1.compareTo(itemL2);

            if (compareResult == 0)
            {
                Intersect.add(itemL1);
                itemL1 = iterL1.hasNext() ? iterL1.next() : null;
                itemL2 = iterL2.hasNext() ? iterL2.next() : null;
            }
            else if (compareResult < 0)
            {
                itemL1 = iterL1.hasNext() ? iterL1.next() : null;
            }
            else
                itemL2 = iterL2.hasNext() ? iterL2.next() : null;
        }
    }

3.5 给定两个已排序的表L1和L2，只使用基本的表操作编写计算L1|L2的过程

    public static <AnyType extends Comparable<? super AnyType>>
    void union(List<AnyType>L1, List<AnyType>L2, List<AnyType>Result)
    {
        ListIterator<AnyType>iterL1 = L1.listIterator();
        ListIterator<AnyType>iterL2 = L2.listIterator();
        
        AnyType itemL1 = null, itemL2 = null;
        
        if (iterL1.hasNext() && iterL2.hasNext())
        {
            itemL1 = iterL1.next();
            itemL2 = iterL2.next();
        }
        
        while (itemL1 != null && itemL2 != null)
        {
            int compareResult = itemL1.compareTo(itemL2);
            
            if (compareResult == 0)
            {
                Result.add(itemL1);
                itemL1 = iterL1.hasNext() ? iterL1.next() : null;
                itemL2 = iterL2.hasNext() ? iterL2.next() : null;
            }
            else if (compareResult < 0)
            {
                Result.add(itemL1);
                itemL1 = iterL1.hasNext() ? iterL1.next() : null;
            }
            else {
                Result.add(itemL2);                 
                itemL2 = iterL2.hasNext() ? iterL2.next() : null;
            }
        }
    }

3.6 Josephus问题：N个人编号从1到N，围坐成一个圆圈。从1号开始传递一个热土豆。经过M次传递后拿着热土豆的人被清除离座，围坐的圆圈缩紧，由坐在被清除的人后面的人拿起热土豆继续进行游戏。

    public static void pass(int m, int n)
    {
        int i, j, mPrime, numleft;

        ArrayList<Integer>L = new ArrayList<>();

        for (i = 1; i <= n; i++)
            L.add(i);

        ListIterator<Integer>iter = L.listIterator();
        Integer item = 0;

        numleft = n;
        mPrime = m % n;

        for (i = 0; i < n; i++)
        {
            mPrime = m % numleft;
            if (mPrime < numleft / 2)
            {
                if (iter.hasNext())
                    item = iter.next();
                for (j = 0; j < mPrime; j++)
                {
                    if (!iter.hasNext())
                        iter = L.listIterator();
                    item = iter.next();
                }
            }
            else
            {
                for (j = 0; j < numleft - mPrime; j++)
                {
                    if (!iter.hasPrevious())
                        iter = L.listIterator(L.size());
                    item = iter.previous();
                }
            }
            System.out.print("Removed " + item + " ");
            iter.remove();
            if (!iter.hasNext())
                iter = L.listIterator();

            System.out.println();
            for (Integer x : L)
                System.out.print(x + " ");
            System.out.println();
            numleft--;
        }
        System.out.println();
    }

3.11 假设单链表使用一个头节点实现，但无尾节点，并假设它只保留对该节点的引用

public class SingleList
{
    SingleList()
    { init(); }

    boolean add(Object x){
        if (!contains(x))
            return false;
        else
        {
            Node<Object>p = new Node<>(x);
            p.next = head.next;
            head.next = p;
            theSize++;
        }
        return true;
    }

    boolean remove(Object x)
    {
        if (!contains(x))
            return false;
        else
        {
            Node<Object>p = head.next;
            Node<Object>trailer = head;
            while (!p.data.equals(x))
            {
                trailer = p;
                p = p.next;
            }
            trailer.next = p.next;
            theSize--;
        }
        return true;
    }

    int size()
    { return theSize; }

    void print()
    {
        Node<Object>p = head.next;
        while (p != null)
        {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }

    boolean contains(Object x)
    {
        Node<Object> p = head.next;
        while (p != null)
        {
            if (x.equals(p.data))
                return true;
            else
                p = p.next;
        }
        return false;
    }

    void init()
    {
        theSize = 0;
        head = new Node<Object>();
        head.next = null;
    }

    private Node<Object>head;
    private int theSize;
    private class Node<Object>
    {
        Node()
        {
            this(null, null);
        }
        Node(Object d)
        {
            this(d, null);
        }
        Node(Object d, Node n)
        {
            data = d;
            next = n;
        }
        Object data;
        Node next;
    }
}

3.12 保持单链表以排序的顺序重复练习3.11

public class SingleListSorted
{
    SingleListSorted()
    { init(); }

    boolean add(Comparable x)
    {
        if (!contains(x))
            return false;
        else
        {
            Node<Comparable>p = head.next;
            Node<Comparable>trailer = head;
            while (p != null && p.data.compareTo(x) < 0)
            {
                trailer = p;
                p = p.next;
            }
            trailer.next = new Node<Comparable>(x);
            theSize++;
        }
        return true;
    }

    boolean remove(Comparable x)
    {
        if (!contains(x))
            return false;
        else
        {
            Node<Comparable>p = head.next;
            Node<Comparable>trailer = head;
            while (!p.data.equals(x))
            {
                trailer = p;
                p = p.next;
            }
            trailer.next = p.next;
            theSize--;
        }
        return true;
    }

    int size()
    { return theSize; }

    void print()
    {
        Node<Comparable>p = head.next;
        while (p != null)
        {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }

    boolean contains(Comparable x)
    {
        Node<Comparable>p = head.next;
        while (p != null && p.data.compareTo(x) < 0 )
        {
            if (x.equals(p.data))
                return true;
            else
                p = p.next;
        }
        return false;
    }

    void init()
    {
        theSize = 0;
        head = new Node<Comparable>();
        head.next = null;
    }

    private Node<Comparable>head;
    private int theSize;

    private class Node<Comparable>
    {
        Node()
        {
            this(null, null);
        }
        Node(Comparable d)
        {
            this(d, null);
        }
        Node(Comparable d, Node n)
        {
            data = d;
            next = n;
        }
        Comparable data;
        Node next;
    }
}