数据结构——数组

数组定义：

 在计算机科学中，数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识。

因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来。

性能空间占用

java中所有对象的大小都是8字节的整数倍，不足的要用对齐字节补足

随机访问

即根据索引查找元素，时间复杂度是O(1)

动态数组

 private int size; // 逻辑大小private int capacity=8; // 容量private int[] array=new int[capacity];

插入

//向最后的位置[size]添加元素public void addLast(int element){array[size]=element;size++;}

//向[0....size]位置添加元素public void add(int index,int element){//未考虑数组扩容问题if(size>=0&&index<size) {//进行一个拷贝System.arraycopy(array, index, array, index + 1, size - index);array[index] = element;size++;} else if(index==size){//addLastarray[index]=element;size++;}}

public void add1(int index,int element){if(size >= 0 && index < size){System.arraycopy(array,index,array,index+1,size-index);}array[index]=element;size++;}

查询和遍历元素

//查询元素public int get(int index){//[0....size]return array[index];}//打印每个元素public void foreach(){for (int i=0;i<size;i++){System.out.println(array[i]);}}//函数式接口//遍历方法1，consumer接口 遍历执行的操作，每个元素入参public void foreach1(Consumer<Integer> consumer){for(int i=0;i<size;i++){consumer.accept(array[i]);}}//Iterator 是个接口，要有实现类//迭代器遍历@Overridepublic Iterator<Integer> iterator() {//java里叫匿名内部类return new Iterator<Integer>() {int i=0;@Overridepublic boolean hasNext() {//有没有下一个严肃return i<size;}@Overridepublic Integer next() {//返回当前元素，并移动到下一个元素return array[i++];}};}public IntStream stream(){//IntStream 传的数字不仅有有效数字，还有无效的 eg：1,2,3,4,0,0,0,0return IntStream.of(Arrays.copyOfRange(array,0,size));}

  public static void main(String[] args) {System.out.println("Hello world!");DynamicArray dynamicArray = new DynamicArray();dynamicArray.addLast(1);dynamicArray.addLast(2);dynamicArray.addLast(3);dynamicArray.addLast(4);dynamicArray.add(2,5);for(int i=0;i<5;i++){System.out.println(dynamicArray.get(i));}//迭代器遍历for(Integer element:dynamicArray){//hasnext()、next()方法System.out.println(element);}}

删除

 public int remove(int index){  //[0...size]int removed=array[index];if(index<size-1) {//java数组中移动元素的方法System.arraycopy(array, index + 1, array, index, size - index - 1);}size--;return removed;}

对比数据是否一致（断言）

assertEquals(3,removed);

assertIterable(List.of(1,2,4,5),dynamicArray);

容量不够，先扩容

   private void checkAndGrow() {//容量检查if(size==0){array=new int[capacity];}if(size==capacity){//进行扩容，1.5   1.618   2capacity+=capacity>>1;int [] newArray=new int[capacity];System.arraycopy(array,0,newArray,0,size);array=newArray;}}

插入或删除性能

头部位置，时间复杂度是O(n)

中间位置，时间复杂度是O(n)

尾部位置，时间复杂度是O(1)

全部代码

package org.example;import java.util.Iterator;
import java.util.Arrays;
import java.util.function.Consumer;
import java.util.stream.IntStream;//动态数组
public class DynamicArray implements Iterable<Integer>{private int size; // 逻辑大小private int capacity=8; // 容量// private int[] array=new int[capacity];private int[] array={};//向最后的位置[size]添加元素public void addLast(int element){array[size]=element;size++;}//向[0....size]位置添加元素public void add(int index,int element){checkAndGrow();//未考虑数组扩容问题if(size>=0&&index<size) {//进行一个拷贝System.arraycopy(array, index, array, index + 1, size - index);array[index] = element;size++;} else if(index==size){//addLastarray[index]=element;size++;}}private void checkAndGrow() {//容量检查if(size==0){array=new int[capacity];}if(size==capacity){//进行扩容，1.5   1.618   2capacity+=capacity>>1;int [] newArray=new int[capacity];System.arraycopy(array,0,newArray,0,size);array=newArray;}}public void add1(int index,int element){if(size >= 0 && index < size){System.arraycopy(array,index,array,index+1,size-index);}array[index]=element;size++;}//查询元素public int get(int index){//[0....size]return array[index];}//打印每个元素public void foreach(){for (int i=0;i<size;i++){System.out.println(array[i]);}}//函数式接口//遍历方法1，consumer接口 遍历执行的操作，每个元素入参public void foreach1(Consumer<Integer> consumer){for(int i=0;i<size;i++){consumer.accept(array[i]);}}//Iterator 是个接口，要有实现类//迭代器遍历@Overridepublic Iterator<Integer> iterator() {//java里叫匿名内部类return new Iterator<Integer>() {int i=0;@Overridepublic boolean hasNext() {//有没有下一个严肃return i<size;}@Overridepublic Integer next() {//返回当前元素，并移动到下一个元素return array[i++];}};}public IntStream stream(){//IntStream 传的数字不仅有有效数字，还有无效的 eg：1,2,3,4,0,0,0,0return IntStream.of(Arrays.copyOfRange(array,0,size));}public int remove(int index){  //[0...size]int removed=array[index];if(index<size-1) {//java数组中移动元素的方法System.arraycopy(array, index + 1, array, index, size - index - 1);}size--;return removed;}}

二维数组

从行开始遍历比从列开始遍历更快。

局部性原理：（空间方面）

  cpu读取内存（速度慢）数据后，会将其放入高速缓存（速度快）中当中，如果后来的计算机再用到此数据，在缓存中能读到的话，就不必读内存了。

  缓存的最小存储单位是缓存行，一般是64bytes，一次读的数据少了不划算，因此最少读64bytes填满一个缓存行，因此读入某一个数据时也会读取其临近的数据，这就是所谓的空间局部性。