深入浅出数据结构之数组

简介: 深入浅出数据结构之数组

深入浅出数据结构之数组

数据结构是计算机存储、组织数据的方式

常用的数据结构有数组、链表、栈、队列、散列表(哈希表)、堆、树、图等

熟悉数据结构能够帮助我们在平常工作中更好的使用

本篇文章将围绕数组深入浅出的解析数组的特点、适用场景以及设计如何实现数组

数组的特点

存储元素内存连续

数组是在内存中连续存储多个元素的结构,元素能够通过数组的下标(索引)进行访问

数组的下标从0开始,比如图中创建了一个长度为5(连续空间)的数组,其中从下标0开始存储元素1、2、3、4

数组中存储什么元素,由什么类型的数组决定,比如我规定创建int类型的数组,那么数组中元素类型就都应该是int,并且数组中每个元素占4Byte空间

image.png

随机访问

由于数组内存空间是连续的且元素类型大小相同,这能让数组做到对每个元素的"随机访问"

比如我知道这个int数组存储真实数据的物理空间偏移量位置offset为500,则下标为0的元素就是从offset=500开始存储的,则下标为3的元素就是从offset=500+(3 * 4)=512 开始的

插入/删除时可能需要挪动其他元素

在数组中寻找某个关键元素时,我们可以选择将数组遍历(从头到尾)查找一边,这样平均时间复杂度就变成O(n)其中n为数据规模,随着数组中元素的增多耗时将会上升

在数组中插入某个元素时,如果插入的是数组末尾则时间复杂度不高为常量级别O(1),如果插入的是数组中间,由于空间连续,还需要将后续所有元素向后挪动一位,平均时间复杂度为O(n)

比如图中将元素0插入到下标2的位置

image.png

删除同理,比如将元素1删除时其他元素向前挪动

image.png

扩容与缩容

当发生添加操作时且数组已经被占满了就会发生扩容,需要创建一个更大的数组来装载元素,由于数组的特点,创建新数组后还需要将老数组所有元素迁移到新数组中

扩容大小是需要权衡的,当数组太小且后续还有添加操作时,扩容太小将会导致后续又进行扩容;当数组太大且后续无添加操作时,扩容太大可能导致浪费空间(图中是从长度为5 扩容为长度为10)

image.png

频繁删除元素后,数组可能存在大量空余空间,这时候如果想避免浪费空间就能进行缩容,以此来节约空间,缩容流程与扩容相似,也是新创建数组再对元素做迁移,也会额外耗时

适用场景

刚刚分析过数组的特点,熟悉特点的同学已经能够从特点分析出数组适用于哪些场景了

数组是空间连续的,支持随机访问的,访问数组中某个元素的时间成本都相同,这很适用于想查找某个下标位置上元素是什么的场景

对数组中最后一个元素进行添加/删除时,时间复杂度是常量级别的,这适用于频繁在数组尾部添加/删除的场景

数组的扩容/缩容会额外耗费时间,如果操作时就知道数据大小,可以在创建数组时就进行初始化大小,避免扩容

设计实现数组

设计数组时,需要考虑用变量来记录数组的一些信息

考虑到通用性,可以使用泛型来实现各种类型的对象数组,可能需要一个size变量来记录数组中元素的数量

 public class ListArray<T> {
     private int size = 0;
     private Object[] element;
 }

考虑到要给用户提供初始化大小,还需要INITSIZE变量来记录初始化数组长度

 private final int INITSIZE = 5;
 ​
 ListArray() {
     element = new Object[INITSIZE];
 }
 ​
 ListArray(int elements) {
     if (elements <= 0) element = new Object[INITSIZE];
     else element = new Object[INITSIZE];
 }

当遇到不理想的情况时返回一个特殊的常量ERROR

 private final int ERROR = -1;

提供一些基础能够使用数组的方法等等

查看元素数量

     public int size() {
         return size;
     }

判断数组是否为空

     public boolean isEmpty() {
         return size == 0;
     }

查找元素

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

判断数组中是否包含某个元素

     public boolean contains(T element) {
         return indexOf(element) != ERROR;
     }

获取下标位置的元素,查询前还要判断所给下标是否越界

     //时间复杂度:O(1)
     public T get(int index) {
         checkIndex1(index);
         return (T) element[index];
     }
 ​
     private void checkIndex1(int index) {
         if (index < 0 || index >= size) throw new ArrayIndexOutOfBoundsException("您输入的下标数有误");
     }

