Java中顺序表的模拟实现
在Java中,顺序表通常可以用数组来实现,它是一种线性数据结构,支持顺序存取和动态大小调整。以下是一个简单的顺序表(动态数组)的基本实现:
public class MyArrayList<E> {
private Object[] elementData; // 存储元素的数组
private int size; // 当前元素个数
private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
// 构造方法
public MyArrayList() {
this.elementData = new Object[DEFAULT_CAPACITY];
this.size = 0;
}
// 获取元素的数量
public int size() {
return size;
}
// 判断是否为空
public boolean isEmpty() {
return size == 0;
}
// 获取指定位置的元素
public E get(int index) {
rangeCheck(index);
return (E) elementData[index];
}
// 添加元素到末尾
public void add(E element) {
ensureCapacity(size + 1);
elementData[size++] = element;
}
// 在指定位置插入元素
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacity(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
// 删除指定位置的元素
public E remove(int index) {
rangeCheck(index);
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null; // 释放最后一个元素的引用
return oldValue;
}
// 确保容量足够,当容量不足时进行扩容
private void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length) {
int newCapacity = elementData.length * 2;
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
elementData = java.util.Arrays.copyOf(elementData, newCapacity);
}
}
// 索引范围检查
private void rangeCheck(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
// 插入时索引范围检查
private void rangeCheckForAdd(int index) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
}
功能描述:
- 构造函数:初始化一个默认容量的数组。
size()
:返回当前元素个数。isEmpty()
:检查容器是否为空。get(int index)
:根据索引获取元素。add(E element)
:在容器末尾添加元素。add(int index, E element)
:在指定位置插入元素。remove(int index)
:移除指定位置的元素并返回该元素。ensureCapacity(int minCapacity)
:确保数组有足够的容量,必要时扩容。- 索引检查:方法
rangeCheck
和rangeCheckForAdd
分别用于普通访问和插入操作的索引范围检查,以防止非法操作。
这是一个基础的顺序表实现,类似于Java中的ArrayList
,可以根据需要进行扩展,比如实现其他接口、增加更多操作方法等。