Collection
2021-10-02 22:37:02 6 举报AI智能生成
java ArrayList源码
作者其他创作
大纲/内容
ArrayList
子类
AbstractList
子类
AbstractCollection
实现接口
Collection
Iterable
实现接口
List
Collection
Iterable
实现接口
List
Collection
Iterable
RandomAccess
arrayList中的元素可以随机访问
Cloneable
实现该接口时使实现Object类中的clone()方法合法，使实现clone()方法后对象的调用不会报错
Serializable
序列化接口，使数据序列化，如不给serialVersionUID赋值则会默认赋值，但更新类中的内容时serialVersionUID会重新赋值，此时会影响对象的反序列化，因此建议给serialVersionUID赋值
属性
DEFAULT_CAPACITY
ArrayList默认初始化容量为10，如超过最大容量时，ArrayList会通过grow()方法动态扩容
EMPTY_ELEMENTDATA
空Object数组，非空构造器时使用
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
空Object数组,空构造器时使用
elementData
Object数组，存储ArrayList元素
MAX_ARRAY_SIZE
数组最大容量
Integer.MAX_VALUE-8
size
当前数组大小
方法
构造器
ArrayList()
初始化DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组
ArrayList(int initialCapacity)
初始化initialCapacity大小的数组
initialCapacity大于0，则直接初始化initialCapacity大小的Object[];如initialCapacity等于0，则初始化为EMPTY_ELEMENTDATA空数组；如EMPTY_ELEMENTDATA小于0，则会报错
ArrayList(Collection<? extends E> c)
初始化集合数组
如果集合为空集合，则初始化为EMPTY_ELEMENTDATA空数组；如集合不为空，先判断集合是否为ArrayList,如为ArrayList，则直接将c的array赋值为elementData，如不为ArrayList，则初始化与集合c相同容量的数组
主要方法
add(E e)
添加元素，对size+1进行扩容处理。扩容完毕后，size++，将elementData[size++]设置为添加的元素
add(int index, E element)
指定位置添加元素，先判断位置是否合法，然后对size+1进行扩容处理，然后通过System.arrayCopy(elementData,index,elementData,index+1,size-index)方法赋值元素，最后设置index位置元素为添加元素
clone()
浅克隆
contains(Object o)
判断是否包含某个元素，如o为null，则直接遍历elementData数组是否存在null；如o不为null，则通过o的equal()方法进行遍历判断是否相等
remove(int index)
删除指定位置的元素，首先进行index合法判断；如合法通过System.arrayCopy(elementData,index+1,elementData,index,size-index-1)对数组进行移动，最后将elementData最后一位置为null，并size--
subList(int fromIndex, int toIndex)
截取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大小
LinkedList
子类
AbstractSequentialList
子类
AbstractList
子类
AbstractCollection
实现接口
Collection
Iterable
实现接口
List
Collection
Iterable
实现接口
List
Collection
Iterable
Deque
Queue
Collection
Iterable
Cloneable
实现此接口时，重写Object的clone()方法后调用此方法时不会报错
Serializable
实现此接口时，可将对象序列化
属性
transient Node<E> first
链表首节点，transient关键字表示该属性不会被序列化，使对象只会存在在调用者内存中，而不会持久化
transient Node<E> last
链表尾节点
transient int size = 0
链表当前容量
方法
构造器
LinkedList()
空参构造器
LinkedList(Collection<? extends E> c)
调用addAll(Collection<? extends E> c)方法添加集合
主要方法
add(E e)
添加元素，调用linkLast(E e)方法从最后添加元素，注意判断last是否为null，如为null需更新first的信息，最后更新last的信息和size++
contains(Object o)
判断是否包含元素
如o为null，则从first开始遍历所有节点，判断是否有null节点；如不为null，则从first开始遍历所有节点，通过o的equal()方法判断是否相等
element()
获取链表头节点
如头节点为空，则报错
get(int index)
获取指定位置的节点
如节点位置大于size的一半，则会从last遍历到节点；如小于size的一半，则会从first遍历到节点
offer(E e)
添加元素到链表末尾
peek()
取出头节点的值
poll()
取出头节点，并在链表中去除头节点
pop()
取出头节点，并在链表中去除头节点
push(E e)
从头节点处添加元素
remove()
删除头节点，并返回头节点
set(int index, E element)
更新index位置的节点值，并返回原来的值
内部类
Node
属性
item
preNode
nextNode
构造器
Node(Node<E> prev, E element, Node<E> next)
PriorityQueue
介绍
优先级队列，基于优先级堆，队列的长度是无限的，实现方式为Object数组，数组拥有默认容量，如超过默认容量需进行扩容，队列中的元素不能为null
子类
AbstractQueue
子类
AbstractCollection
实现接口
Collection
Iterable
实现接口
Queue
Collection
Iterable
实现接口
Serializable
属性
Comparator<? super E> comparator
默认的Comparator
DEFAULT_INITIAL_CAPACITY = 11
默认容量
MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
最大容量
modCount = 0
队列结构修改次数
Object[] queue
队列实现数组
size = 0
队列当前元素数量
方法
构造器
PriorityQueue()
空参构造器
初始化队列容量为DEFAULT_INITIAL_CAPACITY，comparator为null
PriorityQueue(int initialCapacity)
初始化队列容量为initialCapacity，comparator为null
PriorityQueue(Comparator<? super E> comparator)
初始化队列容量为DEFAULT_INITIAL_CAPACITY，comparator为参数comparator
PriorityQueue(int initialCapacity,
Comparator<? super E> comparator)
Comparator<? super E> comparator)
初始化队列容量为initialCapacity，comparator为参数comparator
PriorityQueue(PriorityQueue<? extends E> c)
初始化comparator为c的comparator，然后通过initFromPriorityQueue初始化queue和size
PriorityQueue(SortedSet<? extends E> c)
初始化comparator为c的comparator，然后通过initElementsFromCollection方法初始化queue和size
主要方法
add(E e)
添加元素，通过offer方法添加元素
offer(E e)
添加元素至queue
1.判断size+1是否大于queue的length，如大于则通过grow方法进行扩容
2.如size==0，则直queue[0]=e，如不等于0，则通过siftUp方法添加元素
grow(int minCapacity)
数组queue的扩容
如果原来数组的容量小于64，则新增容量为原容量+2；如大于等于64，则新增容量为原容量的一半
siftUp(int k, E x)
在位置k处添加元素x，然后将x向上提升直至它大于或等于其父项或者根来维持堆不变
如comparator为空则调用siftUpComparable方法，反之则调用siftUpUsingComparator方法
siftUpComparable(int k, E x)
通过x实现的Comparator接口中的方法进行插入并调整排序
默认构建小顶堆
siftUpUsingComparator(int k, E x)
通过comparator进行插入并调整排序
默认构建小顶堆
clear()
清空queue的元素，容量不变，size=0
contains(Object o)
通过indexOf方法判断元素是否存在
indexOf(Object o)
查询元素是否存在
如o为null则直接返回-1；如不为null，则遍历数组，通过o的equals方法判断是否相等
peek()
获取堆的根，即queue的头元素
heapify()
将queue数组中的元素堆化
只会堆化索引size>>>1之前的元素，确保堆化后为完全二叉树，主要堆化方式为通过遍历调用siftDown方法
siftDown(int k, E x)
在位置k处添加元素x，然后将x向下降落直至它小于或等于其子项或叶子节点来维持跟不变
如comparator为空则调用siftDownComparable方法，反之则调用siftDownUsingComparator方法<br>
siftDownComparable(int k, E x)
通过x实现的Comparator接口中的方法进行插入并调整排序
1.找到size节点的父节点
2.如k大于父节点索引，则直接queue[k]=x;如小于父节点索引，则
siftDownUsingComparator(int k, E x)
通过comparator进行插入并调整排序
poll()
收藏
0 条评论
下一页
