数据结构之数组
本文最后更新于 2024-12-16，文章内容可能已经过时。
数组是一种线性表数据结构，使用一段连续的内存空间来存储一组具有相同类型的数据。这种特性使得数组能够支持高效的随机访问，即可以根据索引直接计算出元素的地址并访问之，时间复杂度为O(1)。
一、基本概念
- 数组索引：每个元素都有一个唯一的整数索引，从0开始计数(C、JAVA等)，用于访问数组中的元素。
- 数组元素：数组中的所有元素必须是相同类型的数据，可以是基本数据类型如整数、浮点数等，也可以是指向对象的引用。
- 数组长度：指的是数组中包含的元素数量。
由于数组在内存中是连续存储的，因此可以通过索引快速定位到任何一个元素的位置。此外，数组还支持多种操作，包括但不限于插入、删除、修改和查找等。
二、固定数组
数组的长度在创建时是固定的，一旦初始化后，其大小不可改变。
int[] array = {1,2,3,4,5}
知道了数组的数据起始地址Address,就可以由公式Address + i * size计算出索引 i元素的地址
- i即索引，在 Java、C 等语言都是从 0 开始
- size是每个元素占用字节，如int为4，double为8
byte[] array = {1,2,3,4,5}
已知 array 的数据的起始地址是 0x7138f94ca，那么元素 3 的地址是什么？
0x7138f94ca + 2 * 1 = 0x7138f94cc
Ⅰ、空间占用
在HotSpot JVM中，对象的大小通常会被填充到8字节（64位系统）或4字节（32位系统）的倍数，这是因为内存对齐（memory alignment）的原因。内存对齐是为了确保数据结构（如对象）按照一定的边界存储在内存中，这样可以优化CPU访问内存的速度。
具体来说，在HotSpot JVM中：
- 32位系统：对象大小会被填充到4字节的倍数。
- 64位系统：默认情况下，对象大小会被填充到8字节的倍数。
但是，这并不意味着所有对象的原始大小本身就是8字节的倍数。实际的对象大小由对象头、实例变量以及可能的数组元素决定，而这些部分的总和可能不是8字节的整数倍。JVM通过添加必要的填充字节来使最终对象的大小符合内存对齐的要求。
需要注意的是，虽然HotSpot倾向于使用8字节对齐（在64位系统上），但这并不是一个绝对规则，并且可以通过JVM参数进行调整。例如，-XX:ObjectAlignmentInBytes 参数可以用来设置对象的对齐大小，默认值是8。
因此，总结来说，在HotSpot JVM中，为了优化内存访问性能，对象的最终大小通常会被调整为8字节的整数倍（对于64位系统），但这并不反映对象本身的实际大小需求，而是包含了额外的填充以满足内存对齐的要求。
Java 中数组结构为
- 8 字节 markword
- 4 字节 class 指针（压缩 class 指针的情况）
- 4 字节 数组大小（决定了数组最大容量是 2^{32}）
- 数组元素 + 对齐字节（
java中所有对象大小都是 8 字节的整数倍，不足的要用对齐字节补足）
int[] array = {1, 2, 3, 4, 5};
的大小为 40 个字节，组成如下8 + 4 + 4 + 5*4 + 4(alignment)
Ⅱ、插入或删除性能
头部位置，时间复杂度是 O(n)
中间位置，时间复杂度是 O(n)
尾部位置，时间复杂度是 O(1)
Ⅲ、缺点
- 固定大小：一旦创建了数组，其大小就不可改变。如果需要存储更多的元素，则必须创建一个新的更大的数组，并将旧数组的元素复制到新数组中。
- 类型限制：虽然数组可以存储多个元素，但这些元素都必须是相同的数据类型。如果你想在一个数组中存储不同类型的对象，那么你只能使用它们的公共父类或者接口来声明数组，但这会导致类型转换的麻烦和潜在的风险。
- 不支持复杂操作：与更高级别的集合类相比（如
ArrayList、LinkedList等），数组提供的功能较为有限，例如缺乏内置的添加、删除元素的方法，查找元素的便捷方法等。 - 初始化繁琐：对于大型数组，初始化所有元素可能会变得非常繁琐。而一些集合框架则提供了更加简便的方式来进行批量操作。
- 内存浪费：如果你事先不确定要存储多少数据，而只是基于估计创建了一个较大容量的数组，那么未使用的空间就会造成内存浪费。
- 多维数组的实际表现：在Java中，多维数组实际上是数组的数组。这可能使得某些操作效率低下，并且增加了代码的复杂度。
- 缺少泛型的支持：尽管Java 5引入了泛型，但是数组并不完全支持泛型。比如，你不能创建一个泛型类型的数组，像
new ArrayList<T>[size]这样的语句是非法的。 - 线程安全性问题：数组本身不是线程安全的。当多个线程同时访问和修改数组中的元素时，可能会导致数据不一致的问题。
三、动态数组
Java中的动态数组是一种可以自动调整大小的数据结构，它允许程序员在程序运行期间根据需要添加或删除元素。与静态数组不同，动态数组不需要在创建时就确定其大小，并且可以在运行时动态地增长或缩小。这种灵活性使得动态数组非常适合处理未知数量的数据集合。
在Java中，最常用的动态数组实现是ArrayList类，它是java.util包的一部分。ArrayList不仅实现了动态调整大小的功能，还提供了许多方便的方法来操作其中的元素，例如添加、删除、查找等。此外，ArrayList实现了List接口，这意味着它可以与其他使用List接口的API兼容。
Ⅰ、特点
- 动态大小：
ArrayList的大小可以在运行时改变，这是它与静态数组（即固定大小的数组）的主要区别。 - 随机访问：可以通过索引直接访问
ArrayList中的任何元素，访问速度非常快（O(1)时间复杂度）。 - 插入和删除：在
ArrayList末端插入或删除元素通常很快（O(1)），但在中间或开始位置插入或删除元素则需要移动元素，速度较慢（O(n)）。
Ⅱ、自己实现
import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;
/**
* 动态数组
*/
public class DIntArray implements Iterable<Integer> {
private int size = 0; // 当前数组大小
private int capacity = 10; // 容量
private int[] array = {};
public int[] array() {
return Arrays.copyOf(array, size);
}
public DIntArray() {}
public DIntArray(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("Capacity must be a positive integer");
}
this.capacity = capacity;
}
/**
* 向最后位置 [size] 添加元素
*
* @param element 待添加元素
*/
public void addLast(int element) {
// array[size] = element;
// size++;
add(size, element);
}
/**
* 向 [0 .. size] 位置添加元素
*
* @param index 索引位置
* @param element 待添加元素
*/
public void add(int index, int element) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
checkAndGrow();
// 添加逻辑
if (index >= 0 && index < size) {
// 向后挪动, 空出待插入位置
System.arraycopy(array, index, array, index + 1, size - index);
}
array[index] = element;
size++;
}
private void checkAndGrow() {
// 容量检查
if (size == 0) {
array = new int[capacity];
} else if (size == capacity) {
// 进行扩容, 1.5
capacity += capacity >> 1;
int[] newArray = new int[capacity];
System.arraycopy(array, 0,
newArray, 0, size);
array = newArray;
}
}
/**
* 从 [0 .. size) 范围删除元素
*
* @param index 索引位置
* @return 被删除元素
*/
public int remove(int index) { // [0..size)
if (index > size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
int removed = array[index];
if (index < size - 1) {
// 向前挪动
System.arraycopy(array, index + 1, array, index, size - index - 1);
}
size--;
return removed;
}
/**
* 查询元素
*
* @param index 索引位置, 在 [0..size) 区间内
* @return 该索引位置的元素
*/
public int get(int index) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
return array[index];
}
/**
* 遍历方法1
*
* @param consumer 遍历要执行的操作, 入参: 每个元素
*/
public void foreach(Consumer<Integer> consumer) {
for (int i = 0; i < size; i++) {
// 提供 array[i]
// 返回 void
consumer.accept(array[i]);
}
}
/**
* 遍历方法2 - 迭代器遍历
*/
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
int cursor = 0;
@Override
public boolean hasNext() { // 有没有下一个元素
return cursor < size;
}
@Override
public Integer next() { // 返回当前元素,并移动到下一个元素
return array[cursor++];
}
};
}
/**
* 遍历方法3 - stream 遍历
*
* @return stream 流
*/
public IntStream stream() {
return IntStream.of(array());
}
}
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;
import static org.junit.jupiter.api.Assertions.*;
public class DArrayTest {
@Test
@DisplayName("测试添加")
public void test1() {
DIntArray dIntArray = new DIntArray();
dIntArray.addLast(1);
dIntArray.addLast(2);
dIntArray.addLast(3);
dIntArray.addLast(4);
// dynamicArray.addLast(5);
dIntArray.add(2, 5);
dIntArray.add(2, 6);
assertEquals(1, dIntArray.get(0));
assertEquals(2, dIntArray.get(1));
assertEquals(6, dIntArray.get(2));
assertEquals(5, dIntArray.get(3));
assertEquals(3, dIntArray.get(4));
assertEquals(4, dIntArray.get(5));
}
@Test
@DisplayName("测试遍历1")
public void test2() {
DIntArray dIntArray = new DIntArray();
dIntArray.addLast(1);
dIntArray.addLast(2);
dIntArray.addLast(3);
dIntArray.addLast(4);
dIntArray.add(2, 5);
dIntArray.add(2, 6);
ResultCollector consumer = new ResultCollector();
dIntArray.foreach(consumer);
consumer.test(List.of(1, 2, 6, 5, 3, 4));
}
static class ResultCollector implements Consumer<Integer> {
List<Integer> list = new ArrayList<>();
public void accept(Integer element) {
list.add(element);
}
public void test(List<Integer> expected) {
assertIterableEquals(expected, list);
}
}
@Test
@DisplayName("测试遍历2")
public void test3() {
DIntArray dIntArray = new DIntArray();
dIntArray.addLast(1);
dIntArray.addLast(2);
dIntArray.addLast(3);
dIntArray.addLast(4);
assertIterableEquals(List.of(1, 2, 3, 4), dIntArray);
}
@Test
@DisplayName("测试遍历3")
public void test4() {
DIntArray dIntArray = new DIntArray();
dIntArray.addLast(1);
dIntArray.addLast(2);
dIntArray.addLast(3);
dIntArray.addLast(4);
assertArrayEquals(new int[]{1, 2, 3, 4},
dIntArray.stream().toArray());
}
@Test
@DisplayName("测试删除")
public void test5() {
DIntArray dIntArray = new DIntArray();
dIntArray.addLast(1);
dIntArray.addLast(2);
dIntArray.addLast(3);
dIntArray.addLast(4);
dIntArray.addLast(5);
int removed = dIntArray.remove(4);
assertEquals(5, removed);
assertIterableEquals(List.of(1, 2, 3, 4), dIntArray);
}
@Test
@DisplayName("测试扩容")
public void test6() {
DIntArray dIntArray = new DIntArray();
for (int i = 0; i < 12; i++) {
dIntArray.addLast(i + 1);
}
int i = 4 >> 1;
int ii = 4 >>> 1;
System.out.println("i = " + i);
System.out.println("ii = " + ii);
assertIterableEquals(
List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12),
dIntArray
);
}
}
[INFO] -------------------------------------------------------
[INFO] T E S T S
[INFO] -------------------------------------------------------
[INFO] Running com.nn3n.BinarySearchTest
[INFO] Tests run: 9, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.063 s -- in com.nn3n.BinarySearchTest
[INFO] Running com.nn3n.DArrayTest
i = 2
ii = 2
[INFO] Tests run: 6, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.016 s -- in com.nn3n.DArrayTest
[INFO]
[INFO] Results:
[INFO]
[INFO] Tests run: 15, Failures: 0, Errors: 0, Skipped: 0
[INFO]
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time: 1.749 s
[INFO] Finished at: 2024-12-16T11:23:06+08:00
[INFO] ------------------------------------------------------------------------
Ⅲ、优点与缺点
尽管ArrayList提供了极大的灵活性，但也有它的局限性。一方面，它支持高效的随机访问和快速地在尾部进行增删操作；另一方面，在数组中间进行插入或删除操作效率较低，因为这涉及到大量元素的移动。此外，由于每次扩容都需要重新分配内存并复制所有元素，所以在频繁增删元素的情况下可能会产生额外开销。
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
