2.数组与列表-java

霍格沃兹测试学院校内交流
1

什么是数组？

数组是线性表数据结构。用连续的内存空间存储相同类型的数据。

  • 线性表：线性表是数据排成一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。
    包括：数组，链表、队列、栈。
  • 非线性表：数据之间并不是简单的前后关系。
    包括：二叉树、堆、图等。
  • 连续的内存空间和相同类型的数据：使数组支持“随机访问”。但在数组中删除、插入数据时，需要做大量的数据搬移工作。

数组如何实现随机访问？

C 语言代码： int[] tmp = new int[4]，这个数组在内存中连续放置：

image

插入操作

  • 在数组末尾插入元素，不需要移动数据，时间复杂度为 O(1)。
  • 在数组开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 O(n)。
  • 假设每个位置插入元素概率相同，平均情况时间复杂度为 (1+2+…n)/n=O(n)。

image
image846×290 1.17 KB

如果元素无序，可直接换位：

删除操作

  • 删除数组末尾数据：则最好情况时间复杂度为 O(1)；
  • 删除开头的数据：则最坏情况时间复杂度为 O(n)；
  • 平均情况时间复杂度也为 O(n)。

image
image846×290 1.17 KB

预删除思想：JVM 标记清除垃圾回收算法

改进数组

编程语言封装了数组，比如 Java 的 ArrayList， Python 的 List ，可实现自动扩容，多种数据类型组合。

如果你是底层工程师，需要极致的比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

实现方法-1

import java.util.Arrays;

import org.graalvm.compiler.core.common.alloc.Trace;

public class Array {
    public int[] data;
    private int n;
    private int count;

    public Array(int capacity) {
        data = new int[capacity];
        n = capacity;
        count = 0;

    }

    public boolean insert(int location, int value) {
        if (n == count) {
            return false;   
        }

        if (location < 0 || location > count) {
            return false;
        }
        
        for (int i = count; i > location; i--) {
            data[i] = data[i-1];
        }

        data[location] = value;
        count++;
        return true;
    }

    public int find(int location) {
        if (location < 0 || location >= count) {
            return -1;
        }

        return data[location];
    }

    public boolean delete(int location) {
        if (location < 0 || location >= count) {
            return false;
        } 

        for (int i = location + 1; i < count; i++) {
            data[i-1] = data[i]; 
        }

        count--;
        return true;

        
    }

    public static void main(String[] args) {
        Array array = new Array(5);
        array.insert(0, 1);
        array.insert(0, 2);
        array.insert(1, 3);
        array.insert(2, 4);
        array.insert(4, 5);
        // 判断插入不成功
        assert !array.insert(0, 100);
        assert array.find(0) == 2;
        assert array.find(2) == 4;
        assert array.find(4) == 5;
        assert array.find(10) == -1;
        assert array.count == 5;
        boolean removed = array.delete(4);
        assert removed;
        assert array.find(4) == -1;
        removed = array.delete(10);
        assert !removed;
        // 2 3 4 1 5
        int[] tmp = new int[] { 2, 3, 4, 1, 5 };
        assert Arrays.equals(array.data, tmp);
    }

}
2
3