Java实现的数据结构与算法:顺序表
顺序表(也称为动态数组或数组列表)是一种常用的数据结构,用于存储一定数量的元素,并支持快速的索引访问。在Java中,顺序表的实现可以通过使用数组来完成。下面是如何使用Java实现顺序表的一个简单示例:
public class MyArrayList<T> {
private Object[] elements;
private int size;
private static final int DEFAULT_CAPACITY = 10;
// Constructor with default capacity
public MyArrayList() {
this.elements = new Object[DEFAULT_CAPACITY];
this.size = 0;
}
// Constructor with custom capacity
public MyArrayList(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Capacity must be non-negative");
}
this.elements = new Object[initialCapacity];
this.size = 0;
}
// Adds an element to the end of the list
public void add(T element) {
ensureCapacity(size + 1);
elements[size++] = element;
}
// Ensures there's enough capacity to hold new elements
private void ensureCapacity(int minCapacity) {
if (minCapacity > elements.length) {
int newCapacity = elements.length * 2;
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
Object[] newElements = new Object[newCapacity];
System.arraycopy(elements, 0, newElements, 0, size);
elements = newElements;
}
}
// Retrieves an element at a specified index
public T get(int index) {
checkIndex(index);
return (T) elements[index];
}
// Removes an element at a specified index
public T remove(int index) {
checkIndex(index);
T oldValue = (T) elements[index];
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elements, index + 1, elements, index, numMoved);
}
elements[--size] = null; // Clear to let GC do its work
return oldValue;
}
// Returns the number of elements in the list
public int size() {
return size;
}
// Checks if an index is within the bounds of the list
private void checkIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
// Example usage
public static void main(String[] args) {
MyArrayList<Integer> list = new MyArrayList<>();
list.add(1);
list.add(2);
list.add(3);
System.out.println("Element at index 1: " + list.get(1)); // Output: 2
System.out.println("List size: " + list.size()); // Output: 3
list.remove(1);
System.out.println("List size after removal: " + list.size()); // Output: 2
}
}
说明
- 数据存储:使用一个数组来存储元素。
- 动态扩容:
ensureCapacity
方法用于在添加新元素时,检查并增加数组容量。 - 添加元素:
add
方法用于在列表末尾添加元素。 - 获取元素:
get
方法通过索引获取元素。 - 删除元素:
remove
方法通过索引移除元素,并调整后续元素的位置。 - 边界检查:
checkIndex
用于确保索引在有效范围内。
这个简单的实现展示了顺序表的基本操作以及如何关键的动态扩容等特性的实现。Java中的ArrayList
是此数据结构的一个强大实现,提供了许多优化和额外的功能。