一 java中的数组
1. 数组是学习java接触到的第一个数据结构，也是最简单的数据结构;
2. 数组基础
- 把数据码成一排进行存放就叫做数组;
- 数组中有一个很重要的概念叫做索引(注意：索引从0开始)；
- 使用数组的优点：可以根据索引快速查询；
- 数组最好应用于有“索引有语意”的情况；
- 并非所有有语意的索引都适用于数组，比如说使用身份证号查询某人的工资情况，这样的情况就需要考虑其他的数据结构了或者考虑使用索引没有语意的情况；
- 如果索引没有语意就会出现新的问题比如说：
1⃣️如上图所示，在索引没有语意的情况下，如何表示没有的元素？
2⃣️如何添加元素，如何删除元素？
二 基于java提供的数组二次封装出一个属于自己的数组
1. 封装一个基本数组
2. 示例代码
public class ArrayTest {
// 声明一个私有的int类型数组
private int[] data;
// 声明数组的大小
private int size;
/**
* 构造函数，传入数组的容量capacity构造ArrayTest
* @param capacity
*/
public ArrayTest(int capacity){
// 创建一个数组，容量为capacity
data = new int[capacity];
// 初始长度为0
size = 0;
}
/**
* 无参数的构造函数，默认数组的容量capacity=10
*/
public ArrayTest(){
// 默认数组长度为10
this(10);
}
/**
* 获取数组中的元素个数
* @return
*/
public int getSize(){
return size;
}
/**
* 获取数组容量
* @return
*/
public int getCapacity(){
return data.length;
}
/**
* 判断数组中是否有元素
* @return
*/
public boolean isEmpty(){
return size == 0;
}
}
参数说明：
- size：表示数组中元素的个数(后续的添加 删除等操作需要维护此属性)；
- data：声明的数组；
- capacity：不需要维护，因为当用户创建数组是需要传入数组的默认长度；
2. 向数组中添加元素
2.1 向空数组添加元素
2.2 代码
/**
* 向所有元素后添加一个新元素
* @param e
*/
public void addlast(int e){
// 判断数组长度与容量是否相等
if (size == data.length){
throw new IllegalArgumentException("AddLast failed. Array is full.");
}
// 向最后一个元素后边添加一个元素
data[size] = e;
// 维护数组长度
size++;
}
2.3 向数组中任意一个位置添加新的元素
由上边图示可以看出，向指定索引添加元素的过程需要对数组其他位置的元素进行移动的操作，而且是从后向前移动(如果从前往后移动会覆盖掉下一个索引位置的元素)，最后还需要维护一下size属性；
2.4 代码
/**
* 向指定索引位置插入元素
* @param index
* @param e
*/
public void add(int index, int e){
// 判断数组长度与容量是否相等
if (size == data.length){
throw new IllegalArgumentException("AddLast failed. Array is full.");
}
// 判断索引是否合法
if (index < 0 || index > size){
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
// 从后往前遍历遍历数组，实现数组中元素的位移
for (int i = size - 1; i >= index; i--){
// 将当前索引位置的元素移动至下一个索引位置上
data[i + 1] = data[I];
}
// 向指定索引位置插入元素
data[index] = e;
// 维护数组长度
size++;
}
2.5 复用核心添加逻辑改造方法
/**
* 向所有元素后添加一个新元素
* @param e
*/
public void addlast(int e){
// 复用核心的添加逻辑
add(size,e);
}
/**
* 向数组的第一个位置添加一个元素
* @param e
*/
public void addFirst(int e){
// 复用核心的添加逻辑
add(0,e);
}
/**
* 向指定索引位置插入元素
* @param index
* @param e
*/
public void add(int index, int e){
// 判断数组长度与容量是否相等
if (size == data.length){
throw new IllegalArgumentException("AddLast failed. Array is full.");
}
// 判断索引是否合法
if (index < 0 || index > size){
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
// 从后往前遍历遍历数组，实现数组中元素的位移
for (int i = size - 1; i >= index; i--){
// 将当前索引位置的元素移动至下一个索引位置上
data[i + 1] = data[I];
}
// 向指定索引位置插入元素
data[index] = e;
// 维护数组长度
size++;
}
3. 重写toString
/**
* toString
* @return
*/
@Override
public String toString(){
// 创建新的容器
StringBuilder stringBuilder = new StringBuilder();
// 设置格式
stringBuilder.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
// 开始拼接返回值
stringBuilder.append("[");
// 使用循环进行拼接
for (int i = 0; i < size; i++){
// 向容器中装载元素
stringBuilder.append(data[I]);
// 判断是否是最后一个元素
if (i != size - 1){
// 拼接分隔符
stringBuilder.append(", ");
}
}
// 闭合
stringBuilder.append("]");
// 返回
return stringBuilder.toString();
}
4 获取以及修改指定索引位置的元素
/**
* 获取指定索引位置上的元素
* @param index
* @return
*/
public int get(int index){
if (index < 0 || index >= size){
throw new IllegalArgumentException("Get failed, index is illegal.");
}
return data[index];
}
/**
* 修改指定索引位置的元素
* @param index
* @param e
*/
public void set(int index, int e){
if (index < 0 || index >= size){
throw new IllegalArgumentException("Set failed, index is illegal.");
}
data[index] = e;
}
注意：get方法对data进行了封装，调用者是无法调用到没有元素的索引位置的。
5 包含与搜索
/**
* 查看数组中是否包含某个元素
* @param e
* @return
*/
public boolean contains(int e){
// 遍历数组查询元素
for (int i = 0; i < size; i++){
// 判断当前位置元素是否是要找的元素
if (data[i] == e){
// 返回结果
return true;
}
}
// 返回结果
return false;
}
/**
* 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
* @param e
* @return
*/
public int find(int e){
// 遍历数组查询元素
for (int i = 0; i < size; i++){
// 判断当前位置元素是否是要找的元素
if (data[i] == e){
// 返回结果
return I;
}
}
return -1;
}
6 删除操作
6.1 删除操作过程图示
从以上图示中可以看出，删除操作与添加操作相似，删除操作是一个从后向前赋值的操作，通过将后一个元素赋值给前一个元素从而到达删除元素的目的；值得注意的是最后一个元素也就是size所在位置的元素在操作完成以后并没有被置为默认值，但是调用者是无法调用到这个位置的，所以可以不做处理；
6.2 代码
/**
* 删除指定索引位置的元素，并返回被删除的元素
* @param index
* @return
*/
public int remove(int index){
// 判断索引是否合法
if (index < 0 || index >= size){
throw new IllegalArgumentException("Remove failed, index is illegal.");
}
// 记录要被删除的元素
int ret = data[index];
// 通过遍历找到要被删除的元素
for (int i = index + 1; i < size; i++){
// 从后向前进行赋值操作
data[i - 1] = data[i];
}
// 维护数组长度
size--;
// 返回结果
return ret;
}
/**
* 删除数组中的第一个元素
* @return
*/
public int removeFirst(){
return remove(0);
}
/**
* 删除数组中的最后一个元素
* @return
*/
public int removelast(){
return remove(size - 1);
}
/**
* 删除指定索引
* @param e
*/
public void removeElement(int e){
// 调用查询方法查找要删除元素的索引
int index = find(e);
// 判断索引是否合法
if (index != -1){
// 调用删除方法执行删除操作
remove(index);
}
}
在删除操作中也使用了类似于添加操作的复用思想。
7 使用泛型改造数组
截止目前为止，封装的数组是int型的(也就是说只能存放int型的数据)，在java的概念中关于数组我们一般习惯性的称之为容器；所以我们需要对数组进行一定的改造，让它可以存放任何类型(这些类型包含java中的对象以及我们自己创建的数据类型比如：student、car)
下面看一下改造以后的代码：
package com.arrays.array;
/**
* Created by yangxiaokai on 2018/5/27.
*/
public class Array<E> {
private E[] data;
private int size;
/**
* 构造函数，传入数组的容量capacity构造Array
* @param capacity
*/
public Array(int capacity){
// 创建数据，长度为capacity
data = (E[]) new Object[capacity];
// 长度为0
size = 0;
}
/**
* 无参数的构造函数，默认数组的容量capacity=10
*/
public Array(){
// 默认数组长度为10
this(10);
}
/**
* 获取数组的容量
* @return
*/
public int getCapacity(){
return data.length;
}
/**
* 获取数组中的元素个数
* @return
*/
public int getSize(){
return size;
}
/**
* 返回数组是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 向所有元素后添加一个新元素
* @param e
*/
public void addLast(E e){
add(size,e);
}
/**
* 在所有元素前添加一个新元素
* @param e
*/
public void addFirst(E e){
add(0,e);
}
/**
* 在index索引的位置插入一个新元素e
* @param index
* @param e
*/
public void add(int index, E e){
// 判断索引是不是合法
if (index < 0 || index > size){
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
// 通过遍历将数组中的元素进行位移
for (int i = size - 1; i >= index; i--){
data[i + 1] = data[i];
}
// 将新添加的元素放入到数组指定的索引位置上
data[index] = e;
// 操作数组长度增加1
size++;
}
/**
* 获取索引index上的元素
* @param index
* @return
*/
public E get(int index){
if (index < 0 || index >= size){
throw new IllegalArgumentException("Get failed, index is illegal.");
}
return data[index];
}
/**
* 设置索引index上的元素
* @param index
* @param e
*/
public void set(int index, E e){
if (index < 0 || index >= size){
throw new IllegalArgumentException("Set failed, index is illegal.");
}
data[index] = e;
}
/**
* 查询数组中是否包含元素e
* @param e
* @return
*/
public boolean contains(E e){
// 遍历数组查找元素
for (int i = 0; i < size; i++){
if (data[i].equals(e)){
return true;
}
}
return false;
}
/**
* 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
* @param e
* @return
*/
public int find(E e){
// 遍历数组查找元素
for (int i = 0; i < size; i++){
if (data[i].equals(e)){
// 返回索引
return i;
}
}
return -1;
}
/**
* 从数组中删除index位置的元素, 返回删除的元素
* @param index
* @return
*/
public E remove(int index){
if (index < 0 || index >= size){
throw new IllegalArgumentException("Remove failed, index is illegal.");
}
// 记录被删除的元素
E res = data[index];
// 通过遍历将数组中的元素进行位移
for (int i = index + 1; i < size; i++){
// 索引考后的元素覆盖索引靠前的元素
data[i - 1] = data[i];
}
// 操作数组长度
size--;
// 将数组的最后一个位置上的元素置为空
data[size] = null;
// 返回记录结果
return res;
}
/**
* 从数组中删除第一个索引上的元素并返回被删除的元素
* @return
*/
public E removeFirst(){
return remove(0);
}
/**
* 从数组中删除最后一个索引上的元素并返回被删除的元素
* @return
*/
public E removeLast(){
return remove(size - 1);
}
/**
* 从数组中删除指定元素
* @param e
*/
public void removeElement(E e){
// 查询数组中是否有此元素
int index = find(e);
// 根据结果判断
if (index != -1){
remove(index);
}
}
/**
* toString
* @return
*/
@Override
public String toString(){
// 创建新的容器
StringBuilder builder = new StringBuilder();
// 设置数组格式
builder.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
// 拼接返回值
builder.append("[");
for (int i = 0; i < size; i++){
// 向容器中添加元素
builder.append(data[i]);
// 判断是否大于容器长度
if (i != size -1){
// 拼接分隔符
builder.append(", ");
}
}
// 闭合
builder.append("]");
// 返回
return builder.toString();
}
}
由于现在数组使用了泛型可以存放引用的数据类型，所以我们在删除的方法中需要将最后一个位置上的元素置为空，如果不置空的话将会影响垃圾回收，因为此位置上一直存在一个引用。
8 动态数组改造
截止目前为止，我们自己封装的数据还是一个静态的数组，但是静态数组有一个问题：每一次在初始化的时候对于数组的初始容量没有办法进行准确的预估，这就导致数组空间开辟过大会产生空间的浪费，开辟的过小又不够用的情况；所以我们需要一种自动的可伸缩的机制来实现数组容量的自动化管理来解决我们的这个问题。
8.1 动态数组图示
通过以上图示可以看出，当数组空间达到上限的时候我们可以创建一个容量更大的新数组，然后使用循环将之前数组中的元素放入新数组中，这样就实现了数组的扩容，就可以解决上面我们提到的静态数组空间的问题；对于删除的操作我们也可以采用这样的机制来实现；不过这个过程需要循环来将原来数组中的数据添加到新的数组中可能对于性能有一定的损耗，我们将在文章的最后来一起探究这个数组的性能问题。
8.2 代码
/**
* 动态数组逻辑(扩容缩容)
* @param newCapacity
*/
private void resize(int newCapacity){
// 创建新的容器
E[] newData = (E[]) new Object[newCapacity];
// 复制数组元素到新的数组
for (int i = 0; i < size; i++){
newData[i] = data[i];
}
// 改变数组索引
data = newData;
}
/**
* 从数组中删除index位置的元素, 返回删除的元素
* @param index
* @return
*/
public E remove(int index){
if (index < 0 || index >= size){
throw new IllegalArgumentException("Remove failed, index is illegal.");
}
// 记录被删除的元素
E res = data[index];
// 通过遍历将数组中的元素进行位移
for (int i = index + 1; i < size; i++){
// 索引考后的元素覆盖索引靠前的元素
data[i - 1] = data[i];
}
// 操作数组长度
size--;
// 将数组的最后一个位置上的元素置为空
data[size] = null;
// 数组缩容逻辑
if (size == data.length / 4 && data.length / 2 != 0){
// 执行数组缩容
resize(data.length / 2);
}
// 返回记录结果
return res;
}
/**
* 在index索引的位置插入一个新元素e
* @param index
* @param e
*/
public void add(int index, E e){
// 判断索引是不是合法
if (index < 0 || index > size){
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
// 判断当前长度是不是大于数组长度,如果大于则进行扩容
if (size >= data.length){
resize(data.length * 2);
}
// 通过遍历将数组中的元素进行位移
for (int i = size - 1; i >= index; i--){
data[i + 1] = data[i];
}
// 将新添加的元素放入到数组指定的索引位置上
data[index] = e;
// 操作数组长度增加1
size++;
}
三 完整版代码
package com.arrays.array;
/**
* Created by yangxiaokai on 2018/5/27.
*/
public class Array<E> {
private E[] data;
private int size;
/**
* 构造函数，传入数组的容量capacity构造Array
* @param capacity
*/
public Array(int capacity){
// 创建数据，长度为capacity
data = (E[]) new Object[capacity];
// 长度为0
size = 0;
}
/**
* 无参数的构造函数，默认数组的容量capacity=10
*/
public Array(){
// 默认数组长度为10
this(10);
}
/**
* 获取数组的容量
* @return
*/
public int getCapacity(){
return data.length;
}
/**
* 获取数组中的元素个数
* @return
*/
public int getSize(){
return size;
}
/**
* 返回数组是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 向所有元素后添加一个新元素
* @param e
*/
public void addLast(E e){
add(size,e);
}
/**
* 在所有元素前添加一个新元素
* @param e
*/
public void addFirst(E e){
add(0,e);
}
/**
* 在index索引的位置插入一个新元素e
* @param index
* @param e
*/
public void add(int index, E e){
// 判断索引是不是合法
if (index < 0 || index > size){
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
// 判断当前长度是不是大于数组长度,如果大于则进行扩容
if (size >= data.length){
resize(data.length * 2);
}
// 通过遍历将数组中的元素进行位移
for (int i = size - 1; i >= index; i--){
data[i + 1] = data[i];
}
// 将新添加的元素放入到数组指定的索引位置上
data[index] = e;
// 操作数组长度增加1
size++;
}
/**
* 获取索引index上的元素
* @param index
* @return
*/
public E get(int index){
if (index < 0 || index >= size){
throw new IllegalArgumentException("Get failed, index is illegal.");
}
return data[index];
}
/**
* 设置索引index上的元素
* @param index
* @param e
*/
public void set(int index, E e){
if (index < 0 || index >= size){
throw new IllegalArgumentException("Set failed, index is illegal.");
}
data[index] = e;
}
/**
* 查询数组中是否包含元素e
* @param e
* @return
*/
public boolean contains(E e){
// 遍历数组查找元素
for (int i = 0; i < size; i++){
if (data[i].equals(e)){
return true;
}
}
return false;
}
/**
* 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
* @param e
* @return
*/
public int find(E e){
// 遍历数组查找元素
for (int i = 0; i < size; i++){
if (data[i].equals(e)){
// 返回索引
return i;
}
}
return -1;
}
/**
* 从数组中删除index位置的元素, 返回删除的元素
* @param index
* @return
*/
public E remove(int index){
if (index < 0 || index >= size){
throw new IllegalArgumentException("Remove failed, index is illegal.");
}
// 记录被删除的元素
E res = data[index];
// 通过遍历将数组中的元素进行位移
for (int i = index + 1; i < size; i++){
// 索引考后的元素覆盖索引靠前的元素
data[i - 1] = data[i];
}
// 操作数组长度
size--;
// 将数组的最后一个位置上的元素置为空
data[size] = null;
// 数组缩容逻辑
if (size == data.length / 4 && data.length / 2 != 0){
// 执行数组缩容
resize(data.length / 2);
}
// 返回记录结果
return res;
}
/**
* 从数组中删除第一个索引上的元素并返回被删除的元素
* @return
*/
public E removeFirst(){
return remove(0);
}
/**
* 从数组中删除最后一个索引上的元素并返回被删除的元素
* @return
*/
public E removeLast(){
return remove(size - 1);
}
/**
* 从数组中删除指定元素
* @param e
*/
public void removeElement(E e){
// 查询数组中是否有此元素
int index = find(e);
// 根据结果判断
if (index != -1){
remove(index);
}
}
/**
* toString
* @return
*/
@Override
public String toString(){
// 创建新的容器
StringBuilder builder = new StringBuilder();
// 设置数组格式
builder.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
// 拼接返回值
builder.append("[");
for (int i = 0; i < size; i++){
// 向容器中添加元素
builder.append(data[i]);
// 判断是否大于容器长度
if (i != size -1){
// 拼接分隔符
builder.append(", ");
}
}
// 闭合
builder.append("]");
// 返回
return builder.toString();
}
/**
* 动态数组逻辑(扩容缩容)
* @param newCapacity
*/
private void resize(int newCapacity){
// 创建新的容器
E[] newData = (E[]) new Object[newCapacity];
// 复制数组元素到新的数组
for (int i = 0; i < size; i++){
newData[i] = data[i];
}
// 改变数组索引
data = newData;
}
}
