所有线性表接口的定义：
/**
* 定义列表的接口,所有列表该实现的约定
* 增删改查
* @author Administrator
*
*/
public interface MyList {
/**
* 增加一个元素
* @param element
*/
void add(Object element);
/**
* 根据值，删除一个元素
* @param element
*/
void delete(Object element);
/**
* 根据下标删除一个元素
* @param index
*/
void delete(int index);
/**
* 根据下标更新一个元素
* @param index
* @param element
*/
void update(int index, Object element);
/**
* 判断线性表中是否包含该元素
* 返回布尔型
* @param element
* @return
*/
boolean contains(Object element);
/**
* 返回线性表中与该元素相等的值的下标
* 如果没有返回-1
* @param element
* @return
*/
int index(Object element);
}
public class _01MyArrayList implements MyList{
/**
* 线性表的定义:
* 基于数组实现线性表
* @param args
*/
private Object[] elements;//基于数组的数据结构
private int size = 0;//当前线性表中元素个数
private int capacity = 10;//线性表容量，初值为10
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
for(int i = 0; i < size; i++) {
sb.append(elements[i] + (i == size - 1?"]":" , "));
}
return sb.toString();
}
public _01MyArrayList(int capacity) {//自定义线性表容量
super();
this.capacity = capacity;
elements = new Object [capacity];
}
public _01MyArrayList() {//默认线性表容量
super();
elements = new Object [capacity];
}
@Override
public void add(Object element) {//开空间与拷贝都是耗时的操作
if(size == capacity) {//扩容,拷贝原数组元素
capacity += 20;
Object[] newArr = new Object[capacity];
for(int i = 0; i < size; i++) {//拷贝
newArr[i] = elements[i];
}
elements = newArr;
}
elements[size] = element;
size++;
}
@Override
public void delete(Object element) {
int index = index(element);
if(index >= 0)
delete(index);
}
@Override
public void delete(int index) {
//线性表重排,从删除位置依次向前更新,不更改原线性表排序
for(int i = index; i < size - 1; i++) {
Object temp = elements[i];
elements[i] = elements[i+1];
elements[i+1] = temp;
}
elements[size - 1] = null;
size--;
}
@Override
public void update(int index, Object element) {
elements[index] = element;
}
@Override
public boolean contains(Object element) {
return index(element) >= 0;
}
@Override
public int index(Object element) {
for(int i = 0; i < size; i++) {
if(elements[i].equals(element))
return i;
}
return -1;
}
}
网友评论