数据结构 - 代码片段

public class ArrayList<T> implements IList<T>, Iterable<T> {
    private static final int DEFAULT_CAPACITY = 10;
    private int size;
    private T[] items;

    public ArrayList(){
        this(DEFAULT_CAPACITY);
    }

    public ArrayList(int capacity){
        this.items = (T[]) new Object[capacity];
        this.size = 0;
    }

    public void clear(){ this.size = 0; }

    public int size(){ return this.size; }

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

    public boolean contains(T item){
        for (int i = 0; i < this.size; i++){
            if (this.items[i] == item) return true;
        }
        return false;
    }

    public T get(int index) {
        if (index >= this.size || index < 0) throw new IndexOutOfBoundsException();
        return this.items[index];
    }

    public void set(int index, T item) {
        if (index >= this.size || index < 0) throw new IndexOutOfBoundsException();
        this.items[index] = item;
    }

    public boolean add(T item){
        add(this.size, item);
        return true;
    }

    public void add(int index, T item) {
        if (index > this.size || index < 0) throw new IndexOutOfBoundsException();
        if (this.size == this.items.length) ensureCapacity(this.size * 2);
        System.arraycopy(this.items, index, this.items, index + 1, this.size - index);
        this.items[index] = item;
    }

    public boolean remove(T item){
        int index = -1;
        for (int i = 0; i < this.size; i++)
            if (item.equals(this.items[i])) index = i;

        if (index != -1){
            remove(index);
            return true;
        }
        return false;
    }

    public void remove(int index) {
        if (index >= size() || index < 0) throw new IndexOutOfBoundsException();
        System.arraycopy(this.items, index + 1, this.items, index, this.size - index);
        --this.size;
    }

    private void ensureCapacity(int capacity){
        if (capacity < this.size) return;
        T[] old = this.items;
        this.items = (T[]) new Object[capacity];
        System.arraycopy(old, 0, this.items, 0, old.length);
    }

    public Iterator<T> iterator() {
        return new ArrayListIterator();
    }

    private class ArrayListIterator implements Iterator<T>{
        private int current = 0;

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

        public T next() {
            if (! hasNext()) throw new NoSuchElementException();
            return items[current++];
        }

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

public class LinkedList<T> implements Iterable<T> {
    private int size;
    private int modCount;
    private final Node<T> startNode;
    private final Node<T> endNode;

    public MyLinkedList(){
        this.startNode = new Node<T>(null, null, null);
        this.endNode = new Node<T>(null, this.startNode, null);
        this.startNode.next = this.endNode;

        this.size = 0;
        modCount++;
    }

    public int size(){ return size; }

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

    public boolean contains(T item){
        Node<T> curr = startNode;
        while (curr.next != null) {
            curr = curr.next;
            if (curr.data == item) return true;
        }
        return false;
    }

    public boolean add(T item) {
        add(size(), item);
        return true;
    }

    public void add(int index, T item){
        addBefore(getNode(index, 0, size()), item);
    }

    private void addBefore(Node<T> node, T item){
        Node<T> newNode = new Node<T>(item, node.prev, node);
        newNode.prev.next = newNode;
        node.prev = newNode;
        size++;
        modCount++;
    }

    public boolean remove(T item){
        Node<T> curr = startNode;
        while (curr.next != endNode){
            curr = curr.next;
            if (curr.data == item){
                remove(curr);
                return true;
            }
        }
        return false;
    }

    public void remove(int index){
        remove(getNode(index));
    }

    private void remove(Node<T> node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
        modCount++;
    }

    public Node<T> getNode(int index){
        return getNode(index, 0, size() - 1);
    }

    public Node<T> getNode(int index, int lower, int upper){
        Node<T> node;
        if (index < lower || index > upper)
            throw new IndexOutOfBoundsException();
        if (index < size() / 2){
            node = startNode.next;
            for (int i = 0; i < index; i++)
                node = node.next;
        }else {
            node = endNode;
            for (int i = size(); i > index; i--)
                node = node.prev;
        }
        return node;
    }

    public T get(int index){
        return getNode(index).data;
    }

    public T set(int index, T item){
        Node<T> node = getNode(index);
        T oldValue = node.data;
        node.data = item;
        return oldValue;
    }

    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }

    public static class Node<T>{
        public T data;
        public Node<T> prev;
        public Node<T> next;

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

    public class LinkedListIterator implements Iterator<T>{
        private Node<T> curr = startNode.next;
        private int expectedModCount = modCount;
        private boolean okToRemove = false;

        public boolean hasNext() {
            return curr != endNode;
        }

        public T next() {
            if (modCount != expectedModCount) throw new ConcurrentModificationException();
            if (!hasNext()) throw new NoSuchElementException();
            
            T nextItem = curr.data;;
            curr = curr.next;
            okToRemove = true;
            return nextItem;
        }

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