朴素数组表(Java语言)¶

朴素数组表 ( Naive Array List )是本文自创的名词，表示一种 最直观最原始 的数组表。

类实现¶

首先定义一个 NaiveArrayList 类，有两个私有成元变量：

listSize ，表示当前表中已存储的元素个数；
listItems ，用于存储元素的数组，大小固定；

public class NaiveArrayList {
    private int listSize;
    private int[] listItems;
}

构造函数¶

构造函数在创建该类对象时调用，作用是初始化类对象。

NaiveArrayList 构造函数接收一个参数 capacity ，指定了数组大小，即数组表的容量。函数体先创建一个指定大小的数组，并将元素个数初始化为 0 。

public NaiveArrayList(int capacity) {
    listItems = new int[capacity];
    listSize = 0;
}

容量与大小¶

容量¶

capacity 返回数组表的容量，即底层数组的大小：

public int capacity() {
    return listItems.length;
}

大小¶

size 方法返回数组表已存储的元素个数，即 listSize ：

public int size() {
    return listSize;
}

是否为空¶

isEmpty 方法在数组表为空，即 size 为 0 时，返回 true ：

public boolean isEmpty() {
    return size() == 0;
}

是否已满¶

isFull 方法在数组表已满，即 size 等于 capacity 时，返回 true ：

public boolean isFull() {
    return size() == capacity();
}

增删改查¶

查¶

get 方法根据给定下标( index )，查找对应元素并返回：

public int get(int idx) {
    // index out of bounds
    if (idx < 0 || idx >= size()) {
        throw new ArrayIndexOutOfBoundsException();
    }

    return listItems[idx];
}

第 3-5 行，先判断下标是否超出有效范围，超出则抛异常；
第 7 行，以给定下标取回数组中的元素；

改¶

set 方法为给定下标元素设置新值，并返回旧值：

public int set(int idx, int newVal) {
    // index out of bounds
    if (idx < 0 || idx >= size()) {
        throw new ArrayIndexOutOfBoundsException();
    }

    // store old value for returning
    int oldVal = listItems[idx];
    listItems[idx] = newVal;

    return oldVal;
}

函数逻辑与 get 方法类似，注意到第 8 行先暂存旧值用于返回。

增¶

add 方法在指定下标处添加新元素，如果该位置已被占用，需将相关元素往后挪：

public void add(int idx, int x) {
    // there's no space left
    if (isFull()) {
        throw new ArrayOutOfCapacity();
    }

    // shift items behind backward
    for (int i = size() - 1; i >= idx; i--) {
        listItems[i+1] = listItems[i];
    }

    // store new item
    listItems[idx] = x;
    listSize++;
}

第 3-5 行，判断数组表是否已满，满则抛异常；
第 8-10 行，将该位置(如有)以及其后所有元素往后挪一个位置；
第 13-14 行，将新元素存储到指定位置，并自增 listSize ；

实现另一个版本的 add 方法，无须指定下标，将新元素添加到末尾：

public void add(int x) {
    add(size(), x);
}

注意到， size() 为底层数组下一个可用位置。

删¶

remove 方法将指定下标元素从表中删除，并将其返回：

public int remove(int idx) {
    // index out of bounds
    if (idx < 0 || idx >= size()) {
        throw new ArrayIndexOutOfBoundsException();
    }

    // store value for returning
    int value = listItems[idx];

    // shift items behind forward
    for (int i = idx + 1; i < size(); i++) {
        listItems[i-1] = listItems[i];
    }

    listSize--;

    return value;
}

第 3-5 行，先判断下标是否超出有效范围，超出则抛异常；
第 8 行，暂存待删除元素，以便向调用者返回；
第 11-13 行，将被删除元素后面所有元素往前挪一个位置；
第 15 行，自减 listSize ；
第 17 行，返回被删除元素；

辅助方法¶

打印¶

print 方法将数值表所有元素打印出来：

public void print(String hint) {
    System.out.printf("%s[ ", hint);

    for (int i = 0; i < listSize; i++) {
        System.out.printf("%s ", listItems[i]);
    }

    System.out.printf("]\n");
}

该方法接收一个参数 hint ，用于区分不同时机的打印。

时间复杂度¶

类应用¶

下面，实现一个 main 函数，考察 NaiveArrayList 类的用法：

public static void main(String args[]) {
    NaiveArrayList list = new NaiveArrayList(10);
    list.print("After init: ");
    System.out.println();

    list.add(1);
    list.add(2);
    list.add(3);

    list.print("After add 1, 2, 3: ");
    System.out.printf("#1 is: %d\n", list.get(1));
    System.out.println();

    list.add(0, -1);
    list.print("After insert -1: ");
    System.out.println();

    list.remove(1);
    list.print("After remove #1: ");
    System.out.println();

    list.add(4);
    list.print("After append 4: ");
    System.out.println();

    for (int i = 5; i < 20; i++) {
        list.add(i);
        list.print("After append i: ");
        System.out.println();
    }
}

第 2 行，实例化一个容量为 10 的数组表，最多可存储 10 个整数元素；
第 3-4 行，将数组表输出，确认其为空；
第 6-8 行，依次将 1 、 2 、 3 添加到数组表；
第 10-11 行，将数组表输出确认添加效果，并查询小标为 1 的元素；
第 14 行，将 -1 添加到位置 0 ；
第 18 行，将存储在位置 1 的元素删除；
第 22 行，将元素 4 添加到末尾；
第 26-30 行，循环添加元素，确认超出容量后抛异常；

运行¶

执行 javac 命令编译程序：

$ javac NaiveArrayList

执行 java 命令运行程序：

$ java NaiveArrayList

程序输出如下：

After init: [ ]

After add 1, 2, 3: [ 1 2 3 ]
#1 is: 2

After insert -1: [ -1 1 2 3 ]

After remove #1: [ -1 2 3 ]

After append 4: [ -1 2 3 4 ]

After append i: [ -1 2 3 4 5 ]

After append i: [ -1 2 3 4 5 6 ]

After append i: [ -1 2 3 4 5 6 7 ]

After append i: [ -1 2 3 4 5 6 7 8 ]

After append i: [ -1 2 3 4 5 6 7 8 9 ]

After append i: [ -1 2 3 4 5 6 7 8 9 10 ]

Exception in thread "main" ArrayOutOfCapacity: Array out of capacity
                at NaiveArrayList.add(NaiveArrayList.java:56)
                at NaiveArrayList.add(NaiveArrayList.java:70)
                at NaiveArrayList.main(NaiveArrayList.java:131)
make: *** [run] Error 1

下一步¶

订阅更新，获取更多学习资料，请关注我们的微信公众号：

小菜学编程