多语言企业网站源码,wordpress 赢利模式,沧州网站建设沧州,备案 添加网站数组数据结构
数组#xff08;Array#xff09;是一种线性表数据结构。它用一组连续的内存空间#xff0c;来存储一组具有相同类型数据的集合。 数组的特点#xff1a;
数组是相同数据类型的元素集合#xff08;int 不能存放 double#xff09;数组中各元素的存储是有先…数组数据结构
数组Array是一种线性表数据结构。它用一组连续的内存空间来存储一组具有相同类型数据的集合。 数组的特点
数组是相同数据类型的元素集合int 不能存放 double数组中各元素的存储是有先后顺序的它们在内存中按照这个顺序连续存放到一起。内存地址连续。数组获取元素的时间复杂度为O(1)
1. 一维数组
维数组是最常用的数组其他很多数据结构的变种也都是从一维数组来的。例如 HashMap 的拉链寻址结构ThreadLocal 的开放寻址结构都是从一维数组上实现的。
2. 二维数组 二维以及多维数组在开发场景中使用到的到是不多不过在一些算法逻辑数学计算中到是可以使用。
✍️手写实现数组列表
在 Java 的源码中数组是一个非常常用的数据结构很多其他数据结构也都有数组的影子。在一些数据存放和使用的场景中基本也都是使用 ArrayList 而不是 LinkedList 需要实现的方法
public interface PjpListE {// 添加boolean add(E e);// 删除E remove(int index);// 获取E get(int index);}
实现类
public class PjpArrayListE implements PjpListE {}
1. 基本设计
数组是一个固定的、连续的、线性的数据结构那么想把它作为一个自动扩展容量的数组列表则需要做一些扩展。
/*** 默认初始化空间*/
private static final int DEFAULT_CAPACITY 10;/*** 空元素*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};/*** ArrayList 元素数组缓存区*/
transient Object[] elementData;/*** List 集合元素数量*/
private int size; 2. 初始化
初始化分指定大小、不指定大小
public PjpArrayList() {// 初始化 ArrayList 阶段如果不指定大小默认给个空的元素当开始添加元素的时候在初始化长度this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}public PjpArrayList(int initialCapacity) {
if (initialCapacity 0) {// 如果给定长度大于0那么直接创建一个数组this.elementData new Object[initialCapacity];
} else if (initialCapacity 0) {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
} else {throw new IllegalArgumentException(Illegal Capacity: initialCapacity);
}
}
初始化 ArrayList 阶段如果不指定大小默认会初始化一个空的元素。这个时候是没有默认长度的。那么什么时候给初始化的长度呢是在首次添加元素的时候因为所有的添加元素操作也都是需要判断容量以及是否扩容的。那么在 add 添加元素时统一完成这个事情还是比较好处理的。之后就是随着元素的添加容量是会不足的。当容量不足的是需要进行扩容操作。同时还得需要把旧数据迁移到新的数组上。所以数据的迁移算是一个比较耗时的操作 3. 添加元素
Override
public boolean add(E e) {
int minCapacity size 1;
// 判断当前容量与初始化容量使用 Math.max 函数取最大值最为最小初始化空间
if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity Math.max(DEFAULT_CAPACITY, minCapacity);
}
if (minCapacity - elementData.length 0) {int oldCapacity elementData.length;// 扩为原来的1.5倍int newCapacity oldCapacity (oldCapacity 1);// 如果是第一次扩容扩容至初始化空间大小if (newCapacity - minCapacity 0) {newCapacity minCapacity;}elementData Arrays.copyOf(elementData, newCapacity);
}
elementData[size] e;
return true;
}
判断当前容量与初始化容量使用 Math.max 函数取最大值最为最小初始化空间。接下来是判断 minCapacity 和元素的数量是否达到了扩容。首次创建 ArrayList 是一定会扩容的也就是初始化 DEFAULT_CAPACITY 10 的容量。Arrays.copyOf 实际上是创建一个新的空间数组之后调用的 System.arraycopy 迁移到新创建的数组上。这样后续所有的扩容操作也就都保持统一了。ArrayList 扩容完成后就是使用 elementData[size] e; 添加元素操作了。 4. 移除元素
ArrayList 的重点离不开对 System.arraycopy 的使用它是一个本地方法可以让你从原数组的特定位置迁移到新数组的指定位置和迁移数量。
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
arraycopy 各个参数的含义
src: 原数组
srcPos 原数组起始位置从这个位置开始复制
dest 目标数组
destPos目标数组粘贴的起始位置
length 复制的个数 元素删除
public E remove(int index) {
E oldValue (E) elementData[index];
int numMoved size - index - 1;
if (numMoved 0) {System.arraycopy(elementData, index 1, elementData, index, numMoved);
}
elementData[--size] null; // 为了GC和我们不会再读到
return oldValue;
} ArrayList 的元素删除就是在确定出元素位置后使用 System.arraycopy 拷贝数据方式移动数据把需要删除的元素位置覆盖掉。此外它还会把已经删除的元素设置为 null 一方面让我们不会在读取到这个元素另外一方面也是为了 GC 5. 获取元素
Override
public E get(int index) {
return (E) elementData[index];
}Override
public String toString() {return PjpArrayList{ elementData Arrays.toString(elementData) , size size };
}
获取元素就比较简单了直接从 elementData 使用索引直接获取即可。这个是一个 O(1) 操作。也正因为搜索元素的便捷性才让 ArrayList 使用的那么广泛。
测试
public class test {public static void main(String[] args) {PjpListString num new PjpArrayList();num.add(a);num.add(b);num.add(c);num.remove(0);System.out.println(num.get(1));System.out.println(num);num.add(d);num.add(e);num.add(f);num.add(g);num.add(h);num.add(i);num.add(j);num.add(k);num.add(l);System.out.println(扩容);System.out.println(num);}
}
测试结果
⚠️注意在添加第 11 个元素的时候数组进行了扩容长度扩为原来的 1.5 倍10 -15
c
PjpArrayList{elementData[b, c, null, null, null, null, null, null, null, null], size2}
扩容
PjpArrayList{elementData[b, c, d, e, f, g, h, i, j, k, l, null, null, null, null], size11}
