一、java 集合包最常用的的2个接口Collection /和Map
List接口
最常用的有ArrayList ,LinkedList, Vector,Stack
ArrayList 的实现如下：
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
可以看出它是通过数组来操作的，那么他的增删查都是通过数组方法的来实现：
/**
* 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) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
删除要复杂点：
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);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
将index 后面的对象当成一个数组，移动到index位置，然后将最后的一个给null.
get 最简单直接按数组下标找。
总结：
ArrayList 是一个基于数组实现的非线性安全的不限制容量的容器。在增加的时候要扩容，删除的时候却不减少容量
LinkedList：这是一个很有意思的双向链表
初始化的时候首先要new 一个 内部的entry 对象 。这个 对象代表一个元素
private static class Entry<E> {
E element; //当前元素
Entry<E> next; //下一个
Entry<E> previous; //前一个
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
/**
* Constructs an empty list.
*/
public LinkedList() {
header.next = header.previous = header; //都指给自己
}
增加元素的时候 首先要创建一个 newEntry 将newEntry 前一个元素的next指给自己，将自己的next 的元素的previous 指向自己。 通俗点说，有2个位置，新来的坐后面，对面的人说，我是你的下一个，对将要来的第3个人说，我是你的前一个。
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;
}
删除元素的时候 就告诉你前面的说我走了，你的后面的将是我的后面的。告诉你的后面，你的前面的将是我的前面的。
我自己的都为空，你们再也找不到我了。3人行变成2人行。
public boolean remove(Object o) {
if (o==null) {
for (Entry<E> e = header.next; e != header; e = e.next) {
if (e.element==null) {
remove(e);
return true;
}
}
} else {
for (Entry<E> e = header.next; e != header; e = e.next) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}
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;
}
在LinkedList 里面 查找是意见比较麻烦的事情，因为没有直接的索引，得一个一个去询问，jdk里面给的方法是：如果index >size/2 从后面找，否则从前面找。一直找到为止
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;
}
LinkedList 总结: 他是一个非线性安全的基于双向链表实现的容易。元素相互之间都非常熟悉。
Vector
Vector 其实跟ArrayList 的实现方式基本相同，但是他的方法前面都加了 synchronized.还有一点区别就是他的扩容策略跟ArrayList不一样。
private void ensureCapacityHelper(int minCapacity) {
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object[] oldData = elementData;
//如果容量不足，将原来的容量*2
int newCapacity = (capacityIncrement > 0) ?
(oldCapacity + capacityIncrement) : (oldCapacity * 2);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
Vector 总结： 他是一个
线程安全的ArrayList 。
Stack
Stack 继承自Vector push 操作就是vector 的addElement peek 获得最后一个元素。pop 调用peek 同时删除最后一个元素。
相关文章
