当前位置:网站首页>Source code analysis of ArrayList
Source code analysis of ArrayList
2022-07-07 14:22:00 【LLAiden】
Preface
ArrayList It is a very common data storage class , In this article, we will learn about ArrayList The internal data structure of , Start with the constructor
structure
ArrayList<Object> arrayList1 = new ArrayList<>();
ArrayList<Object> arrayList2 = new ArrayList<>(10);
ArrayList<Object> arrayList3 = new ArrayList<>(arrayList1);
Here is ArrayList Let's look down one by one at the three constructors of the source code
First, post the source code of the above parameter structure
transient Object[] elementData; // non-private to simplify nested class access
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
It can be seen from the empty parameter structure ArrayList Array is used to store data , Just because we didn't add data here, we used one length by 0 Array of
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
This is a single parameter construction , You need to pass in the container length , An array will be created according to this length to store the data , Of course, this length is not fixed , When the maximum capacity is reached, we will see .
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
// notes 1
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
// notes 2
elementData = a;
} else {
// notes 3
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
notes 1: take arrayList Of size The variable is set to the length of the passed array , After that, add data from this size++;
notes 2: If it's delivered ArrayList Just the one that will be delivered directly arrayList The array in is assigned to the current arrayList
notes 3: Yes, it will come in Collection Data in the array in copy To a new data and point this new data to the current ArrayList Medium elementData
Let's take a look ArrayList Addition, deletion and modification of
increase
public boolean add(E e) {
// This variable is mainly used to add or delete in iterators
// Making it not throw exceptions is not the focus we need to grasp this time, which can be ignored for the time being
modCount++;
add(e, elementData, size);
return true;
}
// Really add
private void add(E e, Object[] elementData, int s) {
// When s == elementData.length It means that the current data storage is full and needs to be expanded
if (s == elementData.length)
elementData = grow();
// Add data to the last digit
elementData[s] = e;
// After storing data , Maintenance of size+1
size = s + 1;
}
// Capacity expansion
private Object[] grow() {
return grow(size + 1);
}
// The concrete implementation of expansion
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
// notes 1
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// notes 2
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
// notes 3
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
// notes 4
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
Let's focus on what the expansion function does
notes 1: Judge whether it is currently constructed with null parameters ArrayList And the data has not been added. If yes, it will be executed back to the comment 4
notes 2: Here is to calculate the length to be expanded , This expansion rule is to expand the capacity at least 1, Usually, the capacity is expanded to the previous capacity 1.5 times
notes 3: Here is the data in the previous array copy In the new array and points to the new array
notes 4: This line of code will arrayList Expand the array in to 10 The length of
Adding data at a specified location is also a common method , Go straight to source
public void add(int index, E element) {
// Check whether the position to be inserted is legal
// If at present size = 10, The location of the data to be inserted is 11 At this time, it is illegal to throw an exception
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
// Determine whether capacity expansion is needed
// Join in ArrayList Of Size = 10, In this function index Also equal to 10 At this time, we need to expand the capacity
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
// notes 1
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
// Add data to the specified location
elementData[index] = element;
size = s + 1;
}
Let's focus on the notes 1
Insert data at specified location , The witty little friend will think whether the data of the original location has been covered , Seeing this line of code, I believe you have a clear idea
Here we will start with the incoming subscript ,size Move back a position after finishing the data to make index The position is empty for new data to be inserted .
Delete
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
There are two ways to delete , Method 1 Delete for the specified object , Compare whether the objects are equal by traversal. If they are equal, set the data of this position null Operate and move the subsequent data one bit forward , And set the last data to null And size -1
The second method is to directly set the corresponding position to null, And move the subsequent data forward one bit , And set the last data to null And size -1
modify
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
It is simpler to modify. Set the element at the specified position as a new element without moving other elements
Inquire about
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
The query operation is to judge whether the subscript of the data to be retrieved is legal , If it goes beyond size -1 Throw out
outOfBoundsCheckIndex, If it is legal, take out the data directly through subscript
summary
In the source code, we see ArrayList Add, delete, and modify the operations done in the query , We will find that intermediate insertion or deletion of data will trigger the operation of data displacement , Adding a lot of data will make ArrayList Frequent capacity expansion operations will have an impact on performance , Therefore, we should try to avoid using ArrayList
边栏推荐
- Parameter keywords final, flags, internal, mapping keywords internal
- C # use TCP protocol to establish connection
- Equipment failure prediction machine failure early warning mechanical equipment vibration monitoring machine failure early warning CNC vibration wireless monitoring equipment abnormal early warning
- requires php ~7.1 -&gt; your PHP version (7.0.18) does not satisfy that requirement
- 设备故障预测机床故障提前预警机械设备振动监测机床故障预警CNC震动无线监控设备异常提前预警
- Environment configuration of lavarel env
- NLLB-200:Meta开源新模型,可互译200种语言
- CSMA/CD 载波监听多点接入/碰撞检测协议
- 請問,在使用flink sql sink數據到kafka的時候出現執行成功,但是kafka裏面沒有數
- Huawei image address
猜你喜欢
内部排序——插入排序
[Reading stereo matching papers] [III] ints
libSGM的horizontal_path_aggregation程序解读
The longest ascending subsequence model acwing 482 Chorus formation
PERT图(工程网络图)
AutoCAD - how to input angle dimensions and CAD diameter symbols greater than 180 degrees?
AI talent cultivation new ideas, this live broadcast has what you care about
Advanced Mathematics - Chapter 8 differential calculus of multivariate functions 1
Use case diagram
Reverse non return to zero code, Manchester code and differential Manchester code of common digital signal coding
随机推荐
Did login metamask
Search engine interface
Attribute keywords aliases, calculated, cardinality, ClientName
JS get the current time, month, day, year, and the uniapp location applet opens the map to select the location
wpf dataGrid 实现单行某个数据变化 ui 界面随之响应
Flask session forged hctf admin
Use case diagram
Leetcode - Sword finger offer 05 Replace spaces
搜索引擎接口
Vmware共享主机的有线网络IP地址
请问指南针股票软件可靠吗?交易股票安全吗?
UML 顺序图(时序图)
PERT图(工程网络图)
c#通过frame 和 page 切换页面
The longest ascending subsequence model acwing 1012 Sister cities
C # switch pages through frame and page
数据流图,数据字典
libSGM的horizontal_path_aggregation程序解读
requires php ~7.1 -&gt; your PHP version (7.0.18) does not satisfy that requirement
Pert diagram (engineering network diagram)