1、Java中的三大类集合list、set、map
其中list和set均实现了collection接口，并且应用了泛型；
public interface List<E> extends Collection<E>
public interface Set<E> extends Collection<E>
2、collection接口
3、list接口
list的两个主要特点：有序、可重复；另外还提供了ListIterator访问元素的方法，ListIterator接口中定义的方法如下：
list中set和add方法的区别：set-替换该位置的元素，返回之前的元素；add在该位置增加元素，并改变该位置及其右面位置的元素位置；
3、set接口
set接口没有什么特别的方法，和collection接口声明的方法完全一致。
4、常见的list的三个实现类：arraylist、LinkedList、vector
4.1 arraylist
arraylist中的变量
默认大小--
/** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10;
空列表--
/** * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {};
数组，用于存储数据----
/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to * DEFAULT_CAPACITY when the first element is added. */ private transient Object[] elementData;
arraylist大小---
/** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size;
array最大值----
/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
一些方法解读：
去除list中不用的存储----减少内存浪费
/** * Trims the capacity of this <tt>ArrayList</tt> instance to be the * list's current size. An application can use this operation to minimize * the storage of an <tt>ArrayList</tt> instance. */ public void trimToSize() { modCount++; if (size < elementData.length) { elementData = Arrays.copyOf(elementData, size); } }
增加存储空间---
/** * Increases the capacity of this <tt>ArrayList</tt> instance, if * necessary, to ensure that it can hold at least the number of elements * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ public void ensureCapacity(int minCapacity) { int minExpand = (elementData != EMPTY_ELEMENTDATA) // any size if real element table ? 0 // larger than default for empty table. It's already supposed to be // at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
增加存储空间方法---默认扩展为原来的两倍
/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
返回元素第一次|最后一次出现的位置-----
/** * Returns the index of the first occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the lowest index <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, * or -1 if there is no such index. */ public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; } /** * Returns the index of the last occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the highest index <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, * or -1 if there is no such index. */ public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; }
增加元素---set 和 add的区别
/** * Replaces the element at the specified position in this list with * the specified element. * * @param index index of the element to replace * @param element element to be stored at the specified position * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } /** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } /** * Inserts the specified element at the specified position in this * list. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
4.2 LinkedList
linkedlist结构看起来并不复杂，主要成员变量如下：
transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last;
Node的实现如下：
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
也就是说在linkeedlist中，只记录了头节点和尾节点，通过节点之间的传递关系来维持整个linkedlist；
增加头节点的方法-----
/** * Links e as first element. */ private void linkFirst(E e) { //拷贝旧的头节点 final Node<E> f = first; //创建一个新节点 指向原先的头节点 final Node<E> newNode = new Node<>(null, e, f); //将此节点作为头节点 first = newNode; //如果原先的头节点为null 则加入后头尾节点是同一个节点 if (f == null) last = newNode; //否则将原先的头节点的前置连接修改为新的头节点 else f.prev = newNode; //总数目+1 size++; modCount++; }
增加尾节点的方法------
/** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
在一个元素前面增加一个元素-----
/** * Inserts element e before non-null Node succ. */ void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
在一个元素后面增加一个元素（个人所写）
public void linkAfter(E e,Node<E> succ){ Node oldAfter = succ.next; Node newNode= new Node(succ,e,oldAfter); succ.next = newNode; if(oldAfter!=null) oldAfter.pre = newNode else last=newNode; size++ }
remove元素
/** * Unlinks non-null first node f. */ private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; } /** * Unlinks non-null last node l. */ private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; } /** * Unlinks non-null node x. */ E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }
总结一下，删除元素有四点注意，
前节点或者是后节点是否为null，
将删除的元素置为null，以便GC回收
最后增删元素后可能需要修改null节点；
修改size大小
下面都是个人模仿写的一些代码，留作记录
public void linkedfirst(E e){ Node f = first; Node newFirst = Node(null,E,f); first = newFirst; if(f!=null) f.pre = newFirst; else last=newFirst; size++; } public void linkLast(E){ Node l = last; Node newNode = new Node(last,E,null); last = newNode; if(last==null){ first = newNode; }else{ l.next = newNode; } } public void linkAfter(E e,E succ){ Node oldAfter = succ.next; Node newNode= new Node(succ,e,oldAfter); succ.next = newNode; if(oldAfter!=null) oldAfter.pre = newNode else last=newNode; size++ } public element unlinklast{ Node pre = last.pre; last.item = null; last.pre = null; last = pre; if(pre!=null) pre.next = null; else first = null; } public unlike (Node e){ Node pre = e.pre; Node next = e.next; Node item = e.item if(pre == null) first = next; else pre.next = next; if(next == null) last = pre; else next.pre = pre; e.pre = null; e.next = null; e.next = null; size--; }
根据索引位置获取元素，索引位置大于中位置，从后向前，否则从前向后
/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
弹出一个元素，区别在于list为空的时候，返回null还是抛出异常：
/** * Retrieves and removes the head (first element) of this list. * * @return the head of this list, or {@code null} if this list is empty * @since 1.5 */ public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } /** * Retrieves and removes the head (first element) of this list. * * @return the head of this list * @throws NoSuchElementException if this list is empty * @since 1.5 */ public E remove() { return removeFirst(); }
向链表头或者尾部增加元素：
/** * Adds the specified element as the tail (last element) of this list. * * @param e the element to add * @return {@code true} (as specified by {@link Queue#offer}) * @since 1.5 */ public boolean offer(E e) { return add(e); } // Deque operations /** * Inserts the specified element at the front of this list. * * @param e the element to insert * @return {@code true} (as specified by {@link Deque#offerFirst}) * @since 1.6 */ public boolean offerFirst(E e) { addFirst(e); return true; }
/**
* Inserts the specified element at the end of this list.
*
* @param e the element to insert
* @return {@code true} (as specified by {@link Deque#offerLast})
* @since 1.6
*/
public boolean offerLast(E e) {
addLast(e);
return true;
}
压入和弹出元素
/** * Pushes an element onto the stack represented by this list. In other * words, inserts the element at the front of this list. * * <p>This method is equivalent to {@link #addFirst}. * * @param e the element to push * @since 1.6 */ public void push(E e) { addFirst(e); } /** * Pops an element from the stack represented by this list. In other * words, removes and returns the first element of this list. * * <p>This method is equivalent to {@link #removeFirst()}. * * @return the element at the front of this list (which is the top * of the stack represented by this list) * @throws NoSuchElementException if this list is empty * @since 1.6 */ public E pop() { return removeFirst(); }
4.3 Vector
成员变量，数组 + 容量 + 增量值：
/** * The array buffer into which the components of the vector are * stored. The capacity of the vector is the length of this array buffer, * and is at least large enough to contain all the vector's elements. * * <p>Any array elements following the last element in the Vector are null. * * @serial */ protected Object[] elementData; /** * The number of valid components in this {@code Vector} object. * Components {@code elementData[0]} through * {@code elementData[elementCount-1]} are the actual items. * * @serial */ protected int elementCount; /** * The amount by which the capacity of the vector is automatically * incremented when its size becomes greater than its capacity. If * the capacity increment is less than or equal to zero, the capacity * of the vector is doubled each time it needs to grow. * * @serial */ protected int capacityIncrement;
构造函数，初始化为10：
/** * Constructs an empty vector with the specified initial capacity and * capacity increment. * * @param initialCapacity the initial capacity of the vector * @param capacityIncrement the amount by which the capacity is * increased when the vector overflows * @throws IllegalArgumentException if the specified initial capacity * is negative */ public Vector(int initialCapacity, int capacityIncrement) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } /** * Constructs an empty vector with the specified initial capacity and * with its capacity increment equal to zero. * * @param initialCapacity the initial capacity of the vector * @throws IllegalArgumentException if the specified initial capacity * is negative */ public Vector(int initialCapacity) { this(initialCapacity, 0); } /** * Constructs an empty vector so that its internal data array * has size {@code 10} and its standard capacity increment is * zero. */ public Vector() { this(10); }
vector是线程安全的容器，大部分方法都是同步的！