作者:小傅哥 博客:https://bugstack.cn
❝沉淀、分享、成长,让自己和他人都能有所收获!😜 ❞
数组是数据结构还是数据类型?
数组只是个名称,它可以描述一组操作,也可以命名这组操作。数组的数据操作,是通过 idx->val 的方式来处理。它不是具体要求内存上要存储着连续的数据才叫数据,而是说,通过连续的索引 idx,也可以线性访问相邻的数据。
那么当你定义了数据的存储方式,也就定义了数据结构。所以它也是被归类为数据结构。
数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型数据的集合。
数组的特点:
一维数组是最常用的数组,其他很多数据结构的变种也都是从一维数组来的。例如 HashMap 的拉链寻址结构,ThreadLocal 的开放寻址结构,都是从一维数组上实现的。
二维以及多维数组,在开发场景中使用到的到不是不多,不过在一些算法逻辑,数学计算中到是可以使用。
在 Java 的源码中,数组是一个非常常用的数据结构,很多其他数据结构也都有数组的影子。在一些数据存放和使用的场景中,基本也都是使用 ArrayList 而不是 LinkedList,具体性能分析参考:LinkedList插入速度比ArrayList快?你确定吗?
那么本章节我们就借着数组结构的学习,实现一个简单的 ArrayList,让使用 Java 的读者既能了解学习数据结构,也能了解到 Java 源码实现。
Java 算法与数据结构
数组是一个固定的、连续的、线性的数据结构,那么想把它作为一个自动扩展容量的数组列表,则需要做一些扩展。
/**
* 默认初始化空间
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空元素
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* ArrayList 元素数组缓存区
*/
transient Object[] elementData;
public boolean add(E e) {
// 确保内部容量
int minCapacity = size + 1;
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 判断扩容操作
if (minCapacity - elementData.length > 0) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 添加元素
elementData[size++] = e;
return true;
}
这是一份简化后的 ArrayList#add 操作
ArrayList 的重点离不开对 System.arraycopy 的使用,它是一个本地方法,可以让你从原数组的特定位置,迁移到新数组的指定位置和迁移数量。如图 2-5 所示,数据迁移 测试代码在 java-algorithms
删除元素
public E remove(int index) {
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0) {
// 从原始数组的某个位置,拷贝到目标对象的某个位置开始后n个元素
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public E get(int index) {
return (E) elementData[index];
}
@Override
public String toString() {
return "ArrayList{" +
"elementData=" + Arrays.toString(elementData) +
", size=" + size +
'}';
}
@Test
public void test_array_list() {
cn.bugstack.algorithms.data.array.List<String> list = new ArrayList<>();
list.add("01");
list.add("02");
list.add("03");
list.add("04");
list.add("05");
list.add("06");
list.add("07");
list.add("08");
list.add("09");
list.add("10");
list.add("11");
list.add("12");
System.out.println(list);
list.remove(9);
System.out.println(list);
}
测试结果
ArrayList{elementData=[01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, null, null, null], size=12}
ArrayList{elementData=[01, 02, 03, 04, 05, 06, 07, 08, 09, 11, 12, null, null, null, null], size=11}
Process finished with exit code 0
- END -
你好,我是小傅哥。一线互联网java
工程师、T8架构师,开发过交易&营销、写过运营&活动、设计过中间件也倒腾过中继器、IO板卡。不只是写Java语言,也搞过C#、PHP,是一个技术活跃的折腾者。