数据结构与算法

本文的主要内容是对《数据结构与算法分析》(Java语言描述)的学习过程记录。由于第一章和第二章主要讲解了一些数学基础和java基础，所以主要从第三章开始。

第三章 表、栈和队列

3.1 抽象类型

抽象数据类型（abstract data type ，ADT）是带有一组操作的一些对象的集合。

3.2 表ADT

这里不对太多细致的概念进行描述。主要记录一些数据结构的特点。

1. 数组

• 特点：
  • 只有findKth操作花费常数时间。
• 缺点：
  • 插入和删除慢，时间复杂度 O(N) 。插入和删除之后需要对影响到的所有数据进行移动。

2. 链表

• 特点：
  • findKth 不如数组效率高，findKth(i) 花费O(i)，
  • remove 方法可以通过修改一个next引用来实现。删除最后一项比较复杂，需要找出最后的节点，把它的next改为null，然后再持有最后节点的链。
  • insert 方法需要使用new操作符从系统取得一个新的节点，然后执行两次引用的调整。
  • 可以让每一个节点持有一个指向它在表中的前驱节点的链，这种链成为双链表。

3.3 Java Collections API

1. Collection接口

Collection接口扩展了Iterable接口。实现了Iterable接口的那些类可以拥有增强的for循环。

2. Iterator接口

实现Iterator接口必须提供iterator方法，该方法返回一个Iterator类型的对象。
Iterator的remove方法的优点在于，Collection的remove方法必须首先找出被删除的项。

3. List接口、ArrayList类和LinkedList

• ArrayList
  • get() 时间消耗为常数
  • set() 时间消耗为常数
  • 缺点： add() remove() contains() 消耗昂贵，除非在末尾，前端的操作时间复杂度是 O(N)
• LinkedList
  • addFirst()
  • removeFirst()
  • addLast()
  • removeLast()
  • 缺点：不易检索，get() 代价昂贵，contains的时间呈线性关系
• ListIterator接口
  • 扩展了List的Iterator
  • previous()
  • hasPrevious()
  • add()
  • set()

4. ArrayList的实现

import org.omg.CORBA.Object;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 第三章 3.4
 * 第47页
 * 本程序提供了一个ArrayList类的实现
 */
public class MyArrayList<AnyType> implements Iterable<AnyType> {

    public static final int DEFAULT_CAPACITY = 10;

    private int theSize;

    private 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 anyType) {
        if (idx < 0 || idx > size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        AnyType old = theItems[idx];
        theItems[idx] = anyType;
        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];
        }
    }

    /**
     * 添加到末端的代价是昂贵的，时间复杂度O(N)
     * @param anyType
     * @return
     */
    public boolean add(AnyType anyType) {
        add(size(), anyType);
        return true;
    }

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

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

    @Override
    public Iterator<AnyType> iterator() {
        return new ArrayListIterator<AnyType>(this);
    }

    public class ArrayListIterator<AnyType> implements Iterator<AnyType> {

        private int current = 0;
        private MyArrayList<AnyType> theList;

        public ArrayListIterator(MyArrayList<AnyType> list){
            theList = list;

        }

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

        /**
         * 因为next中访问theItems 是非法的，所以构造一个ArrayList<>的对象，在构造方法中将MyArrayList传递给theList
         * @return
         */
        @Override
        public AnyType next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return theList.theItems[current ++];
        }

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

    }

}

5. LinkedList的java实现

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 第三章 3.5
 * 第54页
 * 本程序提供了一个LinkedList类的实现
 *
 */
public class MyLinkedList<AnyType> implements Iterable<AnyType> {

    private int theSize;
    private int modCount = 0;
    private Node<AnyType> beginMarker; // 开始标记
    private Node<AnyType> endMarker; // 结束标记

    /**
     * 节点
     * @param <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();
    }

    private 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 add(AnyType x) {
        add(size(), x);
        return true;
    }

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

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

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


    @Override
    public Iterator<AnyType> iterator() {
        return new LinkedListIterator();
    }

    private class LinkedListIterator implements Iterator<AnyType> {

        private Node<AnyType> current = beginMarker.next;
        private int expectedModCount = modCount;
        private boolean okToRemove = false;

        @Override
        public boolean hasNext() {
            return current != endMarker;
        }

        @Override
        public AnyType next() {
            if(modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if(!hasNext()) {
                throw  new NoSuchElementException();
            }

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

        @Override
        public void remove() {
            if(modCount != expectedModCount) {
                throw  new ConcurrentModificationException();
            }
            if(!okToRemove) {
                throw new IllegalStateException();
            }
            MyLinkedList.this.remove(current.prev);
            expectedModCount++;
            okToRemove = false;
        }
    }


}