转载

纯数据结构Java实现(1/11)(动态数组)

我怕说这部分内容太简单后，突然蹦出来一个大佬把我虐到哭，还是悠着点，踏实写

大致内容有: 增删改查，泛型支持，扩容支持，复杂度分析。(铺垫: Java语言中的数组)

基础铺垫

其实没啥好介绍的，顺序存储，(非受限的)线性结构。查询O(1)，因为支持随机存取。

Java中的数组

Java 中的数组操作，大致如下:

int[] arr = new int[10]

String[] strArr = new String[9]

// 定义的时候就有初始值 --- 自动感知数组长度
int[] scores = new int[]{100, 99, 88}

//获取数组的长度
arr.length

//for each 循环 (数组是可迭代对象)
for(int s in arr){
    System.out.println(s)
}

但不同于 Python 这类动态脚本语言，Java中的数组 只能存储相同类型的元素 。 

数组长度

自己实现

先别管动态扩容的部分，现在就看数组这个容器，如何实现增删改查

大体思路

其实就是内部封装一个 int[] 数组，为了方便，顺便需要一个长度属性。 

package array;

public class MyArray {
    //先声明一下相应的变量, 不暴露给外部 (内部维护保持两者一致)
    private int[] data; //capacity 就是 data 的 length
    private int size;

    // 构造函数，传入数组容量
    public MyArray(int capacity) {
        data = new int[capacity];
        size = 0; //初始情况下，实际有 0 个元素
    }

    //提供一个默认的吧, 不需要用户手动提供 capacity, 无参
    public MyArray() {
        this(10);
    }


    //获取数组元素个数
    public int getSize() {
        return size;
    }

    //返回动态数组的容量
    public int getCapacity() {
        return data.length;
    }

    //数组此刻是否为空
    public boolean isEmpty() {
        return size == 0;
    }

}
  • capacity 容量，数组实际装了多少，用 size 表示
  • capacity 可以用内部数组的长度表示，及 data.length

上面就是整体的框架。(还没有涉及动态扩容)

增删改查

因为赶时间，所以增删改查一起来。

添加元素

此时 size 应该指向的是，要添加元素的下一个位置。即尾部添加时 size++ 。

简单想: 一开始没有元素，size 在 0 位置，即第一个元素的位置。

尾部添加:

public void append(int elem) {
    //TODO: 考虑一下是否超过容量
    if (size == data.length) {
      throw new IllegalArgumentException("append failed");
    }
    this.data[size++] = elem;
}

//如果实现了 insert(key, elem) 方法，可以直接写成
//末尾添加
public void append(int elem) {
     insert(size, elem);
}

指定位置添加:

//指定位置插入
public void insert(int index, int elem) {
  //TODO: 考虑一下是否超过容量
  if (size == data.length) {
    throw new IllegalArgumentException("append failed");
  }
  //检查 index 是合法的
  if(index < 0 || index > size){
    throw new IllegalArgumentException("insert failed, require: index >=0 and index <= size ");
  }

  //先移动元素，从后面开始 (size-1 移动到 size --> index 移动到 index+1；腾出 index)
  for(int i = size-1; i>=index; i--){
    data[i+1] = data[i];
  }
  data[index] = elem; //覆盖原来的 index 处的内容
  size++;
}

注意一下，要维护 size 。

头部添加:

此时就可以复用 insert 方法了:

//头部添加
public void presert(int elem){
  insert(0, elem);
}

遍历元素

其实就是遍历内部封装的数组，找到相应的元素。

获取整体: （覆写 toString 这个方法） 

//获取数组整体，即打印时需要显示的信息
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("MyArray: size=%d, capacity=%d/n", size, data.length));

        res.append("[");
        //只遍历现有元素，而不是容量
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if(i != size-1){
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }

测试看看:

import array.MyArray;

public class Main {

    public static void main(String[] args) {
        MyArray arr = new MyArray(20); //容量20
        //放入 10 个元素
        for(int i=0; i< 10; i++){
            arr.append(i);
        }
        System.out.println(arr);
      
        arr.insert(1, 100);
        System.out.println(arr);      
    }
}

//输入结果如下:
MyArray: size=10, capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
MyArray: size=11, capacity=20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]

取出具体元素 (getter)

按照索引取。