将某位置的下标元素替换为新元素,并返回旧元素

     //设置对象,返回的是旧对象
     //时间复杂度:O(1)
     public T set(int index,T elements) {
         checkIndex1(index);
         T oldElement = (T) element[index];
         element[index] = elements;
         return oldElement;
     }

添加元素,添加前需要检查扩容, 扩容中的迁移其实不需要遍历老数组迁移,可以使用APISystem.arraycopy();直接将老数组数据复制到新数组中

     /*
     添加对象到最后
     时间复杂度:
     最好:O(1) 在末尾添加元素
     最差:O(n) 扩容,移动元素
     平均:O(1)
     均摊:O(1) 连续多次复杂度低,出现个别复杂度高的情况(把复杂度高的均摊给复杂度低的)
     n是数据规模,这里数据规模是size(数组大小)
     */
     public void add(T element) {
         add(size, element);
     }
 ​
     /*
     往index位置添加对象
     时间复杂度:
     最好:O(1) 在末尾添加元素
     最差:O(n) 在头部添加元素,所有元素往后挪一位
     平均:O(n)
     n是数据规模,这里数据规模是size(数组大小)
     */
     public void add(int index, T elements) {
         checkIndex2(index);
         capacityExpansion(size + 1);
         for (int i = size; i > index; i--) {
             element[i] = element[i - 1];
         }
         element[index] = elements;
         size++;
     }
 ​
     //检查Index是否正确
     private void checkIndex2(int index) {
         if (index < 0 || index > size) throw new ArrayIndexOutOfBoundsException("您输入的下标数有误");
     }
 ​
     //扩容
     private void capacityExpansion(int capacity) {
         int oldExpansion = element.length;
         if (capacity <= oldExpansion) return;
 ​
         //(oldExpansion >> 1) = 0.5 oldExpansion
         int newExoansion = oldExpansion + (oldExpansion >> 1);
         Object[] newElement = new Object[newExoansion];
         for (int i = 0; i < size; i++) {
             newElement[i] = element[i];
         }
         element = newElement;
 ​
     }

其他方法不一一展示,数组的实现相对简单,不熟悉的同学可以去查看ArrayList源码或者手写一个简单的数组,这样能够大大加深自己对数组的理解

总结

本篇文章围绕数组,深入浅出的解析数组的特点、适用的场景以及设计数组思路与实现数组过程代码

数组是内存空间连续的结构,能够随机访问数组中的元素

在数组中间进行插入、删除需要挪动其他元素,这是额外的性能消耗,只有在数组末尾进行插入、删除才是最高效的

扩容与缩容会对数据进行复制,也是额外的性能消耗,如果知道操作数据规模就应该在初始化时设置,避免发生扩容缩容

在设计实现数组时,不仅要考虑到需要记录数组的信息,还要考虑到不合理的情况,对不合理的参数进行校验拦截


相关文章
|
2月前
|
存储 Java 程序员
数据结构之 - 深入了解数组数据结构
数据结构之 - 深入了解数组数据结构
42 6
|
2月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
112 64
|
15天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
37 5
|
22天前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
43 4
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
40 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
25 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
3月前
|
存储 Java
java数据结构,线性表顺序存储(数组)的实现
文章介绍了Java中线性表顺序存储(数组)的实现。线性表是数据结构的一种,它使用数组来实现。文章详细描述了线性表的基本操作,如增加、查找、删除、修改元素,以及其他操作如遍历、清空、求长度等。同时,提供了完整的Java代码实现,包括MyList接口和MyLinearList实现类。通过main函数的测试代码,展示了如何使用这些方法操作线性表。
|
5月前
|
存储
【数据结构OJ题】轮转数组
力扣题目——轮转数组
46 2
【数据结构OJ题】轮转数组
|
4月前
|
存储 Java 程序员
"揭秘HashMap底层实现:从数组到链表,再到红黑树,掌握高效数据结构的秘密武器!"
【8月更文挑战第21天】HashMap是Java中重要的数据结构,采用数组+链表/红黑树实现,确保高效查询与更新。构造方法初始化数组,默认容量16,负载因子0.75触发扩容。`put`操作通过计算`hashCode`定位元素,利用链表或红黑树处理冲突。`get`和`remove`操作类似地定位并返回或移除元素。JDK 1.8优化了链表转红黑树机制,提升性能。理解这些原理能帮助我们更高效地应用HashMap。
49 0
|
6月前
|
存储 算法 调度
【数据结构与算法】详解循环队列:基于数组实现高效存储与访问
【数据结构与算法】详解循环队列:基于数组实现高效存储与访问