1、动态数组
- 一、什么是数据结构❓
- 1、线性结构
- 2、树形结构
- 3、图形结构
- 二、线性表
- 三、数组（Array）
- 四、动态数组（Dynamic Array）
- 1、接口设计
- 2、动态数组的设计
- 3、查
- (1) size、isEmpty
- (2) indexOf、contains
- (3) get、checkIndex
- 4、增
- (1) 增加元素到尾部
- (2) 往索引位置添加元素
- (3) 扩容
- 5、打印数组
- 6、删
- (1) remove(int index)
- (2) 对象数组
- (3) clear
- 7、改
- 8、缩容
一、什么是数据结构❓
📕 数据结构是计算机存储、组织数据的方式
1、线性结构
🖊 线性表（数组、链表、栈、队列、哈希表）
2、树形结构
🖊 二叉树
🖊 AVL树
🖊 红黑树
🖊 B树
🖊 堆
🖊 Trie
🖊 哈夫曼树
🖊 并查集
3、图形结构
🖊 邻接矩阵
🖊 邻接表
二、线性表
📕 线性表是具有 n 个相同类型元素的有限序列（n ≥ 0）
🖊 a1 是首节点（首元素）， an 是尾节点（尾元素）
🖊 a1 是 a2 的前驱， a2 是 a1 的后继
🖊 常见的线性表有：
① 数组
② 链表
③ 栈
④ 队列
⑤ 哈希表（散列表）
三、数组（Array）
📕 数组是一种顺序存储的线性表，所有元素的内存地址是连续的
int[] array = new int[]{11, 22, 33};
🖊 数组缺点：
① 无法动态修改容量
② 操纵元素的方式不够面向对象
四、动态数组（Dynamic Array）
1、接口设计
public interface List<E> {
/**
* 返回存储的元素数量
*/
int size();
/**
* 是否为空
*/
boolean isEmpty();
/**
* 是否包含给定元素
*/
boolean contains(E element);
/**
* 返回索引位置的元素
*/
E get(int index);
/**
* 返回指定元素的索引
*/
int indexOf(E element);
/**
* 添加元素到尾部
*/
void add(E element);
/**
* 往索引位置添加元素
*/
void add(int index, E element);
/**
* 删除索引位置的元素
*
* @return 被删除的元素
*/
E remove(int index);
/**
* 清空所有元素
*/
void clear();
/**
* 设置索引位置的元素
*/
E set(int index, E element);
}
2、动态数组的设计
🖊 动态数组内部维护 size 成员变量，用于存储动态数组中元素的数量
🖊 动态数组内部维护 elements 成员变量，它存储着一个普通数组的内存地址
/**
* 动态数组
*/
public class ArrayList<E> {
public static final int DEFAULT_CAPACITY = 10;
private int size;
private E[] elements;
public ArrayList() {
this(DEFAULT_CAPACITY);
}
@SuppressWarnings("unchecked")
public ArrayList(int capacity) {
capacity = Math.max(capacity, DEFAULT_CAPACITY);
elements = (E[]) new Object[capacity];
}
}
3、查
(1) size、isEmpty
/**
* 返回存储的元素数量
*/
@Override
public int size() {
return size;
}
/**
* 是否为空
*/
@Override
public boolean isEmpty() {
return size == 0;
}
(2) indexOf、contains
/**
* 返回指定元素的索引
*/
@Override
public int indexOf(E element) {
if (element == null) {
for (int i = 0; i < size; i++) {
if (elements[i] == null) return i;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(elements[i])) return i;
}
}
return ELEMENT_NOT_FOUND;
}
👆 若给定的元素为 null，遍历 elements 数组的每个元素，若某个元素为 null，则返回该元素的索引
👆 若给定的元素不为 null，遍历 elements 数组的每个元素，用给定元素调用equals()方法和数组的每个元素比较，若 equals 方法返回 true，则返回当前元素的索引
👆 若整个 if-else 执行完毕后依然没有返回，则返回 ELEMENT_NOT_FOUND（实际是常量 -1）
/**
* 是否包含给定元素
*/
@Override
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
👆 若调用 indexOf 方法后返回值不为 ELEMENT_NOT_FOUND 则动态数组中包含给定元素
(3) get、checkIndex
private void checkIndex(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("index=" + index + ", size=" + size);
}
👆 检查参数索引 index 是否符合规范
👆 不符合则抛异常
/**
* 返回索引位置的元素
*/
@Override
public E get(int index) {
checkIndex(index);
return elements[index];
}
👆 直接通过给定索引返回 index 位置的元素
4、增
(1) 增加元素到尾部
🖊 添加元素到尾部：往数组的 size 位置添加元素
/**
* 添加元素到尾部
*/
@Override
public void add(E element) {
elements[size] = element;
size++;
}
(2) 往索引位置添加元素
🖊
add(int index, E element)接口的 index 可以等于 size
private void checkIndex4Add(int index) {
if (index < 0 || index > size)
throw new IllegalArgumentException("index=" + index + ", size=" + size);
}
🖊 把
[index, size-1]范围内的元素全部往后挪，把 index 位置空置出来【从size-1开始挪】
🖊 把 element 添加到 index 位置
/**
* 往索引位置添加元素
*/
@Override
public void add(int index, E element) {
checkIndex4Add(index);
// 把index位置空出来
for (int i = size - 1; i >= index; i--) {
elements[i + 1] = elements[i];
}
// 把element添加到index位置
elements[index] = element;
size++;
}
(3) 扩容
🖊 创建容量更大的新数组，把原来数组的元素复制到新数组中
🖊 elements 指向新数组
@SuppressWarnings("all")
private void ensureCapacity(int capacity) {
int oldCap = elements.length;
if (oldCap >= capacity) return; // 无需扩容
// 新容量为旧容量的1.5倍
int newCap = oldCap + (oldCap >> 1);
// 创建新数组
E[] newElements = (E[]) new Object[newCap];
// 把旧数组元素复制到新数组中
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}
5、打印数组
◼ 重写 toString 方法
◼ 在 toString 方法中将元素拼接成字符串
◼ 字符串拼接建议使用 StringBuilder
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("🖊size=").append(size).append(", [");
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
6、删
(1) remove(int index)
🖊 从
[index+1, size-1]范围内的元素全部往前赋值，覆盖掉 index 位置的元素
🖊size--
/**
* 删除索引位置的元素
*
* @return 被删除的元素
*/
@Override
public E remove(int index) {
checkIndex(index);
E old = elements[index];
// 覆盖
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
// 👇elements[--size] = null;
size--;
elements[size] = null;
return old;
}
(2) 对象数组
🖊 对象数组的每个元素存储的是对象的内存地址
(3) clear
🖊 把数组中的每个元素都设置为 null
🖊 size 成员变量设置为 0
/**
* 清空所有元素
*/
@Override
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
7、改
/**
* 设置索引位置的元素
*/
@Override
public E set(int index, E element) {
checkIndex(index);
E old = elements[index];
elements[index] = element;
return old;
}
8、缩容
◼ 如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作
◼ 比如剩余空间占总容量的一半时，就进行缩容
@SuppressWarnings("all")
private void trim() {
int curCap = elements.length;
int halfCap = curCap >> 1;
if (halfCap > size) {
E[] newElements = (E[]) new Object[halfCap];
// 把旧数组元素复制到新数组中
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
System.out.println("🖊缩容：" + curCap + "→" + halfCap);
}
}
🍀 该文章的完整代码