//获取某个具体元素: 通过封装，加入自定义 index 检查(保证获取数据安全)
public int get(int index) {
  if (index < 0 || index >= size) {
    throw new IllegalArgumentException("Get failed, Index is illegal");
  }
  return data[index];
}

修改元素 (setter)

按照索引修改。

//更新元素
public void set(int index, int elem) {
  if (index < 0 || index >= size) {
    throw new IllegalArgumentException("Get failed, Index is illegal");
  }
  data[index] = elem;
}

是否包含

线性遍历一遍，看看是否存在

//是否包含
public boolean contains(int elem) {
  for (int i = 0; i < size; i++) {
    if (data[i] == elem) {
      return true;
    }
  }
  return false;
}

搜索元素

还是线性搜索一下，找到就返回下标

public int find(int elem){
  for(int i=0; i<size; i++){
    if(data[i] == elem){
      return i;
    }
  }
  return -1; //没有找到返回 -1
}

删除元素

删除就是覆盖，大致分为两类: 按照索引删除，按照元素删除。

从 index 开始到 size-1，不断往前赋值，最后维护一下整体的 size-— 。

(size的元素用户是拿不到的，所以data[size]值不必担心)

//删除元素 (通常要返回相应的元素)
public int remove(int index) {
  if (index < 0 || index >= size) {
    throw new IllegalArgumentException("Remove failed, Index is illegal");
  }
  //先把要返回的值存储起来
  int ret = data[index];
  //覆盖删除: 把 index+1 的值移动到 index --> 把 size-1 的值移动到 size-2
  for (int i = index + 1; i < size; i++) {
    data[i - 1] = data[i];
  }
  size--;
  //data[size] 不必清空，因为用户取不到 data[size]

  return ret;
}

当然也可以补充一些快捷方法:

//快捷删除尾部元素
public int pop(){
  return remove(size-1);
}
//快捷删除头部元素
public int popLeft(){
  return remove(0);
}

按照元素删除: 先查找，然后删除 

//删除指定元素 (不必返回，因为用户已经知道 elem)
public void removeElem(int elem){
  int index = find(elem);
  if(-1 == index) {
    throw new IllegalArgumentException("Remove failed, cannot find this elem");
  }
  //成功了什么都不提示，出错才提示
  remove(index);
}
  • 默认都是查找，删除第一个找到的元素

简单测试一下，删除:

//[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
//删除试试
arr.remove(1);
System.out.println(arr); //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

//删除末尾试试
arr.pop();
System.out.println(arr); //[0, 1, 2, 3, 4, 5, 6, 7, 8]

//删除头部试试
arr.popLeft();
System.out.println(arr); //[1, 2, 3, 4, 5, 6, 7, 8]

//删除 4 这个数字
arr.removeElem(4);
System.out.println(arr); //[1, 2, 3, 5, 6, 7, 8]

泛型支持

语法限制

由于泛型的限制(不能放入基本类型，只能放入其包装类)，内部封装的数组初始化的时候需要强制类型转换一下。

也就是说， 可以用于声明，但不能用于定义 。 

data = new E[capacity]; //报错，历史遗留问题，不支持该语法

//正确的写法 (借助强制类型转换)
data = (E[])new Object[capacity];

完整代码

特别注意一下:

  • 对象值的比较，需要改成 equals
  • 删除的时候，因为存储的是对象的引用，所以应该把移动后的 data[size] 位置设置为 NULL
    • 但是这一条是非必须，因为 闲逛对象 != memory leak

还是贴一下，支持泛型的完整代码吧:

package array;

public class AdvanceArray<E> {

    //先声明一下相应的变量, 不暴露给外部 (内部维护保持两者一致)
    private E[] data; //capacity 就是 data 的 length
    private int size;

    // 构造函数，传入数组容量
    public AdvanceArray(int capacity) {
        data = (E[])new Object[capacity];
        size = 0; //初始情况下，实际有 0 个元素
    }

    //提供一个默认的吧, 不需要用户手动提供 capacity, 无参
    public AdvanceArray() {
        this(10);
    }


    //获取数组元素个数
    public int getSize() {
        return size;
    }

    //返回动态数组的容量
    public int getCapacity() {
        return data.length;
    }

    //数组此刻是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //末尾添加
    public void append(E elem) {
        insert(size, elem);
    }

