2.数组与列表-java

什么是数组?

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

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

数组如何实现随机访问?

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

image

插入操作

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

如果元素无序,可直接换位:

删除操作

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

预删除思想: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);
    }

}