JavaEE
鸿蒙应用开发
HTML&JS+前端
Python+大数据开发
人工智能开发
电商视觉设计
软件测试
新媒体+短视频
集成电路应用开发
C/C++
狂野架构师
IP短视频
ArrayList集合源码分析【java培训】
更新时间:2020年07月08日16时46分 来源:传智播客 浏览次数:
1、数据结构特点
(1)DEFAULT_CAPACITY：表示数组的初始大小，默认10
(2)size: 表示当前数组的大小
(3)modCount: 统计当前数组元素被修改的次数,只要修改,就+1
//实际大小为{},长度为0的数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
说明: ArrayList无参构造方法初始化时,默认大小是空数组,并不是大家常说的10,
10是在第一次add的时候扩容的数组容量值.
//确保数组大小是否足够,不够执行扩容,size为当前数组的大小
ensureCapacityInternal(size + 1); // Increments modCount!!
//直接把元素e保存到数组中
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) {
//在最小容量minCapacity和DEFAULT_CAPACITY(10)选择一个较大的值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
//记录修改次数
modCount++;
//如果我们期望的最小容量>数组目前的长度就扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//oldCapacity >> 1: 是把oldCapacity/2的意思
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容后的值<我们期望的值,扩容后的值等于我们期望的值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果扩容后的值>jvm所能分配的数组的最大值,那么就用Integer的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//通过复制数组扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
注意:
1.扩容的规则并不是翻倍，是原来容量大小的1.5倍
2.ArrayList中数组的最大长度是Integer.MAX_VALUE,超过这个值,JVM就不会给数组分配内存空间了
3.新增元素时，并没有对值进行严格的校验，所以ArrayList是允许null值的
(2)first是双向链表的头节点,它的前一个节点是null
(3)last是双向链表的尾节点,它的后一个节点是null
(4)链表中如果没有数据,first和last都null
(5)因为是双向链表,只要内存空间足够大,链表的大小是没有限制的
{
E item;//节点数据
Node next;//下一个节点的地址
Node prev;//前一个节点的地址
//初始化参数顺序是: 前一个节点地址,节点本身的数据,后一个节点地址
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
linkLast(e);
return true;//链表节点数据可以重复,所以add方法始终返回true
} //从尾部添加节点
void linkLast(E e) {
//把尾节点地址存储在l中
final Node l = last;
//创建新的节点,参数含义如下
//l是新节点的前一个节点的地址,当前值是尾节点地址值
//e是当前新增节点中保存的数据,当前新增节点的下一个节点是null,因为是在末尾添加
final Node newNode = new Node<>(l, e, null);
//last指向新增节点(新增节点作为尾节点)
last = newNode;
//如果链表为空(第一次添加节点)(l是尾节点,尾节点为空,链表即空),头部和尾部都是指向同一个节点,都是新建的节点
if (l == null)
first = newNode;
else
//链表不是空(非第一次添加节点),把添加新节点之前的尾节点的下一个节点指向新添加的节点
l.next = newNode;
//节点数+1
size++;
//链表的实际修改次数+1
modCount++;
}
checkElementIndex(index);//检查索引值是否越界
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
核心根据索引获取节点数据的方法
链表查询某个节点是比较慢的，需要挨个查找才可以 根据链表索引位置查询元素
Node node(int index) {
//如果index处于链表的前半部分,从头开始查,size>>1 是 size/2的意思
if (index < (size >> 1)) {
Node x = first;
//知道for循环到index的前一个node停止
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//如果index处于链表的后半部分,从尾开始查
Node x = last;
//知道for循环到index的后一个node停止
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
从源码中发现,LinkedList并没有采用从头循环到尾的做法，而是采取了简单二分查找法，首先看index是在链表的左半部分还是右半部分。如果是在左半部分,就从左侧开始找，如果实在链表的有伴部分，就从右侧开始找。这种方式,循环的次数至少降低了一半，提高查询性能。
猜你喜欢：
ArrayList底层数据结构是一个数组,查询元素速度快,增删速度稍慢
2、几个概念:(1)DEFAULT_CAPACITY：表示数组的初始大小，默认10
(2)size: 表示当前数组的大小
(3)modCount: 统计当前数组元素被修改的次数,只要修改,就+1
3.空参构造方法初始化
public ArrayList() {//实际大小为{},长度为0的数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
说明: ArrayList无参构造方法初始化时,默认大小是空数组,并不是大家常说的10,
10是在第一次add的时候扩容的数组容量值.
4、第一次添加元素扩容原理
public boolean add(E e) {//确保数组大小是否足够,不够执行扩容,size为当前数组的大小
ensureCapacityInternal(size + 1); // Increments modCount!!
//直接把元素e保存到数组中
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) {
//在最小容量minCapacity和DEFAULT_CAPACITY(10)选择一个较大的值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
//记录修改次数
modCount++;
//如果我们期望的最小容量>数组目前的长度就扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//oldCapacity >> 1: 是把oldCapacity/2的意思
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容后的值<我们期望的值,扩容后的值等于我们期望的值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果扩容后的值>jvm所能分配的数组的最大值,那么就用Integer的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//通过复制数组扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
注意:
1.扩容的规则并不是翻倍，是原来容量大小的1.5倍
2.ArrayList中数组的最大长度是Integer.MAX_VALUE,超过这个值,JVM就不会给数组分配内存空间了
3.新增元素时，并没有对值进行严格的校验，所以ArrayList是允许null值的
LinkeList集合
1.数据结构特点:
LinkedList底层数据结构是一个双向链表,链表中的每个节点都可以查找前一个节点或者向后查找后一个节点
2.几个概念:
(1)链表每个节点叫做Node,Node有prev属性,代表前一个节点的地址,next属性代表后一个节点的地址(2)first是双向链表的头节点,它的前一个节点是null
(3)last是双向链表的尾节点,它的后一个节点是null
(4)链表中如果没有数据,first和last都null
(5)因为是双向链表,只要内存空间足够大,链表的大小是没有限制的
3.链表中的元素(节点)叫做Node,是LinkedList集合的私有静态内部类，代码如下:
private static class NodeE item;//节点数据
Node
Node
//初始化参数顺序是: 前一个节点地址,节点本身的数据,后一个节点地址
Node(Node
this.item = element;
this.next = next;
this.prev = prev;
}
}
4.add添加节点(从链表尾部添加)
public boolean add(E e) {linkLast(e);
return true;//链表节点数据可以重复,所以add方法始终返回true
} //从尾部添加节点
void linkLast(E e) {
//把尾节点地址存储在l中
final Node
//创建新的节点,参数含义如下
//l是新节点的前一个节点的地址,当前值是尾节点地址值
//e是当前新增节点中保存的数据,当前新增节点的下一个节点是null,因为是在末尾添加
final Node
//last指向新增节点(新增节点作为尾节点)
last = newNode;
//如果链表为空(第一次添加节点)(l是尾节点,尾节点为空,链表即空),头部和尾部都是指向同一个节点,都是新建的节点
if (l == null)
first = newNode;
else
//链表不是空(非第一次添加节点),把添加新节点之前的尾节点的下一个节点指向新添加的节点
l.next = newNode;
//节点数+1
size++;
//链表的实际修改次数+1
modCount++;
}
5.get(int index)查询节点
public E get(int index) {checkElementIndex(index);//检查索引值是否越界
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
核心根据索引获取节点数据的方法
链表查询某个节点是比较慢的，需要挨个查找才可以 根据链表索引位置查询元素
Node
//如果index处于链表的前半部分,从头开始查,size>>1 是 size/2的意思
if (index < (size >> 1)) {
Node
//知道for循环到index的前一个node停止
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//如果index处于链表的后半部分,从尾开始查
Node
//知道for循环到index的后一个node停止
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
从源码中发现,LinkedList并没有采用从头循环到尾的做法，而是采取了简单二分查找法，首先看index是在链表的左半部分还是右半部分。如果是在左半部分,就从左侧开始找，如果实在链表的有伴部分，就从右侧开始找。这种方式,循环的次数至少降低了一半，提高查询性能。
猜你喜欢：
最新资讯
0
分享到：
江苏传智播客教育科技股份有限公司 版权所有Copyright 2006-2024 All Rights Reserved 苏ICP备16007882号营业执照增值电信业务经营许可证出版物经营许可证
苏公网安备 32132202001156号