    //头部添加
    public void presert(E elem) {
        insert(0, elem);
    }

    //指定位置插入
    public void insert(int index, E elem) {
        //TODO: 考虑一下是否超过容量
        if (size == data.length) {
            throw new IllegalArgumentException("append failed");
        }
        //检查 index 是合法的
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("insert failed, require: index >=0 and index <= size ");
        }

        //先移动元素，从后面开始 (size-1 移动到 size --> index 移动到 index+1；腾出 index)
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = elem; //覆盖原来的 index 处的内容
        size++;
    }

    //获取数组整体，即打印时需要显示的信息
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("MyArray: size=%d, capacity=%d/n", size, data.length));

        res.append("[");
        //只遍历现有元素，而不是容量
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i != size - 1) {
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }

    //获取某个具体元素: 通过封装，加入自定义 index 检查(保证获取数据安全)
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed, Index is illegal");
        }
        return data[index];
    }

    //更新元素
    public void set(int index, E elem) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed, Index is illegal");
        }
        data[index] = elem;
    }

    //是否包含
    public boolean contains(E elem) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(elem)) {
                return true;
            }
        }
        return false;
    }

    //搜索元素
    public int find(E elem) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(elem)) {
                return i;
            }
        }
        return -1; //没有找到返回 -1
    }

    //删除元素 (通常要返回相应的元素)
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed, Index is illegal");
        }
        //先把要返回的值存储起来
        E ret = data[index];
        //覆盖删除: 把 index+1 的值移动到 index --> 把 size-1 的值移动到 size-2
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }

        size--;
        //data[size] 不必清空，因为用户取不到 data[size]
        //当使用泛型，对对象元素支持时
        data[size] = null; //方便 java 回收 loitering objects (非必须，闲逛对象 != memory leak)
        return ret;
    }

    //快捷删除尾部元素
    public E pop() {
        return remove(size - 1);
    }

    //快捷删除头部元素
    public E popLeft() {
        return remove(0);
    }

    //删除指定元素 (不必返回，因为用户已经知道 elem)
    public void removeElem(E elem) {
        int index = find(elem);
        if (-1 == index) {
            throw new IllegalArgumentException("Remove failed, cannot find this elem");
        }
        //成功了什么都不提示，出错才提示
        remove(index);
    }
}

测试代码如下:

//这个类主要用于 AdvanceArray 做泛型测试
public class Student {
    private String name;
    private int score;

    public Student(String studentName, int studentScore){
        name = studentName;
        score = studentScore;
    }

    @Override
    public String toString() {
        return String.format("Student(name: %s, score: %d)", name, score);
    }
}


// main.java 中:
public class Main {
    private static void test_2(){
        //泛型不支持基本类型，所以这里写 Integer；使用时会自动box，unbox
        AdvanceArray<Integer> arr = new AdvanceArray<>(20); //容量20
        //放入 10 个元素
        for (int i = 0; i < 10; i++) {
            arr.append(i);
        }
        System.out.println(arr);

        //插入试试
        arr.insert(1, 100);
        System.out.println(arr);

        //[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        //删除试试
        arr.remove(1);
        System.out.println(arr); //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

        //删除末尾试试
        arr.pop();
        System.out.println(arr); //[0, 1, 2, 3, 4, 5, 6, 7, 8]

        //删除头部试试
        arr.popLeft();
        System.out.println(arr); //[1, 2, 3, 4, 5, 6, 7, 8]

        //删除 4 这个数字
        arr.removeElem(4);
        System.out.println(arr); //[1, 2, 3, 5, 6, 7, 8]
    }

    private static void test_3(){
        AdvanceArray<Student> arr = new AdvanceArray<>(); //默认容量是 10
        //添加测试数据
        arr.append(new Student("AAA", 100));
        arr.append(new Student("BBB", 90));
        arr.append(new Student("CCC", 60));

        System.out.println(arr);
    }
}

// 测试结果
MyArray: size=3, capacity=10
[Student(name: AAA, score: 100), Student(name: BBB, score: 90), Student(name: CCC, score: 60)]

动态支持

上面其实没有支持动态扩容，也就不能称为一个 动态数组

上面的做法是，一旦检测到索引异常，基本都抛异常结束流程了；正常索引就插入，但没有考虑插入之后超过容量了怎么办？（在容量满的时候就应该检测到了）

