前言
数据结构很重要，因为大学起步晚。上数据结构的时候听是听得懂，但是怎么都写不出来。网上代码也不是很实用，也就是一套代码不可以复用，换个数据类型就不支持了。踏入企业才知道数据结构还是挺重要的，于是重新开始学习数据结构......把自己的学习记下来，然后日后能够复习的时候我想起我写过一篇关于数据结构的文章，我可以重新过一遍。同时，也能够帮助大家学习。
概要说明
Java原生的数组都很不好用，因为其初始化就要指明整个数组的长度，而且还不能修改。但我们希望数组的长度可以随着我们业务所需的数据量的大小，动态变化。而不是每次要想预估可能的数据量，因为凡事都有万一！而且实际发现可能用不了这么多的长度，也在浪费内存为数组开辟的那么大空间。
因此，我们希望再此基础上，进行二次封装，做一个可以动态扩、缩容的数组，且能够不断复用。
使用泛型
在复用性上，我们希望支持泛型。泛型可以放入任何数据类型的数据。当然，整个所谓的任何是不支持基本数据类型（int、double、float等）。估计对Java了解不深的人会跳起来了，你这不是坑人吗，我刚学可就是用这些数据类型，你告诉我不支持，我还学什么。取关！！！
其实，泛型虽然不支持基本数据类型，但可以通过“曲线救国”，使用包装类型。因为基本数据类型没有null概念，所以Java就提出了包装类。为什么要使用包装类，因为它太需要了：某A同学数据结构考了0分，B同学他缺考了，得了0分。老师认为B缺考性质恶劣，要让他没有补考机会。他就可以让B同学的分数为null。它就可以用double的升级版Double来记录分数区分他们。
基本数据类型对应的包装类型很简单，大部分是首字母大写就是它对应的包装类型。其实就是封装了基本数据类型为对象。记住一点：String它不是基本数据类型，从它的大写开头就知道了......
说了这么多，其实也是让自己加深对泛型和包装类的理解。
概要设计
需求
肯定要实现的功能：增、删、改、查
因为要实现动态扩、缩容：我要知道当前数组的容量多大了，还要知道我用了多少长度。每次扩、缩多少长度。
可能还要知道数组是不是为空？
我的业务场景只是每次向第一个或者最后一个坑位插数据，每次还要去判断插满了没，太复杂了。我希望封装起来。
整理
- 增：向某个索引新增数据
void add(int index,T value);
- 删：移除某个索引下的数据
T remove(int index,T value);
- 改：修改某个索引下的数据
void set(int index,T value);
- 查：查询某个索引下的数据
T get(int index);
- 修改数组容量（扩、缩容）
void resize(int capacity);
- 当前数组大小
int size();
- 当前数据容量
int capacity();
- 是否为空
boolean isEmpty();
拓展
- 向数组头插入（第一个位置）
void addFirst(T value);
- 向数组尾插入
void addLast(T value);
- 移除数组头部数据
T removeFirst()
- 移除尾部数据
T removeLast();
- 数组中是否包含有该值？
boolean contains(T value);
- 查询数组中，该值的索引的位置
int find(T value);
实现代码
如何实现思路都是数据结构的书写的，不具体详细概述。具体有些在代码中也有注释，细心体会～
package com.example;
/**
* 自定义数组(二次封装) - Java实现
* 功能说明：
* 1.根据数组自动扩/缩容
* 2.封装常用数组操作
*
* @param <T> 对象类型
*/
public class Array<T> {
//数据
private T[] data;
//数组大小
private int size;
/**
* 无参构造方法
* 初始化使用默认数组容量
*/
public Array() {
this(10);
}
/**
* 有参构造方法
* 初始化自定义数组容量
*
* @param capacity 容量值
*/
public Array(int capacity) {
this.data = (T[]) new Object[capacity];
this.size = 0;
}
/**
* 返回当前数组长度
*
* @return size
*/
public int size() {
return size;
}
/**
* 返回当前数组是否为空
*
* @return true or false
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 获取数组容量
*
* @return 容量
*/
public int capacity() {
return data.length;
}
/**
* 在指定索引添加值
* 设计思路:
* 1.判断索引的合法性
* 2.判断是否空间已满，满了自动扩容
* 3.将该索引之后数据往后挪一位
* 4.放入数据
* 5.数组长度+1
*
* @param index 索引
* @param value 值
*/
public void add(int index, T value) {
if (index < 0 || index >= data.length)
throw new IllegalArgumentException("add fail. index is illegal.");
if (size == data.length)
resize((int) (1.5 * size));
for (int i = size - 1; i >= index; i--)
data[i + 1] = data[i];
data[index] = value;
size++;
}
/**
* 数组尾部添加值
*
* @param value 值
*/
public void addLast(T value) {
add(size, value);
}
/**
* 数组头部添加值
*
* @param value 值
*/
public void addFirst(T value) {
add(0, value);
}
/**
* 数组是否包含该值，包含则返回true，否则返回false
*
* @param value 值
* @return true or false
*/
public boolean contains(T value) {
return find(value) != -1;
}
/**
* 值第一次出现时的索引位值，如果没有该值返回-1
*
* @param value 值
* @return index
*/
public int find(T value) {
for (int i = 0; i < size; i++) {
if (data[i].equals(value)) {
return i;
}
}
return -1;
}
/**
* 修改某个索引的值
* 设计思路：
* 1.判断索引的合法性
* 2.修改
*
* @param index 索引
* @param value 值
*/
public void set(int index, T value) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("set value fail. index is illegal.");
data[index] = value;
}
/**
* 移除某个索引下的值
* 设计思路：
* 1.判断索引的合法性
* 2.将索引之后的数组往前挪一位（覆盖）
* 可选优化：将data[size-1] = null，垃圾回收机制会将其回收
* 4.动态缩减容量
* 3.数组长度-1
*
* @param index 索引
*/
public void remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("remove fail. index is illegal.");
for (int i = index + 1; i < size; i++)
data[i - 1] = data[i];
data[size - 1] = null;
if (size == (capacity() / 2))
resize(capacity() / 2);
size--;
}
/**
* 移除数组的第一个值
*/
public void removeFirst() {
remove(0);
}
/**
* 移除数组的最后一个值
*/
public void removeLast() {
remove(size - 1);
}
/**
* 删除指定元素
*
* @param value 值
*/
public void removetValue(T value) {
int index = find(value);
if (index != -1)
remove(index);
}
/**
* 动态扩容
* 扩容操作对外部来说应该是无感知的，因此将其私有
*/
private void resize(int capacity) {
T[] newData = (T[]) new Object[capacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
}
说明
动态扩所容的实现原理很简单，其实就是重新创建一个数组，将原来的数据拷贝过去。在将指针指向新数组。
很多人会觉得很low，其实封装这种事情，就是为了掩藏low代码，屏蔽其中的细节。但有一个意识很重要：实现方式low不等于性能不好。如果有更好的思路去减少复杂度，是不错的选择！
功能验证
创建一个类和main方法：
package com.example;
public class Application {
class Student {
private String name;
private Integer age;
public Student(String name, Integer age) {
this.name = name;
this.age = age;
}
}
public static void main(String[] args) {
Array<String> array = new Array<>(100);
array.addLast("张三");
array.addLast("李四");
System.out.println(array.removeLast());
//复用示例
Array<Student> array1 = new Array<>(50);
//todo
}
}
验证写的比较少，就是意思一下～博客写的比较累，验证已经没有动力写了，偷懒一下～自己动手试试
网友评论