学习李明杰老师的恋上数据结构笔记
一、 数组
数组是一种顺序存储的线性表，所有元素的内存地址都是连续的。
int[] array = new int[]{11, 22, 33}
在很多编程语言中，数组有个致命的缺点， 无法动态修改容量。实际开发中我们希望数组的容量是动态变化的。
二、动态数组（Dynamic Array）接口设计
- 创建
ArrayList类
public class ArrayList<E> {
private int size; // 管理数组中元素的个数
private E[] elements; // 管理存取的数据
// 元素的数量
int size();
// 是否为空
boolean isEmpty();
// 是否包含某个元素
boolean contains(E element);
// 添加元素到最后面
void add(E element);
// 往index位置添加元素
void add(int index, E element);
// 返回index位置对应的元素
E get(int index);
// 设置index位置的元素
E set(int index, E element);
// 删除index位置对应的元素
E remove(int index);
// 查看元素的位置
int indexOf(E element);
// 清除所有元素
void clear();
}
在Java中，成员变量会自动初始化，比如：
- int 类型自动初始化为 0
- 对象类型自动初始化为 null
三、动态数组的设计和实现
1、构造方法
如果构建的数组空间小于默认空间，则会以默认空间构建数组。
public class ArrayList<E> {
private int size;
private E[] elements;
// 设置elements数组默认的初始化空间
private static final int CAPACITY_DEFAULT = 10;
public ArrayList(int capacity) {
capacity = capacity < CAPACITY_DEFAULT ? CAPACITY_DEFAULT : capacity;
elements = (E[]) new Object[capacity];
}
// 便利构造器
public ArrayList() {
this(CAPACITY_DEFAULT);
}
}
2、添加元素
数组添加元素分为两种情况：
- Case1 ：在最后一个元素的后面添加新元素
- 这个
新元素需要添加到的索引等于当前数组元素的个数加1（即size+ 1）
- 这个
- Case2: 将元素插入到某个位置（
非最后面）。
/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacity(size + 1);
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
// 检测数组越界
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
private void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
如果是Case2的情况，需要依次变动插入位置后面的元素
⚠️ 注意，需要从最后一个元素开始变动
比如有一个原数组 {11, 22, 33,55}, 向index=2的位置插入元素44
image.png
（即：把55赋值到index为4的位置，把33赋值到index为3的位置，最后把44赋值到index为2的位置）
image.png
3、数组扩容
由于数组elements最大的容量只有10，所以当数组存满元素时，就需要对数组进行扩容。
因为数组是无法动态扩容的，所以需要创建一个新的数组，这个数组的容量要比之前数组的容量大。接着，将原数组中的元素存放到新数组中，这样就实现了数组的扩容。
image.png
private void ensureCapacity() {
// 获取数组当前容量
int oldCapacity = elements.length;
// 如果 当前存储的元素个数 < 当前数组容量, 直接返回
if (size < oldCapacity) return;
// 新数组的容量为原数组容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 创建新数组
E[] newElements = (E[]) new Object[newCapacity];
// 原数组中的元素存储到新数组中
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
// 引用新数组
elements = newElements;
}
实现add函数，需要在添加新元素之前，判断数组越界和扩容。
public void add(int index, E element) {
//判断越界
rangeCheckForAdd(index);
//判断扩容
ensureCapacity(size + 1);
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
4、删除元素
删除元素，实际上就是去掉指定位置的元素，并将后面的元素向前移动（其实是向前赋值）。
如下图，当删除索引为2的元素时，只需要将后面的元素向前移动，然后在去掉最后一个元素，size减1即可
image.png
/**
* 删除index位置的元素
* @param index
* @return
*/
public E remove(int index) {
// 删除元素时传入的索引不能越界
rangeCheck(index);
E old = elements[index];
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
elements[--size] = null;
return old;
}
5、数组缩容
当数组中的元素删除后，数组剩余的空间可能会很大，这样就会造成内存的浪费，当数组中元素删除后，我们需要对数组进行缩容。
实现方法类似于扩容，当数组中容量小于某个值时，创建新的数组，然后将原有数组中的元素存入新数组即可。
public void trim() {
// 获取当前数组的容量
int capacity = elements.length;
// 当size大于等于容量的一半, 或则容量已经小于默认容量(10)时, 直接返回
if (size >= capacity >> 1 || capacity < CAPACITY_DEFAULT) return;
// 计算新的容量 = 原有容量的一半
int newCapacity = capacity >> 1;
// 创建新数组
E[] newElements = (E[]) new Object[newCapacity];
// 将原数组元素存入新数组
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
// 引用新数组
elements = newElements;
}
最终, remove方法实现如下：
public E remove(int index) {
// 判断索引是否越界
rangeCheck(index);
// 取出需要删除的元素
E old = elements[index];
// 通过循环, 将index后面的所有元素向前移动一位
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
// 删除最后一个元素
elements[--size] = null;
// 判断数组是否需要缩容
trim();
// 将删除的元素返回
return old;
}
6、清空数组
清空数组时，需要将所有的元素置为null，只有这样才能真正的释放对象，然后size置为0。
public void clear() {
// 清空存储的数据
for (int i = 0; i < size; i++) {
elements[i] = null;
}
// 将size置为0
size = 0;
}
7、修改元素
修改元素时，只需要将原有位置的元素替换掉即可，同样需要注意一下索引是否越界。
public E set(int index, E element) {
// 判断索引是否越界
rangeCheck(index);
// 取出被替换元素
E oldElement = elements[index];
// 替换元素
elements[index] = element;
// 返回被替换元素
return oldElement;
}
8、查询元素
查询元素，只需要将指定索引的元素返回，注意索引是否越界即可
public E get(int index) {
rangeCheck(index);
return elements[index];
}
9、 查看元素位置
可以通过循环, 查找元素在数组中的位置。
注意：假如数组中可以存储null，而null是不能调用equals方法的，所以需要对传入的元素进行判断，如果查找的元素是null，需要单独处理。
当元素存在时返回索引，否则返回变量ELEMENT_ON_FOUND的值。
private static final int ELEMENT_NOT_FOUND = -1;
public int indexOf(E element) {
// null的处理
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;
}
是否包含某元素： 只需通过判断索引是否等于ELEMENT_ON_FOUND即可
public boolean contains(E element) {
// 查看元素的索引是否为ELEMENT_ON_FOUND即可
return indexOf(element) != ELEMENT_ON_FOUND;
}
10、动态数组打印
可以重写toString方法, 来打印ArrayList中的元素
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();
}
- 重写
toString方法 - 在
toString方法中将元素拼接成字符串 - 字符串拼接建议使用
StringBuilder
到此为止，我们成功的实现了动态数组。
11、 测试一下
ArrayList<Integer> list1 = new ArrayList<>();
list1.add(99);
list1.add(88);
list1.add(77);
list1.add(66);
list1.add(55);
list1.set(3, 80);
if ((int)list1.get(3) != 80) {
throw new IllegalAccessError("测试不通过");
}
Asserts.test((int)list1.get(3) == 80);
// Asserts断言类
package com.alangeit;
public class Asserts {
public static void test(boolean value) {
try {
if (!value) throw new Exception("测试未通过");
} catch (Exception e) {
e.printStackTrace();
}
}
}
动态数组的复杂度
image.png
ArrayList能否进一步优化？
image.png
在ArrayList中，如果要删除索引
0位置的元素，则需要将索引0之后的元素全部往前移一位。-
如果要在
索引0位置添加元素，也需要将索引0及之后的元素全部往后移一位。image.png 在ArrayList中增加一个记录
首元素位置的属性。删除索引
0位置的元素，我们只需要将first属性改为1。-
在索引
0位置添加元素，则只需要将first属性改为0。image.png 如果继续往前插入元素，则将插入的元素存放在索引
8这个位置，并将first改为8。-
当要获取索引
8下一个元素时，对索引取模，则拿到索引0位置的元素。image.png 如果插入元素，则可选择挪动前半段数据或后半段数据。
在
索引2处插入元素99，可以选择将元素22，33左移，然后插入99即可。扩容和缩容同样可以优化。
以下是完整源码
java版本
@SuppressWarnings("unchecked")
public class ArrayList<E> {
private int size; // 元素的数量
private E[] elements; // 所有的元素
private static final int DEFAULT_CAPACITY = 10; // 初始容量
private static final int ELEMENT_NOT_FOUND = -1;
public ArrayList(int capacity) { // 容量小于10一律扩充为10
capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
elements = (E[])new Object[capacity];
}
public ArrayList(){
this(DEFAULT_CAPACITY);
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element){
return indexOf(element) != ELEMENT_NOT_FOUND; // 找的到该元素则返回True
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index, E element){
rangeCheckForAdd(index); // 检查下标越界
ensureCapacity(size + 1); // 确保容量够大
// 0 1 2 3 4 5 6 7 8 9 (index)
// 1 2 3 4 5 6 x x x x (原数组)
// 在index=2处，插入9，元素全部后移
// 1 2 9 3 4 5 6 x x x (add后数组)
// 先从后往前开始, 将每个元素往后移一位, 然后再赋值
for (int i = size - 1; i > index; i--) {
elements[i + 1] = elements[i];
}
elements[index] = element; // 复制
size++;
}
/**
* 添加元素到最后面
*/
public void add(E element){
add(size, element);
}
/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素ֵ
*/
public E get(int index){
rangeCheck(index);
return elements[index];
}
/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素ֵ
*/
public E set(int index, E element){
rangeCheck(index);
E old = elements[index];
elements[index] = element;
return old;
}
/**
* 删除index位置的元素
* @param index
* @return
*/
public E remove(int index){
rangeCheck(index);
// 0 1 2 3 4 5 (index)
// 1 2 3 4 5 6 (原数组)
// 删除index为2的元素，元素前移
// 1 2 4 5 6 (remove后的数组)
// 从前往后开始移, 用后面的元素覆盖前面的元素
E old = elements[index];
for (int i = index; i < size - 1; i++) {
elements[i] = elements[i + 1];
}
elements[--size] = null; // 删除元素后, 将最后一位设置为null
return old;
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element){
/*
// 不对 null 进行处理也可以，但是健壮性不够
for (int i = 0; i < size; i++) {
if(elements[i].equals(element)) return i;
}
*/
if(element == null){ // 对 null 进行处理
for (int i = 0; i < size; i++) {
if(elements[i] == null) return i;
}
}else{
for (int i = 0; i < size; i++) {
if(elements[i].equals(element)) return i;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 清除所有元素
*/
public void clear(){
// 使用泛型数组后要注意内存管理(将元素置null)
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
/**
* 扩容操作
*/
private void ensureCapacity(int capacity){
int oldCapacity = elements.length;
if(oldCapacity >= capacity) return;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[])new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i]; // 拷贝原数组元素到新数组
}
elements = newElements;
System.out.println("size="+oldCapacity+", 扩容到了"+newCapacity);
}
/****************封装好的功能函数**************************/
// 下标越界抛出的异常
private void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
// 检查下标越界(不可访问或删除size位置)
private void rangeCheck(int index){
if(index < 0 || index >= size){
outOfBounds(index);
}
}
// 检查add()的下标越界(可以在size位置添加元素)
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
/****************封装好的功能函数***************************/
@Override
public String toString() {
// 打印形式为: size=5, [99, 88, 77, 66, 55]
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
for (int i = 0; i < size; i++) {
if(0 != i) string.append(", ");
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
}
// 测试一下
public static void main(String[] args) {
ArrayList<Person> list = new ArrayList<>();
list.add(new Person(10, "jack"));
list.add(new Person(20, "rose"));
list.add(null);
list.add(null);
System.out.println("add()添加元素: " + list);
System.out.println("get()获取元素: " + list.get(0));
list.set(0, new Person(99, "ghost"));
System.out.println("set()设置元素值: " + list);
list.remove(0);
System.out.println("remove()删除元素: " + list);
list.clear();
System.out.println("clear()清空数组: " + list);
}