解决方案，最基本的就是:

  • 1.开辟新空间
  • 2.把元素复制过去

但这只是扩容支持，如果元素缩减到一定程度，那么也应该减少容量。

增加扩容

//主要就是修改 insert 函数
public void insert(int index, E elem) {
  //检查 index 是合法的
  if (index < 0 || index > size) {
    throw new IllegalArgumentException("insert failed, need: index >=0 and index <= size ");
  }

  //满了，那么就扩容吧 -- 这里不再是抛异常对象了
  if (size == data.length) {
    resize(2 * data.length); //java arraylist 选择的是 1.5 倍
  }

  //先移动元素，从后面开始 (size-1 移动到 size --> index 移动到 index+1；腾出 index)
  for (int i = size - 1; i >= index; i--) {
    data[i + 1] = data[i];
  }
  data[index] = elem; //覆盖原来的 index 处的内容
  size++;
}

private void resize(int newCapacity) {
  E[] newData = (E[]) new Object[newCapacity];
  //复制旧元素过去
  for (int i = 0; i < size; i++) {
    newData[i] = data[i];
  }
  data = newData;
}

简单测试一下:

//初始容量为 10，先初始化 10 个元素
AdvanceDynamicArray<Integer> arr = new AdvanceDynamicArray<>(); //初始容量默认为 10
for (int i = 0; i < 10; i++) {
  arr.append(i);
}
System.out.println(arr);

//再添加一个元素，试试
arr.append(100);
System.out.println(arr);

//输出结果:
MyArray: size=10, capacity=10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
MyArray: size=11, capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 100]

删除缩减

删除元素的之后，如果空间小到一定程度，自动缩减空间

  • 只要就是在删除后，做一下 size 和 capacity 的判断，然后 resize

(即删除后，size 为 capacity 的一半就可以缩容了)

//初始容量为 10，先初始化 10 个元素
AdvanceDynamicArray<Integer> arr = new AdvanceDynamicArray<>(); //初始容量默认为 10
for (int i = 0; i < 10; i++) {
  arr.append(i);
}
System.out.println(arr);

//再添加一个元素，试试 -- 此时容量变为 20，实际占用 11
arr.presert(100);
System.out.println(arr);

//pop一个，容量立马缩减为 10
arr.pop();
System.out.println(arr);

//运行结果为:
MyArray: size=10, capacity=10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
MyArray: size=11, capacity=20
[100, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
MyArray: size=10, capacity=10
[100, 0, 1, 2, 3, 4, 5, 6, 7, 8]

最后，扩容或者删除容量，对于 client 而言，它并不知道。( 扩容策略也可以在细致些 )

复杂度分析

O(1) -> O(logn)优良 —> O(n) 一般 —> O(nlogn) 一般般,其实和O(n)差不太多 —> O(n^2) 差 —>O(C^n) 超差

一般谈起来，会说和运行规模成: 常数关系，对数关系，线性关系，nlogn，平方关系，指数关系。简单理解就是，级大一级压死人。

详细分析

添加操作:

  • 末尾插入 append: O(1)

  • 头添加 presert: O(n)

  • 任意位置插入 insert(index): 在 O(1) 和 O(n) 之间，假设 index 的取值概率一样，index 靠前的时候越慢，越靠后越快，整体需要靠具体需要移动多少个元素，n + (n-1) + … + 0，n 种情况，平均需要移动的元素 n/2，所以复杂度是 O(n/2)，即 O(n)

resize 的操作也是 O(n)。

(尾部操作也可能是 O(n)，但几率比较小，不可能每次都触发 resize)

综上所述，以最差来考虑，即 O(n)。 (一般考虑的是 概率最高的情况 )

删除操作: (其实分析方法类似，核心因素还是元素的移动)

  • 末尾删除 pop(): O(1)
  • 头删除 popLeft(): O(n) 因为元素要往前面移动
  • 任意位置，平均 remove(index): O(n/2)，即 O(n)

resize 的操作也是 O(n)。

(头部操作也可能是 O(n)，但几率比较小，不可能每次都触发 resize)

综上所述，以最差来考虑，即 O(n)。

修改操作: 因为可以支持随机访问(按地址，索引)，所以复杂度 O(1)

查找操作:

  • get(index): O(1)
  • contains(e): O(n) 线性遍历
  • find(e): O(n) 线性遍历

从上面也可以看出，时间复杂度和顺序存储情况一致。

均摊复杂度

也就是仔细考虑一下包含这个 扩容 & 缩容 耗时操作的 remove/insert 到底应该算作 O(1) 还是 O(n)。

比如 addLast() 本来是 O(1)，加入动态支持后，此时还是 O(1) 么。

显而易见，容易得证:

假设 capacity = n，那么进行 n+1 次 addLast，触发扩容，此时包括移动元素，总共操作 2n+1 次，也就是说平均每次 addLast 触发 (2n+1)/(n+1) 即 2 次操作，即常量次操作，所以 addLast() 算均摊，也是 O(1)。

震荡优化

刚添加一个元素，扩容；立马删除一个元素，又缩容

连环的 addLast 和 removeLast 导致最近的操作都是 O(n)。(常规而言是O(1)的)

此时就要延迟处理(lazy)缩容，即真实元素为 1/4 capacity时才容量减半。

代码如下:

//删除元素 (通常要返回相应的元素)
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed, Index is illegal");
        }
        //先把要返回的值存储起来
        E ret = data[index];
        //覆盖删除: 把 index+1 的值移动到 index --> 把 size-1 的值移动到 size-2
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }

        size--;
        //data[size] 不必清空，因为用户取不到 data[size]
        //当使用泛型，对对象元素支持时
        data[size] = null; //方便 java 回收 loitering objects (非必须，闲逛对象 != memory leak)

        //缩减 (只在一个特定的时机缩减，不能用 < 或者 >，可能会存在多次缩减)
        //注意一下，延迟缩减，即 1/4 时，才缩减为一半 (还有一半是空的)
        if(size == data.length/4 && data.length/2 != 0) {
            resize(data.length/2); //那么就缩减为一半
        }
        return ret;
    }

