当前位置:网站首页>线性表之动态数组(ArrayList)的自实现
线性表之动态数组(ArrayList)的自实现
2022-08-04 05:31:00 【crazy__xieyi】
文章目录
一、数组是什么?
数组是一种顺序存储的线性表,所有元素的内存地址是连续的
int[] array = new int[]{11,22,33}
数组的缺点就是无法修改其容量,但是在实际开发过程中往往需要动态修改容量的。
二、对象数组
Object[] objects = new Object[7];
在这里我引入了对象数组,是因为这里会设计到一些内存管理上的细节问题。
在清除所有元素的时候,代码如下:
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
在这里我们要知道,如果Objects指向的地址丢失了,那么数组和对象谁先消失呢?
因为对象是依赖于地址的,所以一定是对象最后才被清除消失。因为JVM的垃圾回收机制一般不会马上进行清除,那么此时就会造成大量空间的浪费,而且再次放元素还要进行频繁的空间创建,这样就会开销很大。所以我们在进行元素清除的时候只需要进行把地址的位置置为null即可。
同样,我们在删除元素的时候也是这样置为null,如下:
public E remove(int index) {
rangeCheck(index);
E old = elements[index];
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
elements[--size] = null;
return old;
}
三、动态数组的设计
1.泛型
使用泛型技术可以让动态数组更加通用,可以存放任何数据类型。
另外一个重要的点是任何类的父类,我们都可以认为是Object的子类。
还提供了有参和无参两个构造方法!!!
public class ArrayList<E> {
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10; //设置初始数组的容量为10
private static final int ELEMENT_NOT_FOUND = -1; //把查找不到的时候返回值统一设为默认值
public ArrayList(int capaticy) {
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
elements = (E[]) new Object[capaticy];
}
public ArrayList() {
this(DEFAULT_CAPACITY);
}
}
2.清除所有元素
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
3.元素的数量
public int size() {
return size;
}
4.判断是否为空
public boolean isEmpty() {
return size == 0;
}
5.是否包含某个元素
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
6.添加元素到尾部
public void add(E element) {
add(size, element);
}
7.获取index位置的元素
public E get(int index) {
rangeCheck(index);
return elements[index];
}
8.设置index位置的元素
public E set(int index, E element) {
rangeCheck(index);
E old = elements[index];
elements[index] = element;
return old;
}
9.在index位置插入一个元素
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacity(size + 1);
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
10.删除index位置的元素
public E remove(int index) {
rangeCheck(index);
E old = elements[index];
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
elements[--size] = null;
return old;
}
11.查看元素的索引
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 (element.equals(elements[i])) return i; // n
}
}
return ELEMENT_NOT_FOUND;
}
12.保证要有capacity的容量
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}
13.溢出抛异常
private void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
14.一般索引检查
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
15.添加元素时索引检查(在尾部可以添加,所以可以等于Size)
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
16.打印
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(", [");
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
四、动态数组复杂度分析
数组的随机访问是非常快的,因为可以直接根据下标索引计算出地址的偏移量,访问很快,而且访问效率与数组元素的个数无关。
动态数组 | |||
最好 | 最坏 | 平均 | |
add(intindex,Eelement) | O(1) | O(n) | O(n) |
remove(intindex) | O(1) | O(n) | O(n) |
set(intindex,Eelement) | O(1) | O(1) | O(1) |
get(intindex) | O(1) | O(1) | O(1) |
总结
在常规的自实现动态数组的基础之上,再引入了泛型,那么就可以应对各种类型的数组了。此时,当你翻开源码,你会发现很大程度上是跟源码的实现方式是一模一样的。
边栏推荐
- LeetCode_Dec_1st_Week
- LeetCode_Nov_3rd_Week
- 彻底删除MySQL教程
- Copy Siege Lion 5-minute online experience MindIR format model generation
- file permission management ugo
- 如何成长为高级工程师?
- Deep Learning Theory - Initialization, Parameter Adjustment
- FAREWARE ADDRESS
- LeetCode_Nov_2nd_Week
- MNIST Handwritten Digit Recognition - Image Analysis Method for Binary Classification
猜你喜欢
file permission management ugo
代码庆端午--粽你心意
【论文阅读】SPANET: SPATIAL PYRAMID ATTENTION NETWORK FOR ENHANCED IMAGE RECOGNITION
LeetCode_Nov_5th_Week
Deep learning, "grain and grass" first--On the way to obtain data sets
LeetCode_Dec_2nd_Week
MNIST手写数字识别 —— 从零构建感知机实现二分类
【论文阅读】Exploring Spatial Significance via Hybrid Pyramidal Graph Network for Vehicle Re-identificatio
Copy Siege Lion's Annual "Battle" | Review 2020
tensorRT5.15 使用中的注意点
随机推荐
多线程顺序输出
counting cycle
[开发杂项][编辑器][代码阅读]ctags&vim
LeetCode_Nov_5th_Week
第三章 标准单元库(下)
深度学习,“粮草”先行--浅谈数据集获取之道
Cut the hit pro subtitles export of essays
target has libraries with conflicting names: libcrypto.a and libssl.a.
【深度学习日记】第一天:Hello world,Hello CNN MNIST
Implementation of CAS lock-free queue
makefile基础学习
多层LSTM
LeetCode_Dec_2nd_Week
打金?工作室?账号被封?游戏灰黑产离我们有多近
CAS无锁队列的实现
度量学习(Metric learning、损失函数、triplet、三元组损失、fastreid)
[English learning][sentence] good sentence
Object.requireNonNull 方法说明
Question 1000: Input two integers a and b, calculate the sum of a+b, this question is multiple sets of test data
No matching function for call to 'RCTBridgeModuleNameForClass'