数组这种数据结构的基本实现
Contents
1 为什么数组元素下标从0开始？
回答这个问题之前，先了解一下数组的特性：
首先，数组这种数据类型，在内存中是申请一片连续的存储空间。比如：如果每个数组元素占据1MB内从空间，申请长度为1000的数组，则内存中必须得有连续的1000MB的可用空间，否则数组分配空间申请失败。对比来看，如果申请的是一个链表的话，只要内存中的可用空间有1000MB即可，并不要求这些存储空间一定是连续的。
正是因为这种要求内存空间是连续的性质，就衍生出数组这种数据类型可以根据元素的索引下标快速定位元素，且其时间复杂度是O(1)。这是怎么实现的呢？因为内存连续，假定第1个元素内存地址为1000，每个元素占4个字节，那么，现在我想要访问第100个元素的话，则可以快速计算出内存地址=首元素地址+(100-1)*4=1396。更进一步，如果规定索引下标从0开始，那么要访问第100个元素的话，其实是要获取第99个元素。此时，其内存地址=首元素地址+99X4=1396。相比较而言，CPU就少了一次减法运算。
其次，数组这种数据类型是单一数据类型，长度固定，不可动态扩展长度。空间开辟小，则不够用，无法扩展，空间开辟大，用不完怎么办，空间浪费。
2 数组不仅是一种数据类型，还是一种数据结构
是的，这是在之前并没有认真认识到的一种数据结构，原来数组本身就是一种数据结构，还是一种非常常用的基础数据结构。
3 自己手写一个数组类
/**
* @Author:asher
* @Date:2021/3/26 20:28
* @Description:PACKAGE_NAME
* @Version:1.0
*/
//自己动手写一个Array类，让其封装一个整型数组
public class Array {
//封装一个int[]数组的成员变量
private int[] data;
//表示数组实际存放的元素个数
private int size;
//构造方法，传入一个整型长度capacity，初始化一个数组
public Array(int capacity) {
data = new int[capacity];
//初始化时，数组分配capacity个存储空间，但是没有存放任何元素，是空数组，size=0;
size = 0;
}
//默认构造方法，初始化长度为10的数组
public Array() {
this(10);
}
//封装一个获取数组实际存放多少个元素的方法
public int getSize() {
return size;
}
//封装一个获取数组总共可以存放多少个元素的方法
public int getCapacity() {
return data.length;
}
//封装一个判断数组是否为空的方法
public boolean isEmpty() {
return size == 0;
}
}4 向数组中添加元素
a 向数组末尾添加元素：
前面，我们在自定义数组类的时候，指定了一个非常好用的成员变量，size，它不但表示当前数组中有几个元素，而且还指向数组中第一个元素为空的位置。比如，当size=3的时候，数组中，此时有3个元素，分别是data[0]，data[1]，data[2]，同时data[3]是空的，该索引位置处没有元素。当我们此时，向数组中添加元素的时候，我们就应该把新元素放到data[3]的位置。所以，我们可以定义一个向数组末尾添加元素的方法：
public void addLast(int e){
//如果数组的实际存放元素个数==数组长度，抛出异常
if( size == data.length){
throw new IllegalArgumentException("addLast failed.Array is full");
}
//否则，将元素e插入到size位置处，同时，size++；
data[size] = e;
size++;
}b 向任意位置添加元素：
public void add(int e,int index){
//判断数组是否满
if(size==data.length){
throw new IllegalArgumentException("数组满,add failed.");
}
//判断插入位置index是否合法
if(index<0||index>=data.length){
throw new IllegalArgumentException("插入位置不合法");
}
//如果插入位置在index取值范围在[0,size]之间，意味着插入位置合法。
//则先将[index,size-1]位置处的元素全部后移一位
if(index<=size){
for(int i=size;i>index;i--){
data[size]=data[size-1];
}
//然后空出index位置，将元素e插入到index位置处,并且size++
//其实，此时i=index,只是离开了变量作用域
data[index]=e;
size++;
}else{
//插入位置在[size+1,length-1],也认为是插入位置不合法，或者此时直接将元素放到size位置处
data[size]=e;
size++;
}
}c 向数组首位置插入元素
有了向数组任意位置插入元素的add(int e,int index)的方法，则可以借用此方法，实现一个向数组首位置插入元素的方法，只需要传入一个位置参数0即可，add(int e,0)
public void addFirst(int e){
add(e,0);
}d 改造向数组末尾添加元素
同时，我们也可以借助add(int e,int index)任意位置插入元素的方法，进而改造。只需，传入位置参数size即可，addLast(int e,size)
e 覆写父类Object的toString()
Java中，任何基本数据类型在打印输出时，编译器会自动将其转化成字符串打印输出。而对于自定义类类型的实例变量，在打印输出时，就需要覆写Object类的toString()方法，否则打印出来的将是该实例变量的内存地址值。其格式大概是：类名@实例变量内存地址。因此，对于我们这个自定义的Array类，我们需要重写toString()。
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("Array size: %d,capacity = %d \n", size, data.length));
stringBuilder.append("[");
//注意，此时遍历的时候，只能到达size位置处，因为可能数组开辟了100个空间的capacity，但是，数组实际存放了size=10个元素
for (int i = 0; i < size; i++) {
stringBuilder.append(data[i]);
//如果没有到达最后一个元素时，则添加一个"空格+,+空格"
if (i != size-1) {
stringBuilder.append(" , ");
}
}
stringBuilder.append("]");
return stringBuilder.toString();
}f 测试addLast(int e)，add(int e,int index)和addFirst(int e)方法
有了toString()方法，我们就可以定义一个main()方法，来分别测试这几个方法。
public static void main(String[] args) {
Array array = new Array(20);
for (int i = 0; i < 10; i++) {
array.addLast(i);
}
System.out.println(array);
array.add(111, 1);
System.out.println(array);
array.addFirst(-1);
System.out.println(array);
}
//输出结果为
Array size: 10,capacity = 20
[0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Array size: 11,capacity = 20
[0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Array size: 12,capacity = 20
[-1 , 0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]5 按元素值查找并返回索引下标
//从数组中查找值等于e的元素，如果找到返回其索引位置，未找到，返回-1
public int find(int e) {
for (int i = 0; i < size; i++) {
if (e == data[i]) {
return i;
}
}
return -1;
}6 按元素值修改元素
//如果数组中存在元素值等于e的元素，则修改它的值为newValue，否则不做任何操作
// 修改数组中元素值等于e的元素为newValue,如果
public void modify(int e, int newValue) {
int temp = find(e);
if (temp != -1) {
data[temp] = newValue;
}
}7 测试按元素值查找和修改元素
public static void main(String[] args) {
Array array = new Array(20);
for (int i = 0; i < 10; i++) {
array.addLast(i);
}
System.out.println(array);
array.add(111, 1);
System.out.println(array);
array.addFirst(-1);
System.out.println(array);
System.out.println("The index of element 1 is:"+array.find(1));
System.out.println("The index of element 18 is:"+array.find(18));
array.modify(9, 999);
System.out.println("After modify element 9 to 999:");
System.out.println(array);
}
//结果
Array size: 10,capacity = 20
[0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Array size: 11,capacity = 20
[0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Array size: 12,capacity = 20
[-1 , 0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
The index of element 1 is:3
The index of element 18 is:-1
After modify element 9 to 999:
Array size: 12,capacity = 20
[-1 , 0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 999]8 按索引下标查找、修改元素
//获取索引位置为index的元素
public int get(int index) {
//如果index<0，或者数组不为空时，index>=size
if (index < 0 || (isEmpty() && index >= size)) {
throw new IllegalArgumentException("get failed,index is invalid.");
}
//否则的话，返回该元素
return data[index];
}
//获取第一个位置元素
public int getFirst(){
return get(0);
}
//获取最后一个位置元素
public int getLast(){
return get(size-1);
}
//修改索引位置为index的元素
public void set(int index,int e) {
//如果index<0，或者数组不为空时，index>=size
if (index < 0 || (isEmpty() && index >= size)) {
throw new IllegalArgumentException("get failed,index is invalid.");
}
//否则的话，直接修改元素
data[index] = e;
}测试：
public static void main(String[] args) {
Array array = new Array(20);
System.out.println(array.get(0));
for (int i = 0; i < 10; i++) {
array.addLast(i);
}
System.out.println(array);
array.add(111, 1);
System.out.println(array);
array.addFirst(-1);
System.out.println(array);
System.out.println("The index of element 1 is:"+array.find(1));
System.out.println("The index of element 18 is:"+array.find(18));
array.modify(9, 999);
System.out.println("After modify element 9 to 999:");
System.out.println(array);
//测试修改索引下标为3的元素为333
array.set(3, 333);
System.out.println(array);
}
//输出
Array size: 10,capacity = 20
[0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Array size: 11,capacity = 20
[0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Array size: 12,capacity = 20
[-1 , 0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
The index of element 1 is:3
The index of element 18 is:-1
After modify element 9 to 999:
Array size: 12,capacity = 20
[-1 , 0 , 111 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 999]
Array size: 12,capacity = 20
[-1 , 0 , 111 , 333 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 999]
//不注释System.out.println(array.get(0));的话， 按预期的抛出异常：
Exception in thread "main" java.lang.IllegalArgumentException: get failed,index is invalid.
at Array.get(Array.java:100)
at Array.main(Array.java:135) 9 判断数组中是否包含元素e
// 判断数组中是否包含元素e
public boolean contains(int e){
for(int i=0;i<size;i++){
if(data[i]==e){
return true;
}
}
return false;
}10 按索引下标删除数组中的元素并返回
public int remove(int index){
if(index<0||index>=size){
throw new IllegalArgumentException("remove failed.index is invalid");
}
//删除之前，把data[index]放入临时变量，删除之后，再返回临时变量
int temp=data[index];
for(int i=index;i+1<size;i++){
data[i]=data[i+1];
}
size--;
return temp;
}
//同理，参照add()方法，有addFist()和addLast(),可以有removeFirst(),removeLast()方法
//删除第1个元素并返回
public int removeFirst() {
return remove(0);
}
//删除最后1个位置元素并返回
public int removeLast() {
return remove(size - 1);
}11 按元素值删除数组中的元素
借助前面定义的查找方法find()，按索引下标删除的方法remove()，是否包含元素的方法contains()，可以实现删除特定元素的方法，以及删除数组中所有的特定元素。
//删除指定元素e
public void removeElement(int e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}
//删除所有的指定元素e
public void removeAllElement(int e) {
//如果数组中包含特定元素，就一直删
while (contains(e)) {
//删除哪个元素呢？删除特定索引位置的元素，这个特定索引位置通过find()方法得到
remove(find(e));
}
}12小结
我们通过自己动手写了一个数组类，并添加了增删改查的方法。这个数组还有一些局限性，比如不能支持任意类型的数据，长度不支持动态扩展。下一篇文章中着手将这个数组改写为支持泛型的数组。
2条评论
Pingback:
Pingback: