继承了Iterable(可迭代) 接口, 继承实现此接口,允许(该实现类的)对象使用Iterator iterator()方法得到iterator迭代器 进而使用“foreach”语句(注:foreach语法 实际上是调用iterator()方法)
ListList继承了Collection,并且扩展了新的功能,比Collection集合约束更细致。
特点:1.元素有索引
2.元素可以重复
3.元素存取顺序一致
ArrayList底层维护了一个可变的数组结构
源码分析:
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size;
空参构造初始化:
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
add源码:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!! 主要是扩容
elementData[size++] = e;//添加元素
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY = 10
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//记录数据结构发生变化的次数
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);// >>-二进制位运算符 右移 除2的意思 新的容量=老的容量+老的容量/2 1.5被扩容
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);//复制产生指定一个长度的新数组对象
}
扩容方式:
1.初始化ArrayList时,容量为10.
2.容量超过10时,ArrayList会以1.5倍原来容量进行扩容。
ArrayList初始化+add测试Demo:
public class ArrayListTest {
public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
ArrayList arrayList = new ArrayList<>();
//测试ArrayList容量的变化
//反射获取ArrayList中的elementData数组
Class arrayListClass = ArrayList.class;
Field elementData = arrayListClass.getDeclaredField("elementData");
elementData.setAccessible(true);
Object[] c = (Object[])elementData.get(arrayList);
System.out.println("初始化数组容量:"+c.length);
System.out.println("初始化数组容量数组:"+ Arrays.deepToString(c));
for (int i = 1; i < 50; i++) {
arrayList.add(i+" ");
Object[] o = (Object[])elementData.get(arrayList);
System.out.println("第"+i+"次添加元素");
System.out.println("数组容量:"+o.length);
System.out.println("数组:"+ Arrays.deepToString(o));
}
}
}
结果:
初始化数组容量:0 初始化数组容量数组:[] 第1次添加元素 数组容量:10 数组:[1 , null, null, null, null, null, null, null, null, null] 第2次添加元素 数组容量:10 数组:[1 , 2 , null, null, null, null, null, null, null, null] 第3次添加元素 数组容量:10 数组:[1 , 2 , 3 , null, null, null, null, null, null, null] 第4次添加元素 数组容量:10 数组:[1 , 2 , 3 , 4 , null, null, null, null, null, null] 第5次添加元素 数组容量:10 数组:[1 , 2 , 3 , 4 , 5 , null, null, null, null, null] 第6次添加元素 数组容量:10 数组:[1 , 2 , 3 , 4 , 5 , 6 , null, null, null, null] 第7次添加元素 数组容量:10 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , null, null, null] 第8次添加元素 数组容量:10 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , null, null] 第9次添加元素 数组容量:10 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , null] 第10次添加元素 数组容量:10 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] 第11次添加元素 数组容量:15 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , null, null, null, null] 第12次添加元素 数组容量:15 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , null, null, null] 第13次添加元素 数组容量:15 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , null, null] 第14次添加元素 数组容量:15 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , null] 第15次添加元素 数组容量:15 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 ] 第16次添加元素 数组容量:22 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , null, null, null, null, null, null] 第17次添加元素 数组容量:22 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , null, null, null, null, null] 第18次添加元素 数组容量:22 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , null, null, null, null] 第19次添加元素 数组容量:22 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , null, null, null] 第20次添加元素 数组容量:22 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , null, null] 第21次添加元素 数组容量:22 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , null] 第22次添加元素 数组容量:22 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 ] 第23次添加元素 数组容量:33 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , null, null, null, null, null, null, null, null, null, null] 第24次添加元素 数组容量:33 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , null, null, null, null, null, null, null, null, null] 第25次添加元素 数组容量:33 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , null, null, null, null, null, null, null, null] 第26次添加元素 数组容量:33 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , null, null, null, null, null, null, null] 第27次添加元素 数组容量:33 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , null, null, null, null, null, null] 第28次添加元素 数组容量:33 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , null, null, null, null, null] 第29次添加元素 数组容量:33 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , null, null, null, null] 第30次添加元素 数组容量:33 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , null, null, null] 第31次添加元素 数组容量:33 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , null, null] 第32次添加元素 数组容量:33 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , null] 第33次添加元素 数组容量:33 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 ] 第34次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , null, null, null, null, null, null, null, null, null, null, null, null, null, null, null] 第35次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , null, null, null, null, null, null, null, null, null, null, null, null, null, null] 第36次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , null, null, null, null, null, null, null, null, null, null, null, null, null] 第37次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , null, null, null, null, null, null, null, null, null, null, null, null] 第38次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , null, null, null, null, null, null, null, null, null, null, null] 第39次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , null, null, null, null, null, null, null, null, null, null] 第40次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , null, null, null, null, null, null, null, null, null] 第41次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , 41 , null, null, null, null, null, null, null, null] 第42次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , 41 , 42 , null, null, null, null, null, null, null] 第43次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , 41 , 42 , 43 , null, null, null, null, null, null] 第44次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , 41 , 42 , 43 , 44 , null, null, null, null, null] 第45次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , 41 , 42 , 43 , 44 , 45 , null, null, null, null] 第46次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , 41 , 42 , 43 , 44 , 45 , 46 , null, null, null] 第47次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , 41 , 42 , 43 , 44 , 45 , 46 , 47 , null, null] 第48次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , 41 , 42 , 43 , 44 , 45 , 46 , 47 , 48 , null] 第49次添加元素 数组容量:49 数组:[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , 41 , 42 , 43 , 44 , 45 , 46 , 47 , 48 , 49 ] Process finished with exit code 0remove源码:
public E remove(int index) {
rangeCheck(index);//检查索引是否合法
modCount++;
E oldValue = elementData(index);//通过索引获得元素
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//通过System.arraycopy方法完成数据拷贝,将要移除的元素不在copy到新数组中
elementData[--size] = null; // clear to let GC do its work
return oldValue;//返回移除的元素
}
set源码:
public E set(int index, E element) {
rangeCheck(index);//检查索引是否合法
E oldValue = elementData(index);//获取索引对应的元素
elementData[index] = element;//重新赋值
return oldValue;//返回老元素
}
get源码:
public E get(int index) {
rangeCheck(index);//检查索引是否合法
return elementData(index);//获取索引对应的元素并返回
}
Vector
底层结构与ArrayList一样,也是实现了动态可变的数组。具体实现和ArrayList非常相似。
不同之处在于,里面的方法时间使用了同步,在多线程环境中是安全的。因为方法大多是同步的,所以在多线程场景下效率会比较低
源码(方法大都被synchronized修饰)
LinkedList底层结构是双向链表。双向链表是链表的一种,他的每个数据节点中都有两个指针(地址),分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。
transient int size = 0;//元素个数
transient Node first;//指向链表的第一个节点
transient Node last;//指向链表的最后一个节点
private static class Node {
E item;//数据元素
Node next;//指向后一个元素
Node prev;//指向前一个元素
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
add源码:
public boolean add(E e) {
linkLast(e);//将元素放置到链表的最后位置
return true;
}
void linkLast(E e) {
final Node l = last;//临时这只最末个节点
final Node newNode = new Node<>(l, e, null);//基于新元素构建一个新节点
last = newNode;//将新节点设置为最末节点
if (l == null)//判断之前是否还有节点
first = newNode;//把当前节点设置为第一个节点
else
l.next = newNode;//把原来最后一个结点的next指向新建的这个节点
size++;
modCount++;
}
remove源码:
public E remove(int index) {
checkElementIndex(index);//检查索引是否越界异常
return unlink(node(index));
}
Node node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {//index是否小于size/2
//小于size/2 则从头往后找
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;//不断遍历后移最终得到x=Node[index]节点
return x;
} else {
//大于size/2 则从最后往回找
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;//不断遍历前移最终得到x=Node[index]节点
return x;
}
}
E unlink(Node x) {//将指定节点删除
// assert x != null;
final E element = x.item;
final Node next = x.next;
final Node prev = x.prev;
if (prev == null) {//prev == null 删除的是第一个节点
first = next;//将next节点(即第二个节点)设置为第一节点
} else {
prev.next = next;//将x前一个结点的next设置为x下一个节点(即跳过x节点)
x.prev = null;
}
if (next == null) {//删除的是最后一个节点
last = prev;//将x前一个节点设置为最后一个节点
} else {
next.prev = prev;//将x后一个结点的prev设置为x前一个节点(即跳过x节点)
x.next = null;//清空 GC
}
x.item = null;
size--;
modCount++;
return element;//返回删除的元素
}
Set
Set集合继承了Collection集合,并没有新增任何方法,只是对于集合的定义约束更加明确了。
特点:
1.集合元素不可以重复
2.集合中的元素不能保证存取顺序一致
3.集合中的元素是没有索引的
数据结构:底层是由HsahMap(哈希表结构)实现的
源码:private transient HashMapLinkedHashSetmap; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); public HashSet() { map = new HashMap<>();//直接赋值一个HashMap } public boolean add(E e) { return map.put(e, PRESENT)==null;//直接把HashSet添加的元素当作HashMap的键使用 PRESENT= new Object()默认设置的 } public boolean remove(Object o) { return map.remove(o)==PRESENT; }
数据结构:底层是由双向链表+HsahMap哈希表实现的
TreeSet数据结构:TreeMap(红黑树)实现的
源码:private static final Object PRESENT = new Object();
public TreeSet() {
this(new TreeMap());//内部创建了一个TreeMap
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;//直接把TreeSet添加的元素当作TreeMap的键使用 PRESENT= new Object()默认设置的
}
注意:
若对Set的理解有困难,建议单独学习下HashMap、树;学完HashMap及树之后,再学习HashSet、LinkedHashSet、TreeSet就非常容易了



