Collection

Iterable

Collection

实现接口

AbstractCollection

子类

List

AbstractList

arrayList中的元素可以随机访问

RandomAccess

实现该接口时使实现Object类中的clone()方法合法，使实现clone()方法后对象的调用不会报错

Cloneable

序列化接口，使数据序列化，如不给serialVersionUID赋值则会默认赋值，但更新类中的内容时serialVersionUID会重新赋值，此时会影响对象的反序列化，因此建议给serialVersionUID赋值

Serializable

ArrayList默认初始化容量为10，如超过最大容量时，ArrayList会通过grow()方法动态扩容

DEFAULT_CAPACITY

空Object数组，非空构造器时使用

EMPTY_ELEMENTDATA

DEFAULTCAPACITY_EMPTY_ELEMENTDATA

Object数组，存储ArrayList元素

elementData

Integer.MAX_VALUE-8

数组最大容量

MAX_ARRAY_SIZE

当前数组大小

size

属性

初始化DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组

ArrayList()

initialCapacity大于0，则直接初始化initialCapacity大小的Object[];如initialCapacity等于0，则初始化为EMPTY_ELEMENTDATA空数组；如EMPTY_ELEMENTDATA小于0，则会报错

初始化initialCapacity大小的数组

ArrayList(int initialCapacity)

初始化集合数组

ArrayList(Collection<? extends E> c)

构造器

添加元素，对size+1进行扩容处理。扩容完毕后，size++，将elementData[size++]设置为添加的元素

add(E e)

浅克隆

clone()

判断是否包含某个元素，如o为null，则直接遍历elementData数组是否存在null；如o不为null，则通过o的equal()方法进行遍历判断是否相等

contains(Object o)

remove(int index)

截取ArrayList，注意返回的为SubList内部类类型，而不是ArrayList类型

主要方法

方法

先判断elementData是否为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则获取DEFAULT_CAPACITY与所需容量的最大值，如elementData不为DEFAULT_CAPACITY，则直接获取所需容量；如果上述计算出的容量大于elementData的容量，则先对原容量进行1.5倍扩容，如扩容后容量还是小于需要的容量，则将容量设置为需要的容量，最后检测容量是否超过MAX_ARRAY_SIZE，如超过，则将容量设置为Integer.MAX_VALUE大小

扩容规则

ArrayList

AbstractSequentialList

Queue

Deque

实现此接口时，重写Object的clone()方法后调用此方法时不会报错

实现此接口时，可将对象序列化

链表首节点，transient关键字表示该属性不会被序列化，使对象只会存在在调用者内存中，而不会持久化

transient Node<E> first

链表尾节点

transient Node<E> last

链表当前容量

transient int size = 0

空参构造器

LinkedList()

调用addAll(Collection<? extends E> c)方法添加集合

LinkedList(Collection<? extends E> c)

添加元素，调用linkLast(E e)方法从最后添加元素，注意判断last是否为null，如为null需更新first的信息，最后更新last的信息和size++

如o为null，则从first开始遍历所有节点，判断是否有null节点；如不为null，则从first开始遍历所有节点，通过o的equal()方法判断是否相等

判断是否包含元素

如头节点为空，则报错

获取链表头节点

element()

如节点位置大于size的一半，则会从last遍历到节点；如小于size的一半，则会从first遍历到节点

获取指定位置的节点

get(int index)

添加元素到链表末尾

offer(E e)

取出头节点的值

peek()

取出头节点，并在链表中去除头节点

poll()

pop()

从头节点处添加元素

push(E e)

删除头节点，并返回头节点

remove()

更新index位置的节点值，并返回原来的值

item

preNode

nextNode

Node

内部类

LinkedList

优先级队列，基于优先级堆，队列的长度是无限的，实现方式为Object数组，数组拥有默认容量，如超过默认容量需进行扩容，队列中的元素不能为null

介绍

AbstractQueue

默认的Comparator

Comparator<? super E> comparator

默认容量

DEFAULT_INITIAL_CAPACITY = 11

最大容量

MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

队列结构修改次数

modCount = 0

队列实现数组

Object[] queue

队列当前元素数量

size = 0

初始化队列容量为DEFAULT_INITIAL_CAPACITY，comparator为null

PriorityQueue()

初始化队列容量为initialCapacity，comparator为null

PriorityQueue(int initialCapacity)

初始化队列容量为DEFAULT_INITIAL_CAPACITY，comparator为参数comparator

PriorityQueue(Comparator<? super E> comparator)

初始化队列容量为initialCapacity，comparator为参数comparator

初始化comparator为c的comparator，然后通过initFromPriorityQueue初始化queue和size

PriorityQueue(PriorityQueue<? extends E> c)

初始化comparator为c的comparator，然后通过initElementsFromCollection方法初始化queue和size

PriorityQueue(SortedSet<? extends E> c)

添加元素，通过offer方法添加元素

1.判断size+1是否大于queue的length，如大于则通过grow方法进行扩容

2.如size==0，则直queue[0]=e，如不等于0，则通过siftUp方法添加元素

添加元素至queue

如果原来数组的容量小于64，则新增容量为原容量+2；如大于等于64，则新增容量为原容量的一半

数组queue的扩容

grow(int minCapacity)

如comparator为空则调用siftUpComparable方法，反之则调用siftUpUsingComparator方法

在位置k处添加元素x，然后将x向上提升直至它大于或等于其父项或者根来维持堆不变

默认构建小顶堆

通过x实现的Comparator接口中的方法进行插入并调整排序

通过comparator进行插入并调整排序

清空queue的元素，容量不变，size=0

clear()

通过indexOf方法判断元素是否存在

如o为null则直接返回-1；如不为null，则遍历数组，通过o的equals方法判断是否相等

查询元素是否存在

indexOf(Object o)

获取堆的根，即queue的头元素

只会堆化索引size>>>1之前的元素，确保堆化后为完全二叉树，主要堆化方式为通过遍历调用siftDown方法

将queue数组中的元素堆化

heapify()

如comparator为空则调用siftDownComparable方法，反之则调用siftDownUsingComparator方法<br>

在位置k处添加元素x，然后将x向下降落直至它小于或等于其子项或叶子节点来维持跟不变

1.找到size节点的父节点

2.如k大于父节点索引，则直接queue[k]=x;如小于父节点索引，则

PriorityQueue

JavaUtil