Table, stack and queue Java implementation

Data structure and algorithm analysis

Table, stack, queue

List interface, ArrayList class and LinkedList class

1.1 list interface inherits Collection interface

public interface List<E> extends Collection<E>{
    E get(int index);
    E set(int index,E newval);
    void add(int index,E x);
    void remove(int index);
    ListIterator<E> listInterator(int pos);
    //......
}

There are two popular implementations of List ADT

  • The ArrayList class is a scalable array implementation.
    • Advantage: the call to get and set takes a constant time
    • Disadvantage: expensive deletion of inserts and existing items
  • The LinkedList class provides a double linked list implementation of List ADT
    • Advantage: the cost of inserting new items and deleting existing items is small
    • Disadvantages: it's not easy to index, and get calls are expensive

Example
Delete all items in the table with even values

 public static void removeEvensVer(List<Integer> list) {
        Iterator<Integer> itr = list.iterator();
        while (itr.hasNext()) {
            if (itr.next() % 2 == 0) {
                itr.remove();
            }
        }
    }

If the efficiency of passing a LinkedList < integer > is high, for an ArrayList, even if the iterator is located on the node to be deleted, because its data needs to be moved, its remove() method is expensive.

1.2 ListIterator interface

List Iterator is the function of Iterator that extends list.

1.3 implementation of ArrayList class

public class MyArrayList<E> implements Iterable<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private int size;
    private E[] items;

    public MyArrayList() {
        doClear();
    }

    private void doClear() {
        this.size = 0;
        ensureCapacity(DEFAULT_CAPACITY);
    }

    public int size() {
        return size;
    }

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

    public void trimToSize() {
        ensureCapacity(size());
    }

    public E get(int index) {
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return items[index];
    }

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

    private void ensureCapacity(int newCapacity) {
        if (newCapacity < size) {
            return;
        }
        E[] old = items;
        items = (E[]) new Object[newCapacity];
        for (int i = 0; i < size(); i++) {
            items[i] = old[i];
        }
    }

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

    public void add(int index, E x) {
        if (items.length == size()) {
            ensureCapacity(size() * 2 + 1);
        }
        for (int i = size; i > index; i--) {
            items[i] = items[i - 1];
        }
        items[index] = x;
        size++;
    }

    public E remove(int index) {
        E removeItem = items[index];
        for (int i = index; i < size() - 1; i--) {
            items[i] = items[i + 1];
        }
        size--;
        return removeItem;
    }

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

    private class ArrayListIterator implements Iterator<E> {

        private int current = 0;

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

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

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

To expand the capacity of ensurcapacity, first store a reference of the original array, then allocate memory for the new array, and then copy the old content to the new array.

1.4 implementation of LinkedList class
public class MyLinkedList<E> implements Iterable<E> {

    private Node<E> beginMarker;
    private Node<E> endMarker;
    private int size;
    private int modCount = 0;


    private static class Node<E> {
        public Node(E d, Node<E> p, Node<E> n) {
            data = d;
            prev = p;
            next = n;
        }

        public E data;
        public Node<E> prev;
        public Node<E> next;
    }

    public MyLinkedList() {
        doClear();
    }

    private void doClear() {
        beginMarker = new Node<>(null, null, null);
        endMarker = new Node<>(null, beginMarker, null);
        this.size = 0;
        this.modCount++;
    }

    public int size() {
        return size;
    }

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

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

    public void add(int index, E x) {
        addBefore(getNode(index, 0, size()), x);
    }

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

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

    public E remove(int index) {
        return remove(getNode(index));
    }

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

    private E remove(Node<E> p) {
        p.next.prev = p.prev;
        p.prev.next = p.next;
        size--;
        modCount++;
        return p.data;
    }

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

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

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

    private class LinkedListIterator implements Iterator<E> {
        private Node<E> current = beginMarker.next;
        private int expectedModCount = modCount;                  // ①
        private boolean okToRemove = false;// ②
        @Override
        public boolean hasNext() {
            return current != endMarker;
        }

        @Override
        public E next() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            E nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }

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

In order to verify that the set is modified during the iteration, the iterator stores the modCount in the data field expectedModCount at ①, and if the next has been executed without subsequent removal at ②, the Boolean data field is true, okto remove is initialized to false, and the next method is set to true

Posted on Tue, 03 Dec 2019 17:14:23 -0800 by iceblossom