恋上数据结构-02动态数组

恋上数据结构-02动态数组

动态数组

什么是数据结构

数据结构是计算机存储，组织从数据的方式，包括

线性结构

线性表（数组，链表，队列，哈希表）

树形结构

二叉树，AVL树，红黑树，B树，堆，Trie,哈弗曼树，并查集

图形结构

邻接矩阵，邻接表 在实际应用中需要根据使用场景选择合适的数据结构

线性表

线性表是具有n个相同类型元素的有限序列（n>=0）

a1是首节点，a0是尾节点a1是a2的前驱， a2是a1的后继

常见的线性表有

数组链表栈队列哈希表（散列表）

数组（Array）

数组是一种顺序存储的线性表，所有元素的内存地址是连续的。

int[] array = new int[]{11,22,33};

在很多编程语言中存在的缺点

无法动态修改容量，我们在实际开发中更加希望数组的容量是可以改变的。

动态数组（Dynamic Array）接口设计

动态数组的设计

ArrayList size ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------- elements

在Java中，成员变量会自动初始化，比如

int类型自动初始化为0对象类型自动初始化为null

添加元素 add(E element)

当size=0时

当size=5时

具体算法为

elements[size]=elementsize++;

打印数组

重写toString方法

在toString方法中将元素拼接为字符串

字符串拼接建议使用StringBuilder

删除元素 remove(int index)

size=7index=3

思考最后一个元素如何处理

答：最后一个元素需要进行置空操作，因为如果不置空的话，第六，第七都会同时指向该对象，那样当第六个置空，不在存储该对象的地址引用后，第七个依旧保存该地址引用，会造成JVM无法回收，同时还会有再次被访问到的风险。

添加元素 add(int index, E element)

size=5index=2

如何扩容

动态扩容，Java基本上都是增加1.5倍，具体做起来还是要新建一个数组，用旧数组指向新的数组。

泛型

使用泛型技术可以让动态数组更加通用，可以存放任何数据类型。

E是泛型，你也可以写ABC在类名后面加泛型

public class ArrayList{ private int size; private E[] elements;}

所有类都继承Object,因此可以用Object构造对象数组，然后用强制类型转换即可，包装对象不需要，会自动装箱。

elements = (E[])new Object[capacity];

创建对象写法

ArrayList list = new ArrayList<>();

对象数组

Object[] objects = new Object[7];

objects是局部变量则放在栈区，new出来的放在堆区对象数组存放的是对象的地址而不是对象本身，这样做可以节省地址空间，因为地址所占用空间是固定的八个字节如果是下面的做法,假设person占10字节，则new时就需要分配连续的70字节内存空间。不如用对象数组空间利用率高。

Object[] objects = new Person[7];

内存管理细节

删除元素，则最后一个元素处理方法与原因

