JDK Collection Code

PriorityQueue
It has contains and remove methods, but the time complexity is O(n).

    public boolean remove(Object o) {

        int i = indexOf(o);

        if (i == -1)

            return false;

        else {

            removeAt(i);

            return true;

        }

    }

    public boolean contains(Object o) {

        return indexOf(o) != -1;

    }

    private int indexOf(Object o) {

        if (o != null) {

            for (int i = 0; i < size; i++)

                if (o.equals(queue[i]))

                    return i;

        }

        return -1;

    }

    public Object[] toArray() {

        return Arrays.copyOf(queue, size);

    }

LinkedList can be used as Stack or queue.

public class LinkedList<E>

    extends AbstractSequentialList<E>

    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

ArrayList can't.

public class ArrayList<E> extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList.addAll - shallow copy - same to LinkedList.addAll - shallow copy too
When u call list.addAll(), No copy of the objects or their data are made; their references are simply added to the list object.

        final ArrayList< ArrayList<Integer> > a1= new ArrayList<>();

        a1.add(new ArrayList<Integer>());

        final ArrayList< ArrayList<Integer> > a2= new ArrayList<ArrayList<Integer>>();

        a2.addAll(a1);

        a1.get(0).add(0);

        a2.get(0).add(0);

        a2.add(new ArrayList<Integer>());

        // [[0, 0]]

        System.out.println(a1);

        // [[0, 0], []]

        System.out.println(a2);

    public static <T>

    int binarySearch(List<? extends Comparable<? super T>> list, T key) {

        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)

            return Collections.indexedBinarySearch(list, key);

        else

            return Collections.iteratorBinarySearch(list, key);

    }

    private static <T>

    int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {

        int low = 0;

        int high = list.size()-1;

        while (low <= high) {

            int mid = (low + high) >>> 1;

            Comparable<? super T> midVal = list.get(mid);

            int cmp = midVal.compareTo(key);

            if (cmp < 0)

                low = mid + 1;

            else if (cmp > 0)

                high = mid - 1;

            else

                return mid; // key found

        }

        return -(low + 1);  // key not found

    }

    private static <T>

    int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)

    {

        int low = 0;

        int high = list.size()-1;

        ListIterator<? extends Comparable<? super T>> i = list.listIterator();

        while (low <= high) {

            int mid = (low + high) >>> 1;

            Comparable<? super T> midVal = get(i, mid);

            int cmp = midVal.compareTo(key);

            if (cmp < 0)

                low = mid + 1;

            else if (cmp > 0)

                high = mid - 1;

            else

                return mid; // key found

        }

        return -(low + 1);  // key not found

    }

    /**

     * Gets the ith element from the given list by repositioning the specified

     * list listIterator.

     */

    private static <T> T get(ListIterator<? extends T> i, int index) {

        T obj = null;

        int pos = i.nextIndex();

        if (pos <= index) {

            do {

                obj = i.next();

            } while (pos++ < index);

        } else {

            do {

                obj = i.previous();

            } while (--pos > index);

        }

        return obj;

    }

Removing last object of ArrayList in Java

list.remove(list.size() - 1)

Here is how it's implemented. elementData does a lookup on the backing array (so it can cut it loose from the array), which should be constant time (since the JVM knows the size of an object reference and the number of entries it can calculate the offset), and numMoved is 0 for this case:

public E remove(int index) {
    rangeCheck(index); // throws an exception if out of bounds

    modCount++;        // each time a structural change happens
                       // used for ConcurrentModificationExceptions

    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // Let gc do its work

    return oldValue;
}

        final ArrayList<Integer> a1 = Lists.newArrayList(1, 2, 3);

        // a1.remove(a1.get(0));  // remove object

        a1.remove((Integer) 1); // remove object

        a1.remove(1); // remove index

How to implement ArrayList Iterator.remove:
java.util.ArrayList.Itr:

    private class Itr implements Iterator<E> {

        int cursor;       // index of next element to return

        int lastRet = -1; // index of last element returned; -1 if no such

        int expectedModCount = modCount;

        public boolean hasNext() {

            return cursor != size;

        }

        @SuppressWarnings("unchecked")

        public E next() {

            checkForComodification();

            int i = cursor;

            if (i >= size)

                throw new NoSuchElementException();

            Object[] elementData = ArrayList.this.elementData;

            if (i >= elementData.length)

                throw new ConcurrentModificationException();

            cursor = i + 1;

            return (E) elementData[lastRet = i];

        }

        public void remove() {

            if (lastRet < 0) // mean remove called twice

                throw new IllegalStateException();

            checkForComodification();

            try {

                ArrayList.this.remove(lastRet);

                cursor = lastRet;

                lastRet = -1;

                expectedModCount = modCount;

            } catch (IndexOutOfBoundsException ex) {

                throw new ConcurrentModificationException();

            }

        }

        @Override

        @SuppressWarnings("unchecked")

        public void forEachRemaining(Consumer<? super E> consumer) {

            Objects.requireNonNull(consumer);

            final int size = ArrayList.this.size;

            int i = cursor;

            if (i >= size) {

                return;

            }

            final Object[] elementData = ArrayList.this.elementData;

            if (i >= elementData.length) {

                throw new ConcurrentModificationException();

            }

            while (i != size && modCount == expectedModCount) {

                consumer.accept((E) elementData[i++]);

            }

            // update once at end of iteration to reduce heap write traffic

            cursor = i;

            lastRet = i - 1;

            checkForComodification();

        }

        final void checkForComodification() {

            if (modCount != expectedModCount)

                throw new ConcurrentModificationException();

        }

    }

ArrayDeque is kind of Circular Array
TreeSet
Complexity of treeset's subset method?
It is O(1), and returns a view with logarithmic extra overhead for its operations.


TreeMap
Java TreeMap time complexity - lowerKey

lowerKey() is a search in a balanced binary search tree, so it's obviously O(log n). You might want to read the source code, e.g. from here, to see how the tree is traversed.

Similarly, each operation with a NavigableMap returned from subMap() also requires O(log n)because you will need to traverse the tree to find elements you want.

Time complexity of TreeMap operations- subMap, headMap, tailMap


http://blog.csdn.net/cyantide/article/details/50955436

失败返回null或false（推荐使用）

• offer(); // 添加元素
• poll(); // 移除元素
• peek(); // 获取头一个元素

失败抛异常

• add(); // 添加元素
• remove(); // 移除元素
• element(); // 获取头一个元素

BlockingQueue

阻塞队列接口 
主要方法

• put(); // 添加元素，队列不可用时，阻塞
• take(); // 移除头一个元素，队列为空时不可用

PriorityBlockingQueue

一个无界阻塞队列，它使用与类 PriorityQueue 相同的顺序规则，并且提供了阻塞获取操作。虽然此队列逻辑上是无界的，但是资源被耗尽时试图执行 add 操作也将失败（导致 OutOfMemoryError）。此类不允许使用 null 元素。依赖自然顺序的优先级队列也不允许插入不可比较的对象（这样做会导致抛出 ClassCastException）

===========================================

ConcurrentLinkedQueue

一个无锁的基于链接节点的无界线程安全队列。当多个线程共享访问一个公共 collection 时，ConcurrentLinkedQueue 是一个恰当的选择。此队列不允许使用 null 元素 
ConcurrentLinkedQueue的size()，与大多数 collection 不同，此方法不是 一个固定时间操作。由于这些队列的异步特性，确定当前的元素数需要进行一次花费 O(n) 时间的遍历，性能很差，应该多用isEmpty()，少用或不用size()。