数组
- 数组在声明时大小固定，未存满的情况下，会留有某个位置是没有元素的
- 数组有索引的概念，从零开始
- 查询快（支持随机访问），增删慢
自己封装的数组（仅支持int类型）
/**
* @ClassName: Array
* @Description: 自定义动态数组
*/
public class Array {
private int[] data; //真正的数组，和数组的容量使用data.length表示
private int size; //数组中有元素的个数，同时也指向了末端后的一个没有元素的位置
/**
* @param capacity: 用户指定的容量
* @MethodName: Array
* @Description: 根据用户需求创建指定大小容量的数组
*/
public Array(int capacity) {
this.data = new int[capacity];
this.size = 0;
}
/**
* @MethodName: Array
* @Description: 为用户设置默认的容量大小，为10
*/
public Array() {
this(10);
}
/**
* @MethodName: getSize
* @Description: 获取已存入元素个数
* @Return int
*/
public int getSize() {
return this.size;
}
/**
* @MethodName: getCapacity
* @Description: 获取数组容量
* @Return int
*/
public int getCapacity() {
return this.data.length;
}
/**
* @MethodName: isEmpty
* @Description: 判断数组是否为空
* @Return boolean
*/
public boolean isEmpty() {
return this.size == 0;
}
/**
* @MethodName: add
* @Description: 向指定的位置插入指定的元素
* @Param index: 指定的位置
* @Param element: 指定的元素
* @Return void
*/
public void add(int index, int element) {
if (index < 0 || index > this.size) { //若传入的index不在数组范围内，将无法插入
throw new IllegalArgumentException("Add failed, Index is illegal");
}
if (this.size == this.data.length) { //若元素个数与容量大小相等时，说明数组已经满了
throw new IllegalArgumentException("Add failed, Array is full");
}
for (int i = size - 1; i >= index; i--) { //size-1将i指针指向了末端
//将数组中从插入元素开始整个向后移动，腾出要插入位置位置
//此时i指向要移动的块（末端），一直向左逼近，直到到插入的位置，将插入位置的元素向后移动后即可循环结束
this.data[i + 1] = this.data[i];
//将前一个元素赋给后一个元素，即将第i个元素赋给第i+1个元素
}
this.data[index] = element; //插入元素
this.size++; //添加完毕元素后需要将元素个数加一
}
/**
* @MethodName: get
* @Description: 用户根据指定索引获取元素
* @Param index: 指定的索引
* @Return int
*/
public int get(int index) {
if (index < 0 || index > this.size) {
throw new IllegalArgumentException("Get failed, Index is illegal");
}
return this.data[index];
}
/**
* @MethodName: set
* @Description: 用户根据索引修改元素内容
* @Param index: 指定的索引
* @Param element: 要修改成的内容
* @Return void
*/
public void set(int index, int element) {
if (index < 0 || index > this.size) {
throw new IllegalArgumentException("Set failed, Index is illegal");
}
this.data[index] = element;
}
/**
* @MethodName: contains
* @Description: 判断数组是否包含该元素
* @Param element: 要判断的元素
* @Return boolean
*/
public boolean contains(int element) {
for (int i = 0; i < size - 1; i++) {
//遍历整个数组，但是仅限于用户存入的元素，size是元素个数，所以要减1
if (this.data[i] == element) {
return true; //若找到相同的元素就返回true
}
}
return false; //遍历完整个数组都未找到相同的元素，说明就不包含该元素，返回false
}
/**
* @MethodName: find
* @Description: 根据元素查找第一个符合的索引，找不到返回-1
* @Param element: 要查找的元素
* @Return int
*/
public int find(int element) {
for (int i = 0; i < this.size; i++) {
if (element == this.data[i]) {
return i;
}
}
return -1;
}
/**
* @MethodName: findAll
* @Description: 根据元素查找所有符合条件的索引并以数组形式返回，找不到返回就返回一个空数组
* @Param element: 要查找的元素
* @Return int[]
*/
public int[] findAll(int element) {
int number = 0; //要返回的数组容量
for (int i = 0; i < this.size; i++) { //遍历整个数组，找到有几个与要查找的元素相同的元素
if (element == this.data[i]) { //有与要查找的元素相同的元素
number++; //容量就加1
}
}
if (number > 0) { //若有符合条件的元素
int[] indexes = new int[number]; //就开辟能刚好盛满所有索引的数组
for (int i = 0, j = 0; i < this.size; i++) { //遍历整个数组
if (element == this.data[i]) { //有与要查找的元素相同的元素
indexes[j] = i; //就放入索引数组中
j++; //索引数组下标加1
}
}
return indexes; //返回索引数组
} else { //若没有符合条件的元素
return new int[]{}; //就返回一个空数组
}
}
/**
* @MethodName: remove
* @Description: 根据索引删除指定元素，并返回删除的元素
* @Param index: 指定的索引
* @Return void
*/
public int remove(int index) {
if (index < 0 || index >= size) { //若传入的index不在数组范围内，将删除失败
throw new IllegalArgumentException("Remove failed, Index is illegal");
}
int result = data[index]; //存储要删除的元素
for (int i = index; i < this.size - 1; i++) { //size-1是末端，当i指向末端时结束移动
//将数组中从删除元素开始整个向前移动，挤掉要删除的元素
//此时i指向要移动的块（始端），一直向右逼近，直到末端，将删除元素覆盖掉即可循环结束
data[i] = data[i + 1];
//将后一个元素赋给前一个元素，即将第i+1个元素赋给第i个元素
}
this.size--; //删除完毕元素后需要将元素个数减1
return result; //返回删除元素
}
/**
* @MethodName: removeElement
* @Description: 根据元素内容删除匹配的第一个元素，删除成功返回true否则返回false
* @Param element: 要匹配的元素
* @Return boolean
*/
public boolean removeElement(int element) {
int index = this.find(element); //先根据元素查找所在索引
if (index != -1) { //若元素存在
this.remove(index); //就删除
return true; //返回true表示删除成功
}
return false; //返回false表示元素不存在，删除失败
}
/**
* @MethodName: removeAllElement
* @Description: 根据元素内容删除所有匹配的元素
* @Param element: 要匹配的元素
* @Return void
*/
public void removeAllElement(int element) {
while (this.removeElement(element)) { } //由于removeElement删除成功会返回true，就可以循环调用达到删除全部的目的
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder(); //使用StringBuilder进行拼接字符串，方便查看结果
for (int i = 0; i < this.size; i++) {
sb.append(data[i]);
if (i != this.size - 1) { //若不是最后一个元素会加一个逗号进行分隔
sb.append(",");
}
}
return "Array{" +
"capacity=" + this.data.length +
", size=" + this.size +
'}' +
": [" +
sb.toString()
+ "]";
}
}
使用泛型增强自定义数组
- Java语言不支持直接new一个泛型数组，需要先new一个Object数组，再使用向下强制转型成泛型数组（记着加
[]） - Java语言对于对象的比较需要使用
equals()方法进行比较 - Java语言对于对象有垃圾回收机制，在弃用对象时，最好将该对象的引用置为null（比如
remove()方法） - 将所有用到传入数据参数的类型中变为泛型（比如
set()方法），所有返回数据参数的类型中变为泛型（比如get()方法） - 在使用泛型类时，需要指定泛型，并且只能使用引用数据类型（声明和创建都需要
<>但是创建中可省略指定类型）
import java.util.Objects;
/**
* @ClassName: Array
* @Description: 自定义动态数组
*/
public class Array<E> {
private E[] data; //真正的数组，和数组的容量使用data.length表示
private int size; //数组中有元素的个数，同时也指向了末端后的一个没有元素的位置
/**
* @param capacity: 用户指定的容量
* @MethodName: Array
* @Description: 根据用户需求创建指定大小容量的数组
*/
public Array(int capacity) {
this.data = (E[]) new Object[capacity];
this.size = 0;
}
/**
* @MethodName: Array
* @Description: 为用户设置默认的容量大小，为10
*/
public Array() {
this(10);
}
/**
* @MethodName: getSize
* @Description: 获取已存入元素个数
* @Return int
*/
public int getSize() {
return this.size;
}
/**
* @MethodName: getCapacity
* @Description: 获取数组容量
* @Return int
*/
public int getCapacity() {
return this.data.length;
}
/**
* @MethodName: isEmpty
* @Description: 判断数组是否为空
* @Return boolean
*/
public boolean isEmpty() {
return this.size == 0;
}
/**
* @MethodName: add
* @Description: 向指定的位置插入指定的元素
* @Param index: 指定的位置
* @Param element: 指定的元素
* @Return void
*/
public void add(int index, E element) {
if (index < 0 || index > this.size) { //若传入的index不在数组范围内，将无法插入
throw new IllegalArgumentException("Add failed, Index is illegal");
}
if (this.size == this.data.length) { //若元素个数与容量大小相等时，说明数组已经满了
throw new IllegalArgumentException("Add failed, Array is full");
}
for (int i = size - 1; i >= index; i--) { //size-1将i指针指向了末端
//将数组中从插入元素开始整个向后移动，腾出要插入位置位置
//此时i指向要移动的块（末端），一直向左逼近，直到到插入的位置，将插入位置的元素向后移动后即可循环结束
this.data[i + 1] = this.data[i];
//将前一个元素赋给后一个元素，即将第i个元素赋给第i+1个元素
}
this.data[index] = element; //插入元素
this.size++; //添加完毕元素后需要将元素个数加一
}
/**
* @MethodName: get
* @Description: 用户根据指定索引获取元素
* @Param index: 指定的索引
* @Return int
*/
public E get(int index) {
if (index < 0 || index > this.size) {
throw new IllegalArgumentException("Get failed, Index is illegal");
}
return this.data[index];
}
/**
* @MethodName: set
* @Description: 用户根据索引修改元素内容
* @Param index: 指定的索引
* @Param element: 要修改成的内容
* @Return void
*/
public void set(int index, E element) {
if (index < 0 || index > this.size) {
throw new IllegalArgumentException("Set failed, Index is illegal");
}
this.data[index] = element;
}
/**
* @MethodName: contains
* @Description: 判断数组是否包含该元素
* @Param element: 要判断的元素
* @Return boolean
*/
public boolean contains(E element) {
for (int i = 0; i < size - 1; i++) {
//遍历整个数组，但是仅限于用户存入的元素，size是元素个数，所以要减1
if (this.data[i].equals(element)) {
return true; //若找到相同的元素就返回true
}
}
return false; //遍历完整个数组都未找到相同的元素，说明就不包含该元素，返回false
}
/**
* @MethodName: find
* @Description: 根据元素查找第一个符合的索引，找不到返回-1
* @Param element: 要查找的元素
* @Return int
*/
public int find(E element) {
for (int i = 0; i < this.size; i++) {
if (this.data[i].equals(element)) {
return i;
}
}
return -1;
}
/**
* @MethodName: findAll
* @Description: 根据元素查找所有符合条件的索引并以数组形式返回，找不到返回就返回一个空数组
* @Param element: 要查找的元素
* @Return int[]
*/
public int[] findAll(E element) {
int number = 0; //要返回的数组容量
for (int i = 0; i < this.size; i++) { //遍历整个数组，找到有几个与要查找的元素相同的元素
if (this.data[i].equals(element)) { //有与要查找的元素相同的元素
number++; //容量就加1
}
}
if (number > 0) { //若有符合条件的元素
int[] indexes = new int[number]; //就开辟能刚好盛满所有索引的数组
for (int i = 0, j = 0; i < this.size; i++) { //遍历整个数组
if (this.data[i].equals(element)) { //有与要查找的元素相同的元素
indexes[j] = i; //就放入索引数组中
j++; //索引数组下标加1
}
}
return indexes; //返回索引数组
} else { //若没有符合条件的元素
return new int[]{}; //就返回一个空数组
}
}
/**
* @MethodName: remove
* @Description: 根据索引删除指定元素，并返回删除的元素
* @Param index: 指定的索引
* @Return void
*/
public E remove(int index) {
if (index < 0 || index >= size) { //若传入的index不在数组范围内，将删除失败
throw new IllegalArgumentException("Remove failed, Index is illegal");
}
E result = data[index]; //存储要删除的元素
for (int i = index; i < this.size - 1; i++) { //size-1是末端，当i指向末端时结束移动
//将数组中从删除元素开始整个向前移动，挤掉要删除的元素
//此时i指向要移动的块（始端），一直向右逼近，直到末端，将删除元素覆盖掉即可循环结束
data[i] = data[i + 1];
//将后一个元素赋给前一个元素，即将第i+1个元素赋给第i个元素
}
this.size--; //删除完毕元素后需要将元素个数减1
data[size] = null;
//由于最后一个元素还与data数组有引用关系，所以最好手动置为空，方便垃圾回收机制快速回收
return result; //返回删除元素
}
/**
* @MethodName: removeElement
* @Description: 根据元素内容删除匹配的第一个元素，删除成功返回true否则返回false
* @Param element: 要匹配的元素
* @Return boolean
*/
public boolean removeElement(E element) {
int index = this.find(element); //先根据元素查找所在索引
if (index != -1) { //若元素存在
this.remove(index); //就删除
return true; //返回true表示删除成功
}
return false; //返回false表示元素不存在，删除失败
}
/**
* @MethodName: removeAllElement
* @Description: 根据元素内容删除所有匹配的元素
* @Param element: 要匹配的元素
* @Return void
*/
public void removeAllElement(E element) {
while (this.removeElement(element)) {
} //由于removeElement删除成功会返回true，就可以循环调用达到删除全部的目的
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder(); //使用StringBuilder进行拼接字符串，方便查看结果
for (int i = 0; i < this.size; i++) {
sb.append(data[i]);
if (i != this.size - 1) { //若不是最后一个元素会加一个逗号进行分隔
sb.append(",");
}
}
return "Array{" +
"capacity=" + this.data.length +
", size=" + this.size +
'}' +
": [" +
sb.toString()
+ "]";
}
}
改为动态数组增强自定义数组
- 动态数组是指容量动态：只是在插入和删除数据时才会对容量进行扩充或收缩
/**
* @MethodName: resize
* @Description: 将data扩容指定大小
* @Param newCapacity: 指定的大小
* @Return void
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < this.size; i++) {
newData[i] = this.data[i];
}
this.data = newData;
}
- 在容量不足时自动扩大容量，也就是
add()方法中，在抛出容量不足的异常时，将该数组拷贝到一个新的且容量较大的数组中- 注意添加元素之前扩容，扩容应该是动态的，应该与当前容量有关
/**
* @MethodName: add
* @Description: 向指定的位置插入指定的元素
* @Param index: 指定的位置
* @Param element: 指定的元素
* @Return void
*/
public void add(int index, E element) {
if (index < 0 || index > this.size) { //若传入的index不在数组范围内，将无法插入
throw new IllegalArgumentException("Add failed, Index is illegal");
}
if (this.size == this.data.length) { //若元素个数与容量大小相等时，说明数组已经满了
this.resize(this.getCapacity() * 2); //此时不再抛出异常，而是扩容操作
}
for (int i = size - 1; i >= index; i--) { //size-1将i指针指向了末端
//将数组中从插入元素开始整个向后移动，腾出要插入位置位置
//此时i指向要移动的块（末端），一直向左逼近，直到到插入的位置，将插入位置的元素向后移动后即可循环结束
this.data[i + 1] = this.data[i];
//将前一个元素赋给后一个元素，即将第i个元素赋给第i+1个元素
}
this.data[index] = element; //插入元素
this.size++; //添加完毕元素后需要将元素个数加一
}
- 在容量过多时自动缩小容量，也就是
remove()方法中，删除元素之后判断在达到一定容量时，就将该数组拷贝到一个新的且较小的数组中- 缩容应该也是动态的，应该与当前容量有关
- 还要注意判断是否缩容使用的是除法，所以除出来的结果有可能等于0，要加一层判断
- 而且不要缩容的刚好将容器填满，否则可能会出现用户在此界限上反复增加删除，导致一直扩容和缩容，性能大大降低）
/**
* @MethodName: remove
* @Description: 根据索引删除指定元素，并返回删除的元素
* @Param index: 指定的索引
* @Return void
*/
public E remove(int index) {
if (index < 0 || index >= size) { //若传入的index不在数组范围内，将删除失败
throw new IllegalArgumentException("Remove failed, Index is illegal");
}
E result = data[index]; //存储要删除的元素
for (int i = index; i < this.size - 1; i++) { //size-1是末端，当i指向末端时结束移动
//将数组中从删除元素开始整个向前移动，挤掉要删除的元素
//此时i指向要移动的块（始端），一直向右逼近，直到末端，将删除元素覆盖掉即可循环结束
data[i] = data[i + 1];
//将后一个元素赋给前一个元素，即将第i+1个元素赋给第i个元素
}
this.size--; //删除完毕元素后需要将元素个数减1
data[size] = null;
//由于最后一个元素还与data数组有引用关系，所以最好手动置为空，方便垃圾回收机制快速回收
if (this.getCapacity() / 4 == this.getSize() && this.getCapacity() / 2 != 0) {
//在删除元素后判断是否容量过大，并且容量不能是0
//缩容也不是刚刚将容器填满
this.resize(this.getCapacity() / 2);
}
return result; //返回删除元素
}
Comments NOTHING