public E remove(int index){ rangeCheck(index); E oldElement = elements[index]; for(int i = 0; i < size-1; i ++){ elements[i] = elements[i+1]; } elements[--size] = null; return oldElement;

最后一个元素需要进行置空操作，因为如果不置空的话，第六，第七都会同时指向该对象，那样当第六个置空，不在存储该对象的地址引用后，第七个依旧保存该地址引用，会造成JVM无法回收，同时还会有再次被访问到的风险。

清空所有元素的处理方法和原因

public void clear(){ for(int i = 0; i < size; i ++){ elements[i] = null; } size = 0;}

清空所有元素有三种方法

1. 对于基本数据类型size=0即可

对象数组存储基本数据元素都是存储元素数据而不是地址，因此直接清空即可。 对于泛型对象，由于存储的对象的地址，只是将size=0，由于数组中各元素依然存在对象的地址，因此JVM无法回收对象的内存空间，如果一定要用size=0，那么只有在再次调用add(E element)之后，新地址覆盖旧地址，没有地址引用后，原有对象的地址空间才能被释放。

2. 需要回收数组内存，将objects=null即可

objects=null直接将栈和堆的联系断掉，数组的内存空间被收回，没有对对象的地址引用，因此对象的内存空间也被收回，这样死的顺序是先死数组再死对象。

3. 只需要回收泛型对象内存空间，只需要把数组清空即可

数组的内存空间是可以循环利用的，把数组清空即是利用了这种特性，但是对象由于都是不同的，因此不可能重复利用，必须回收。

使用System.gc()提醒JVM进行对象回收。

垃圾回收可以重写类的finalize方法，这里重写Person的方法

@Override protected void finalize() throws Throwable { // TODO Auto-generated method stub super.finalize(); System.out.println("Person+"+name+" -- finalize"); }

null的处理

一个内部设计的问题-是否可以存储null数据

因为我们是自定义所以默认是可以存储的，由于Java中null不能调用方法，因此必须将null与非null的元素分开处理，如果是bull,则只需要遍历寻找另一个null元素就行；如果不是null，就可以用equals判断是否相同。

public int indexOf(E element){ if(element == null){ for(int i = 0; i < size; i ++){ if(elements[i] == null) return i; } }else{ for(int i = 0; i < size; i ++){ if(elements[i].equals(element)) return i; } } return ELEMENT_NOT_FOUND;}

equals的问题

等号默认是内存地址,使用equals不自定义其实也是比较内存地址，Java中我们可能需要重写equals方法，不再比较内存地址，而是比较数值。

附上自己写的代码

import java.util.Iterator;/** * 动态数组 * @author lidengyin * */@SuppressWarnings("unchecked")public class ArrayList { //数组元素数量 private int size; //存储元素数组 private E[] elements; //数组默认大小 private static final int DEFAULT_ARRAY_SIZE = 10; //默认没有找到元素返回数字负1 private static final int DEFAULT_NOT_FOUND = -1; /** * 有参构造函数 * @param size * @param elements */ public ArrayList(int capacity) { //this.size = size; //todo判断需要构造的动态数组大小是否小于默认大小， //小于默认大小，，用默认大小代替 if (capacity < DEFAULT_ARRAY_SIZE) { //泛型的都是继承自Object,因此可以构造Object对象数组 //然后强制类型转换为E[]范型即可。 this.elements = (E[]) new Object[DEFAULT_ARRAY_SIZE]; }else { elements = (E[])new Object[capacity]; } } /** * 无参构造函数，默认构造函数 */ public ArrayList() { //构造函数之间的调用用this this(10); } /** * 元素的数量 * @return 返回元素的数量 */ public int size() { return size; } /** * 是否为空 * @return true表示非空，false为空 */ public boolean isEmpty() { return size == 0; } /** * 是否包含某个元素 * @param element * @return true包含， false不包含 */ public boolean contains(E element) { //直接用元素位置作比较， //只要不是返回-1说明包含该元素，否则不存在 if (indexOf(element) != -1) { return true; } return false;// //Java中null不能调用任何函数，否则会有空指针异常// if(element == null) {// for(int i = 0; i < size; i ++) {// if (elements[i] == null) {// return true;// }// return false;// }// }else {// //确定元素不为空后，就可以用equals进行比较// //默认的equals和等号都是对地址进行比较，// //但是可以在对象类中自定义equals的比较规则// for(int i = 0; i < size; i++) {// if (element.equals(elements[i])) {// return true;// }// return false;// }// }// return false; } /** * 添加元素到最后面 * @param element */ public void add(E element) { if (element == null) { throw new NullPointerException(); } //todo 确保数组空间足够 ensureCapacityInternal(); //添加到元素末尾，并将元素个数加1 elements[size++]=element; } /** * 返回index位置对应的元素 * @param index * @return */ public E get(int index) { //todo 确保索引范围正确 ensureRangeInternal(index); return elements[index]; } /** * 设置index位置的元素 * @param index * @param element * @return 返回原有元素 */ public E set(int index, E element) { //保证索引正确 ensureRangeInternal(index); //拿到原有位置元素 E oldElement = elements[index]; elements[index] = element; return oldElement; } /** * 在index位置添加元素 * @param index * @param element */ public void add(int index, E element) { //确保索引正确，此时索引可以是size ensureRangeInAddOnePlace(index); //确保数组空间足够 ensureCapacityInternal(); //将index到size-1的元素全部后移一个单位 //选择从后面开始移 for(int i = size-1; i >= index; i--) { elements[i+1] = elements[i]; } } /** * 删除index位置对应的元素 * @param index * @return */ public E remove(int index) { //确保索引正确 ensureRangeInternal(index); //获取原有对象 E oldElement = elements[index]; //对index之后的元素进行前移操作 for(int i = index; i < size-1; i ++) { elements[i]=elements[i+1]; } //对于最后一个元素置空，消除对原对象的地址引用， //从而使原对象可以被消除 //最后一个元素必须消除，否则会有两个指向该对象的地址引用， //即删除元素引用之后，元素不会消除， //也还会有通过数组调用的风险 elements[--size]=null; //可以提醒JVM，进行垃圾回收 //System.gc(); return oldElement; } /** * 查看元素位置 * @param element * @return */ public int indexOf(E element) { //认为可能有元素是空，因为数组是自定义的，有这个可能； if (element == null) { //遍历查找是null的元素，并返回其索引 for(int i = 0; i < size-1; i ++) { if (elements[i] == null) { return i; } } //没有找到则返回默认未找到-1 return DEFAULT_NOT_FOUND; }else { //不为空，循环遍历即可 for(int i = 0; i < size; i ++) { if (elements[i].equals(element)) { return i; } } //没有找到则返回默认未找到-1 return DEFAULT_NOT_FOUND; } } /** * 清除所有元素 */ public void clear() { //清除所有元素要考虑到置空数组， //会断掉栈空间与堆空间的联系， //虽然，实现了清除元素， //但是再次使用时需要继续new，消耗大 //但是循环就没有这个问题，一个一个置空， //栈空间和堆空间的联系还在， //但是每个索引上对象的地址引用消除了 //对象无法在被引用，就会被垃圾回收机制消除 for(int i = 0; i < size; i ++) { elements[i] = null; } size = 0; //elements=null，也对但是需要再次new } //=============工具类，私有类================// //=============工具类，私有类================// //=============工具类，私有类================// //=============工具类，私有类================// //=============工具类，私有类================// //=============工具类，私有类================// /** * 重写toString方法 */ @Override public String toString() { //使用StringBuilder将元素拼接成字符串 StringBuilder builder = new StringBuilder(); builder.append("size: ").append(size).append(", ["); for(int i = 0; i < size; i ++) { //这里是用逗号间隔开元素， //只要不是第一个元素，那么前面都加上逗号 if (i != 0) { builder.append(","); } //注意如果elements不是包装类型， //可能需要自己重新写该类的toString builder.append(elements[i]); } builder.append("]"); return builder.toString(); // TODO Auto-generated method stub //return super.toString(); } /** * 重写finalize查看是否进行垃圾回收 */ @Override protected void finalize() throws Throwable { // TODO Auto-generated method stub System.out.println("进行垃圾回收"); super.finalize(); } /** * 确保数组空间足够 */ private void ensureCapacityInternal() { if (size==elements.length) { //将原有数组扩容1.5倍, >>即进行位运算。整体右移，相当于除以1/2 E[] newElements = (E[]) new Object[size+(size>>1)]; for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } elements = newElements; } } /** * 确保索引正确 * @param index * @return */ private void ensureRangeInternal(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(); } } /** * 确保插入时索引正确 * @param index * @return */ private void ensureRangeInAddOnePlace(int index) { //可以在最后一个元素后面插入，因此size也是允许的。 if (index < 0 || index > size) { throw new IndexOutOfBoundsException(); } }}

ArrayList源码

这个额就不看了

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。