- 泛型的思想
实现了一个可以存放任意类型的数组，这个数组可以伸缩，当添加一个元素超过了这个数组的容量，那么这个数组会自动扩容，当数组中的个数小于容量的四分之一的时候，数组容量会收缩到原来容量的一半，而且，对于扩容和锁容，我也对相关的算法进行的优化，让扩容与添加数据缩容与删除数据绑定到一起执行。
datastructure.array.Array
public class datastructure.array.Array<E>{
// 泛型不能存放基本的数据类型
private E[] data;
private int size;
// 有参数构造函数
public datastructure.array.Array(int capacity){
// 泛型数组，由于历史遗留原因，必须绕一个圈
data = (E[])new Object[capacity];
size = 0;
}
// 无参构造函数
public datastructure.array.Array(){
this(10);
}
// 获取数组中个元素个数
public int getSize(){
return this.size;
}
// 获取数组的容量
public int getCapacity(){
return this.data.length;
}
// 返回数组是否为空
public boolean isEmpty(){
return this.size == 0;
}
// 在第index个位置插入一个新的元素e
public void add(int index, E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("AddLast failed. require index>=0 and <=?");
}
// 扩容数组,如果
if(size == data.length){
E[] newData = (E[])new Object[data.length * 2];
for(int i = 0; i < index;i++){
newData[i] = data[i];
}
newData[index] = e;
for(int i = index ; i < size;i++){
newData[i+1] = data[i];
}
data = newData;
} else {
for(int i = size - 1; i >= index; i--)
data[i + 1] = data[i];
data[index] = e;
}
size ++;
}
// 向所有元素后面添加一个新元素
public void addLast(E e){
this.add(size, e);
}
// 向所有元素前面添加一个新元素
public void addFirst(E e){
this.add(0, e);
}
// 获取index索引位置的元素
public E get(int index) {
if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed, Index is illegal.");
return data[index];
}
// 修改index索引位置的元素
public void set(int index, E e) {
if(index < 0 || index >= size)
throw new IllegalArgumentException("Set failed, Index is illegal");
data[index] = e;
}
// 查找数组中是否含有元素e,
public boolean contains(E e){
for(int i=0;i < size;i++){
// 两个对象之间值的比较用equals
if(data[i].equals(e))
return true;
}
return false;
}
// 查找数组中是否含有元素e元素的索引,如果查到，返回查询到的第一个索引值，否则返回-1
public int find(E e){
for(int i=0;i < size;i++){
if(data[i].equals(e))
return i;
}
return -1;
}
// 删除指定位置的元素，防止复杂度的震荡，
// 懒缩容。
public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed, Index is illegal");
E ret = data[index];
if(size-1 == data.length / 4 && data.length / 2 != 0){
// 懒惰缩容，防止复杂度震荡，当数组的size小于capacity的四分之一才开始缩容
E[] newData = (E[])new Object[data.length / 2];
for(int i = 0; i < index; i++){
newData[i] = data[i];
}
for(int i = index; i < size - 1;i++){
newData[i] = data[i+1];
}
data = newData;
} else {
for(int i = index; i < size-1;i ++)
data[i] = data[i+1];
}
size --;
// data[size] = null; // 回收内存，可选
// // loitering objects != memory leak
return ret;
}
// 删除的快捷方法
public E removeFirst(){
return remove(0);
}
public E removeLast(){
return remove(size -1);
}
// 删除指定的元素e
public void removeElement(E e){
int index = find(e);
if(index != -1){
remove(index);
}
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
// res.append(String.format("datastructure.array.Array: size = %d , capacity = %d\n", size, data.length));
res.append(String.format("datastructure.array.Array: size = %d , capacity = %d\n", size, data.length));
res.append('[');
for(int i = 0; i < size; i++) {
res.append(data[i]);
if(i != size - 1)
res.append(", ");
}
res.append(']');
return res.toString();
}
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity];
for(int i = 0; i < size; i++){
newData[i] = data[i];
}
data = newData;
}
}
datastructure.stack.Student
public class datastructure.stack.Student {
private String name;
private int score;
public datastructure.stack.Student(String studentName, int studentScore){
name = studentName;
score = studentScore;
}
@Override
public String toString(){
return String.format("datastructure.stack.Student(name: %s, score:%d", name, score);
}
public static void main(String[] args){
datastructure.array.Array<datastructure.stack.Student> arr = new datastructure.array.Array<>();
arr.addLast(new datastructure.stack.Student("Alex", 99));
arr.addLast(new datastructure.stack.Student("Egon", 100));
arr.addLast(new datastructure.stack.Student("Peiqi", 98));
System.out.println(arr);
}
}
datastructure.datastructure.linkedList.bannerySearchTree.Main
public class datastructure.datastructure.linkedList.bannerySearchTree.Main {
public static void main(String[] args) {
datastructure.array.Array<Object> arr = new datastructure.array.Array<>(3);
Integer Int = 100;
Double Dou = 12.54;
String Str = "哈哈大圣";
datastructure.stack.Student LingTing = new datastructure.stack.Student("lingting", 100);
arr.addLast(Int);
arr.addLast(Dou);
arr.addLast(Str);
arr.addLast(LingTing);
System.out.println(arr);
arr.remove(1);
arr.remove(1);
System.out.println(arr);
arr.remove(1);
System.out.println(arr);
}
}
