这些天一直纠结于散列表的总结, 感觉自己对散列表的理解还可以, 源代码也深究了一些, 但是一到要写的时候就找不到好的思路, 只好从基本的开始写, 希望能为后续的散列表总结找到一些思路...
ArrayList是基于数组实现的, 它在一个连续的储存块中储存元素, 不过与数组不同的是: ArrayList可以进行动态的增长, 通俗一点说就是: 当数组不足以容纳更多的元素时, 我们就再建立一个新的,更长的数组, 将原数组的元素拷贝到新数组里, 再对这个新数组进行操作.
首先分析一下它的基本功能:
1.添加操作:将指定索引位置后所有元素向后移动, 再将要插入的数据插入到空出来的指定索引位置.
2.删除操作:
删除操作和插入操作有点类似, 是将指定索引后的元素都向前移动, 想当于插入操作的逆过程.
3.查找操作:
1)给定索引, 可直接查找指定索引出的元素
2)给定值, 则需要遍历
4.修改操作:
给定索引直接替换原值
下面看一下具体的代码实现:
package List;
/**
* 基于数组的列表集合
*
* @author MOYUNYU
*
*/
public class ArrayListImpl {
// 保存元素的数组
private Object[] data;
// 列表中所添加的元素个数
private int size = 0;
/**
* 无参的构造方法, 数组初始大小默认为10
*/
public ArrayListImpl() {
this(10);
}
/**
* 指定列表的初始大小
*
* @param Capacity
*/
public ArrayListImpl(int capacity) {
// 判断给的容量是否合法
if (capacity < 0) {
throw new IllegalArgumentException("列表的容量不能是负数");
}
// 实例化数组
this.data = new Object[capacity];
}
/**
* 在列表尾部插入对象
*
* @param o
* 要插入的对象
* @return 插入成功则返回true
*/
public boolean add(Object o) {
// 检查是否需要扩容
checkCapacity(-1, null);
// 添加对象到列表尾端
data[size] = o;
// 列表长度加一
size++;
// 添加成功, 返回true
return true;
}
/**
* 在指定索引位置插入对象
*
* @param index
* 指定的索引位置
* @param o
* 要插入的对象
*/
public void add(int index, Object o) {
// 尾部直接插入
if (index == size + 1) {
add(o);
}
// 检查索引值的合法性
else if (rangeCheck(index)) {
// 如果不需要扩容, 则直接进行操作, 否则进行扩容插入
if (size < data.length) {
// 将索引index-1后的所有对象后移
System.arraycopy(data, index, data, index + 1, size - index);
// 直接插入对象
data[index] = o;
} else {
// 扩容, 并插入对象
checkCapacity(index, o);
}
// 列表长度加一
size++;
}
}
/**
* 删除指定位置的对象并将删除的对象返回
*
* @param index
* 指定的索引位置
* @return 索引越界返回null, 否则返回删除的对象
*/
public Object remove(int index) {
if (index == size) {
throw new IndexOutOfBoundsException("你指定的索引越界,列表大小 : " + size
+ ", 你指定的索引: " + index);
}
// 索引检查
if (rangeCheck(index)) {
// 保存对象
Object o = data[index];
if (index == size) {
data[index] = null;
} else {
// 将后边的前移
System.arraycopy(data, index + 1, data, index, size - index - 1);
}
// 列表长度加一
size--;
// 将要删除的对象返回
return o;
}
return null;
}
/**
* 删除列表尾部的对象
*
* @param o
* 尾部的对象
* @return 删除成功则返回true, 没有指定对象返回false
*/
public boolean remove(Object o) {
// 遍历数组, 寻找指定对象
for (int i = 0; i < size; i++) {
if (o.equals(data[i])) {
remove(i);
return true;
}
}
// 没有找到返回false
return false;
}
/**
* 查找指定索引位置上的对象
*
* @param index
* 指定的索引位置
* @return 该位置上的对象
*/
public Object find(int index) {
// 检查索引的合法性
rangeCheck(index);
// 返回指定索引位置的对象
return data[index];
}
/**
* 判断列表中是否含有指定对象
*
* @param o
* 指定的对象
* @return 含有指定对象返回true
*/
public boolean contain(Object o) {
// 循环遍历列表
for (int i = 0; i < size; i++) {
if (data[i].equals(o)) {
return true;
}
}
return false;
}
/**
* 修改指定位置上的对象
*
* @param index
* 指定的索引位置
* @param o
* @return 修改成功返回true
*/
public Object change(int index, Object o) {
// 检查指定索引位置的合法性
rangeCheck(index);
// 储存原对象
Object old = data[index];
// 替换
data[index] = o;
return old;
}
/**
* 检查给定的索引是否合法
*
* @param index
* 给定元素
* @return 越界抛出异常, 正常true
*/
public boolean rangeCheck(int index) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException("你指定的索引越界,列表大小 : " + size
+ ", 你指定的索引: " + index);
}
return true;
}
/**
* 作用1: 扩容, 复制原数组 作用2: 扩容, 复制原数组并在指定索引插入对象, 仅当index==-1, o==null
*/
public void checkCapacity(int index, Object o) {
if (size >= data.length) {
// 实例化一个新的数组
Object[] newData = new Object[size * 3];
// 如果index是-1, 直接拷贝即可, 否则, 需要将指定索引位置空下
if (index == -1 && o == null) {
// 将原数组中的对象拷贝过来
System.arraycopy(data, 0, newData, 0, size);
} else {
// 将要插入索引位置前面的对象拷贝
System.arraycopy(data, 0, newData, 0, index);
// 插入对象
newData[index] = o;
// 将要插入索引位置后面的对象拷贝
System.arraycopy(data, index, newData, index + 1, size - index);
}
// 将引用交给data
data = newData;
// 让GC处理
newData = null;
}
}
/**
* 获取列表的大小
*
* @return 列表的大小
*/
public int getSize() {
return this.size;
}
/**
* 打印列表中的数据
*/
public void printArrayList() {
for (int i = 0; i < size; i++) {
if (i == 0) {
System.out.print("{ " + data[i]);
} else if (i > 0 && i < size - 1) {
System.out.print(", " + data[i]);
} else if (i == size - 1) {
System.out.print(", " + data[i] + " }");
}
}
}
}
下面请看测试:
package List;
public class Demo {
public static void main(String[] args) {
ArrayListImpl a = new ArrayListImpl();
long start = System.currentTimeMillis();
for (int i = 0; i < 2000001; i++) {
a.add(i, i);
}
long end = System.currentTimeMillis();
System.out.println("自实现列表的需要所需要的时间为 : " + (end - start));
}
}
结果为:
自实现列表的需要所需要的时间为 : 486
系统列表所需要的时间为 : 453
package List;
import java.util.ArrayList;
public class STest {
public static void main(String[] args) {
ArrayList a = new ArrayList();
long start = System.currentTimeMillis();
for (int i = 0; i < 2000001; i++) {
a.add(i, i);
}
for (int i = 0; i < 2000001; i++) {
a.set(i, i);
}
long end = System.currentTimeMillis();
System.out.println("系统列表所需要的时间为 : " + (end - start));
}
}
结果为:
自实现列表的需要所需要的时间为 : 967
系统列表所需要的时间为 : 811
package List;
public class Demo {
public static void main(String[] args) {
ArrayListImpl a = new ArrayListImpl();
long start = System.currentTimeMillis();
for (int i = 0; i < 2000001; i++) {
a.add(i, i);
}
for (int i = 0; i < 2000001; i++) {
a.change(i, i);
}
for (int i = 2000000; i >= 0; i--) {
a.remove(i);
}
long end = System.currentTimeMillis();
System.out.println("自实现列表的需要所需要的时间为 : " + (end - start));
}
}
结果为:
自实现列表的需要所需要的时间为 : 998
系统列表所需要的时间为 : 842
总结:
1. ArrayList可以高效的随机访问元素
2. 在ArrayList中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动;
3. ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间
也就是说: 当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能; 但是如果需要频繁的进行插入删除等操作, ArrayList的缺点就会很明显了, 这时可以选择LinkedList, 有关LinkedList的实现, 将在下一篇博客中分析.
分享到：
相关推荐
`ArrayList`的底层实现是基于数组结构，因此它在查询元素时具有较快的速度（时间复杂度接近O(1)），但在插入或删除元素时性能较低（时间复杂度为O(n)）。 #### 二、ArrayList的特点 - **动态调整大小**：`ArrayList...
在Java编程语言中，ArrayList是`java....总之，ArrayList是Java中常用的动态数组实现，适用于需要灵活增删元素且对随机访问性能有较高要求的场景。了解并熟练掌握ArrayList的使用和特性对于Java开发者来说至关重要。
ArrayList内部基于数组实现，但提供了更多的灵活性。当你不确定需要存储多少元素或者需要频繁添加、删除元素时，ArrayList是一个更好的选择。例如，在游戏中，如果玩家可以随时加入或退出队伍，使用ArrayList来存储...
ArrayList 底层采用数组实现，所以它的操作基本上都是基于对数组的操作。ArrayList 提供了三个构造函数： 1. ArrayList()：默认构造函数，提供初始容量为 10 的空列表。 2. ArrayList(int initialCapacity)：构造一...
它内部基于动态数组实现，提供了灵活的增删改查功能，同时保持了元素的有序性。本篇将深入探讨如何使用数组来模仿ArrayList的功能，以便理解其底层原理。 首先，数组是最基本的数据结构，它在内存中连续存储相同...
ArrayList是一个基于数组实现的动态列表，可以存储任何类型的数据，并且支持动态扩容。在本实例中，我们将深入探讨ArrayList的常用操作、特性和注意事项。 一、ArrayList的构造方法 ArrayList提供了几种构造方法，...
ArrayList和Vector都是Java集合框架中实现List接口的两种数据结构，它们都允许存储多个元素，但两者在设计和性能上存在显著差异。 1. 同步性： - Vector是线程安全的，这意味着在多线程环境中，多个线程可以同时...
浅析ArrayList内部实现 ArrayList是Java集合框架中的一种常用数据结构，能够存储任意多个对象...ArrayList的内部实现机理是基于数组的，但是通过扩容机理和索引机理，可以实现自由扩展和指定索引位置添加数据的功能。
总结来说，ArrayList是Java中一个重要的动态数组实现，它的优点在于提供了高效的随机访问和修改，但在插入和删除元素时，特别是当元素位于列表中间时，性能相对较差。在多线程环境下，使用ArrayList需要额外的同步...
本篇文章将深入探讨基于数组的问题及其解决方案，尤其关注二维数组（2D Arrays）在Java中的应用。 一、一维数组的基础知识 1. 定义与初始化：在Java中，一维数组可以声明为`type[] arrayName;`或`type arrayName[]...
在Java中，ArrayList是基于数组实现的，而在C++中，我们通常使用std::vector来达到类似的效果。然而，对于大规模数据，简单的数组或vector可能会遇到性能瓶颈，特别是在插入和删除元素时，因为它们可能需要移动大量...
ArrayList的设计基于数组，它提供了一个灵活的、可变大小的列表，允许我们在列表的任何位置进行插入和删除操作。ArrayList类继承自AbstractList接口，并实现了Serializable和Cloneable接口，这使得ArrayList对象可以...
ArrayList是.NET框架中System.Collections命名空间下的一个类，它是基于数组实现的数据结构，但与传统的数组相比具有更灵活的功能。ArrayList作为一个动态数组，允许在运行时动态调整其大小，这使得它更适合那些需要...
由于ArrayList是基于数组实现的，因此它支持快速随机访问，但插入和删除元素时可能需要进行数组的扩容或缩容操作，这可能导致一定的性能开销。 1. ArrayList的构造器 - `public ArrayList()`：无参构造器，创建一...
如果你需要一个可变的List，并且希望它是基于数组的，你可以自定义一个方法，使用java.util.ArrayList来实现： ```java public static List<String> createArrayList(String[] array) { return new ArrayList...
ArrayList是基于数组实现的列表，它维护了一个Object类型的数组，并通过索引来访问元素。由于数组的特性，ArrayList在进行随机读取（get()）时具有较高的效率，因为可以通过索引直接访问。但是，当需要插入或删除...
在Java中，我们可以使用数组或ArrayList等集合类来实现环形缓冲数组。环形缓冲数组的设计灵感来自于环形队列，它提供了一种在有限空间内循环存放元素的方式，具有先进先出（FIFO）的特性。 环形缓冲数组的基本概念...
ArrayList的主要优点在于它提供了快速的随机访问，但由于它是基于数组实现的，所以在插入和删除元素时，尤其是当元素位置远离当前容量末尾时，性能会相对较差。 一、ArrayList的常见功能 1. 添加元素：ArrayList...
ArrayList基于动态数组的数据结构，因此它能够提供自动扩容的功能，同时也能够快速地进行随机访问。本篇文档将深入探讨ArrayList的内部实现原理。 首先，ArrayList是Java集合框架中List接口的一个非常重要的实现。...
ArrayList是基于数组实现的，它继承自AbstractList，并实现了List接口。在初始化ArrayList时，它会创建一个默认容量（通常是10）的Object数组。当我们添加元素超过当前容量时，ArrayList会自动进行扩容操作。这个...