大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
一般来说,我们用数组这种数据结构最多的情况,是用来做查询,时间复杂度为O(1),那么在这里我们来看一下如何用在数组中插入元素和删除元素。
数组的适用场景:
一般在查询中,适用数组的情况是比较多,因为可以根据下标直接访问元素,时间复杂度是O(1),所以适用于读多写少的场景。
数组的插入和删除元素,一般时间复杂度都是O(N),比较麻烦,所以对于插入和删除操作中,不建议选用数组这种数据结构,可以考虑链表。
大家都知道数组是一种数据结构,属于线性表,数据元素在内存中是一块连续的存储区域,属于顺序存储。
那么我们在数组中插入元素的话,一般会有三种插法:
(1)在数组的第一个位置插入元素
(2)在数组的最后一个位置插入元素
(3)在数组的中间位置插入元素
首先我们考虑第一种情况:在数组的第一个位置插入元素:
(1)如果数组是一个空数组的话,那么我们就直接把这个元素赋值给下标为0的数组元素;
(2)如果数组不是空数组,那么我们在第一个位置插入元素之前,需要将原有的数组元素统一向后移动一个位置,但是需要保证插入一个元素后,数组的长度应该小于初始化的时候数组长度,
(3)如果插入后大于了原有数组的长度,那么在插入之前,我们需要新建一个数组,进行数组长度的扩容,以便元素数组内容和新插入的元素都可以插入到数组中。
考虑第二种情况,直接在尾部插入:
(1)如果原有数组还有剩余空间,那么就直接插入到原有数组的空闲位置
(2)如果原有数组所有下标都有元素,那么就需要对原有数组进行扩容
考虑第三种情况,在数组的中间位置插入元素:
类似于在数组的第一个位置插入元素的想法
下面是具体的实现:
public class ArrayTest {
public static void main(String[] args) throws Exception{
MyArray myArray = new MyArray(4);
myArray.insert(3,0);
myArray.insert(7,1);
myArray.insert(9,2);
myArray.insert(5,3);
myArray.insert(6,1);
myArray.output();
}
}
class MyArray{
private int[] array;
private int size;
public MyArray(int capacity) {
this.array = new int[capacity];
this.size = 0;
}
/**
*
* @param element 插入的元素
* @param index 插入的元素的位置
* @throws Exception
*/
public void insert(int element,int index) throws Exception{
if (index < 0 || index > size){
throw new Exception("插入的元素位置超越了数组实际的元素范围");
}
if(size >= array.length){
grow();
}
//这个循环就是在插入元素的时候,将指定位置上的元素都向后移动一位,
//给要插入的元素腾出位置
//移动顺序就是从最后一个元素开始向后移动,一直到原有位置的元素后移一位
for (int i = size-1; i >= index ; i--) {
array[i+1] = array[i];
}
array[index] = element;
size++;
}
/**
* 数组进行扩容,这里必须选择正整数
*/
private void grow() {
int[] newArray = new int[array.length*2];
//将原有数组的内容复制到新数组中
System.arraycopy(array,0,newArray,0,array.length);
//原有数组指向新数组的内容
array = newArray;
}
public void output(){
for (int i = 0; i < size; i++) {
System.out.println(array[i]);
}
}
}
删除指定位置的元素:
(1)判断索引下标是否在数组的下标0~array.length-1之内
(2)然后让要删除位置的元素后面的元素挨个往前挪一位就可以了
/**
* 删除指定位置的元素
* @param index
* @throws Exception
*/
public void delete(int index) throws Exception{
if (index < 0 || index > size-1 ){
throw new Exception("不存在该下标对应的元素");
}
for (int i = index; i < size-1; i++) {
array[i] = array[i+1];
}
size--;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169522.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...