上面有个技巧或者编程语言问题， data.length/2 != 0 ，因为 java 的除法默认是截断的，即可能出现 capacity 为 0 的情况。比如，当前capacity = 1 即 data.length 为 1，即便 size=0，也不能再缩减了(否则执行缩减， capacity 就为 0了)。

总结

顺序存储的结构，不管是不是线性的，基本都有这些操作特征，只不过上层接口隐藏了实现细节，比如 顺序栈 这类受限的结构，底层就是封装了动态数组(而非原始数组了)。

实现的时候注意移动操作从哪里开始，索引合法性判断以及记得维护 size。

深怕有人需要这些粗鄙的代码，我还是把它放在了 gayhub 上，供您参考。

如有不足之处，万望批评指正，虾虾侬。

原文  http://www.cnblogs.com/bluechip/p/self-pureds-vector.html
正文到此结束
所属分类： Java 编程技术

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
springboot-demo Java入门教程 bootstrap3 CSS Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 MongoDB教程 Struts2教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 Hive教程 Ant教程 ANTLR教程 SpringCloud java实例教程 springcloud-demo XStream教程 Hazelcast教程 Elastic-Job-Lite 深入浅出MyBatis SVN教程 ibaties教程 rabittmq教程 solr教程 Hadoop教程 WebService CXF学习 JPA教程 ActiveMQ中文指南 java-demo Java内存模型 dubbo教程 python3-demo Linux入门视频教程
近期评论
  1. 1 Spring Cloud Consul实现选举机制
  2. 2 Spring Boot集成ShedLock实现分布式定时任务
  3. 3 利用oss进行数据库和网站图片备份
  4. 4 Spring Cloud Stream实现数据流处理
  5. 5 Python3访问MySQL数据库快速入门Demo
  6. 6 Github开源项目作者可以免费申请 JetBrains 全家桶
  7. 7 Spring Cloud Vault快速入门Demo
  8. 8 Spring Cloud Gateway快速入门Demo
  9. 9 Spring Cloud Contract快速入门Demo
  10. 10 Spring Cloud Consul快速入门Demo
网站信息
  • 文章总数：82,714 篇
  • 文件总数：284,287 个
  • 标签总数：2,393 个
  • 分类总数：85 个
  • 留言数量：2,560 条
  • 在线人数：696 人
  • 运行天数：4,408天
  • 最后更新：2024年11月21日23点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG