数据结构-数组
程序员文章站
2024-02-24 17:38:13
...
备忘录
最近准备找工作,翻一下数据结构书本想重温一下,顺手写了一下数组,没想到中间出了好几处错误,想了一下还是学完没总结的原因,现在总结一下。
数组介绍
数组是数据结构中比较简单容易理解的结构,在程序中有广泛的应用,如Java中常用的ArrayList就是动态数组的实现,总结特点是:
- 基于下标的查询速度快
- 内存连续
- 插入和删除较慢
- 容器扩容和缩容会花费大量时间
实现代码
public class Array<E> {
/**
* 当前数组中元素数量,永远指向第一个未赋值索引
*/
private int size;
/**
* 容器容量
*/
private int capacity;
private E[] data = (E[]) new Object[0];
public Array() {
size = 0;
capacity = 10;
data = (E[]) new Object[capacity];
}
public Array(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("容器容量需要大于0");
}
size = 0;
this.capacity = capacity;
data = (E[]) new Object[capacity];
}
public void insert(E e, int index) {
if (index < 0) {
throw new IllegalArgumentException("索引参数有误");
}
if (size >= capacity) {
resize(capacity * 2);
}
for (int i = size; index < i; i--) {
data[i] = data[i - 1];
}
data[index] = e;
size++;
}
public void addFirst(E e) {
insert(e, 0);
}
public void addLast(E e) {
insert(e, size);
}
public boolean contains(E e) {
for (E tmp : data) {
if (tmp.equals(e)) {
return true;
}
}
return false;
}
public E remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("索引参数异常");
}
E tmp = data[index];
for (int i = index ; i < size - 1; i++) {
data[i] = data[i + 1];
}
//加快元素回收
data[size - 1] = null;
size--;
if (size <= capacity / 4 && capacity / 2 > 0) {
resize(capacity / 2);
}
return tmp;
}
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size - 1);
}
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
@Override
public String toString() {
StringBuilder buf = new StringBuilder();
for (int i = 0; i < size; i++) {
buf.append(data[i].toString());
if (i < size - 1) {
buf.append(",");
}
}
return buf.toString();
}
}
要点总结
- size永远指向数组中第一个未赋值的索引
- 元素添加需要扩容时,直接扩容,缩容时大量少于容器最大值时在缩容,减少数组复制的开销
下一篇: HDU 6119 小小粉丝度度熊(尺取)