list set map

//Implementing this interface allows an object to be the target of the "foreach" statement.

public interface Iterable<T>

{

    /**
     * Returns an iterator over a set of elements of type T.
     *
     * @return an Iterator.
     */
    Iterator<T> iterator();
}

public interface Collection<E> extends Iterable<E>

{

}

//An ordered collection (also known as a <i>sequence</i>).

//Unlike sets, lists typically allow duplicate elements.

public interface List<E> extends Collection<E>

{

        int size();  boolean isEmpty();   boolean contains(Object o);   Iterator<E> iterator();   Object[] toArray();

       <T> T[] toArray(T[] a);     boolean add(E e);    boolean remove(Object o);   

       boolean containsAll(Collection<?> c);     boolean addAll(Collection<? extends E> c);

       boolean addAll(int index, Collection<? extends E> c);     boolean removeAll(Collection<?> c);

      boolean retainAll(Collection<?> c);       void clear();     boolean equals(Object o);
     int hashCode();        E get(int index);      E set(int index, E element);      void add(int index, E element);

     E remove(int index);     int indexOf(Object o);    int lastIndexOf(Object o);      ListIterator<E> listIterator();

    ListIterator<E> listIterator(int index);     List<E> subList(int fromIndex, int toIndex);

 

 

}

//A collection that contains no duplicate elements

public interface Set<E> extends Collection<E> {}

////////////////////////////////////////////////////////////////

 //LinkedList适合快速的增加  删除元素，是以 栈的形式管理数据，最先加的元素被压入栈底，后面 加的元素在栈顶,类似于StringBuilder，StringBuffer可以再内部修改结构，又不需要创建新的对象
        LinkedList<Integer> linkedList = new LinkedList<Integer>();
        linkedList.add(110);
        linkedList.add(180);
        linkedList.add(190);
        System.out.println(linkedList);//[110, 180, 190]
       // Pushes an element onto the stack represented by this list.
        //In other words, inserts the element at the front of this list.
        //This method is equivalent to addFirst()  它内部就是用addFirst()实现的.
        linkedList.push(1);
        System.out.println(linkedList);//[1, 110, 180, 190]
         //This method is equivalent to  removeFirst().
        //它内部就是用 removeFirst()实现的.
        linkedList.pop();
        System.out.println(linkedList);//[110, 180, 190]
        linkedList.add(1, 111);
        linkedList.add(2, 222);
        System.out.println(linkedList);//[110, 111, 222, 180, 190]

//系统方法add

public boolean add(E e) {
 addBefore(e, header);
        return true;
    }
 private Entry<E> addBefore(E e, Entry<E> entry) {
 Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
 newEntry.previous.next = newEntry;
 newEntry.next.previous = newEntry;
 size++;
 modCount++;
 return newEntry;
    }

//系统方法remove

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

 private E remove(Entry<E> e) {
 if (e == header)
     throw new NoSuchElementException();

        E result = e.element;
 e.previous.next = e.next;
 e.next.previous = e.previous;
        e.next = e.previous = null;
        e.element = null;
 size--;
 modCount++;
        return result;
    }

//get 效率没有  arraylist  高，它要遍历每个元素

 public E get(int index) {

        return entry(index).element;

    }

 private Entry<E> entry(int index) {

        if (index < 0 || index >= size)

            throw new IndexOutOfBoundsException("Index: "+index+

                                                ", Size: "+size);

        Entry<E> e = header;

        if (index < (size >> 1)) {

            for (int i = 0; i <= index; i++)    //开始遍历  

                e = e.next;

        } else {

            for (int i = size; i > index; i--)   //开始遍历  

                e = e.previous;

        }

        return e;

    }

 

 

///////////////////////////////////////////////////////////////////arraylist  查询比较快，只要给index就可以查到

add  remove  都要copy  耗资源 内存  比较慢

get 通过index就可以了，以数组的 形式

 public E get(int index) {

RangeCheck(index);

 

return (E) elementData[index];

    }

 ArrayList<Integer> arrayList = new  ArrayList<Integer>();
      arrayList.add(110);
      arrayList.add(120);
      arrayList.add(0, 0);
      System.out.println(arrayList);//[0, 110, 120]    看样子跟linkedlist一样，其实不一样，内部实现的方法不一样

//先看add 方法

 public boolean add(E e) {
 ensureCapacity(size + 1);  // Increments modCount!!
 elementData[size++] = e;
 return true;
    }
//再看里面的ensureCapacity(size + 1); 

 public void ensureCapacity(int minCapacity) {
 modCount++;
 int oldCapacity = elementData.length;
 if (minCapacity > oldCapacity) {
     Object oldData[] = elementData;
     int newCapacity = (oldCapacity * 3)/2 + 1;
         if (newCapacity < minCapacity)
  newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);//把list  copy 到 一个新的list

//一个原始数组的副本，截断或用null填充以获得指定的长度  这样很浪费资源  制造很多垃圾

}
    }
 /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
 RangeCheck(index);

 modCount++;
 E oldValue = (E) elementData[index];

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

 return oldValue;
    }

 

//////////////////////////////////////////////////////////////hashset   乱序的，随便排的，不是按加入的先后顺序排的

add

Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false.

如果加的元素在集合里没有就加进去，return  true

如果加的元素在集合里有    就不加进去，保持原来集合的状态  return  false 

 public boolean add(E e) {
 return map.put(e, PRESENT)==null;
    }

 public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());//把hashset的值做为map的键值，得到它的hashcode
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;

           //遍历set的所有元素，先比hashcode  然后再比值 ，两者都符合则返回旧值

         //不符合的话就加入set
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

hashset  取元素

 Iterator<Integer> iterator = hashSet.iterator();
       Integer next = iterator.next();
       System.out.println(next);
       for (int i = 0; i <hashSet.size(); i++)
    {
           if(iterator.hasNext())
        System.out.println(iterator.next());
    }

//remove比较麻烦   因为内部是以hashmap的原理实现的。hashset的值就是hashmap里的键值

//所以要知道删除元素是什么，不能通过index

public boolean remove(Object o) {
 return map.remove(o)==PRESENT;
    }
///////////////////////////////////////////////////////////treeset    默认排序，不是按加入的先后顺序排序，是按int char....等

add

  public boolean add(E e) {
 return m.put(e, PRESENT)==null;
    }

.....................................

remove比较麻烦，要知道值，不能通过index

public boolean remove(Object o) {
 return m.remove(o)==PRESENT;
    }