01 简单数组类实现
简单封装数组类
package cn.uestc.practice1;//二次封装自己的数组public class Array01 { private int[] data; //这个类所封装的数组 private int size; //即表示数组的实际长度，又指向实际元素后的一个位置 //构造函数，传入数组的容量capacity构造Array数组 public Array01(int capacity) { data = new int[capacity]; size = 0; } //无参构造，默认数组的容量为10 public Array01() { this(10); //这里调用了有参构造函数 } //获取数组中的元素个数 public int getSize() { return size; } //获取数组的容量 public int getCapacity() { return data.length; } //返回数组是否为空 public boolean isEmpty() { return 0 == size; }//---------------------------------------- //向所有元素后添加一个元素 public void addLast(int e) {// if (size == data.length) {// throw new IllegalArgumentException("Array is full");// }// data[size] = e;// size++;//当写完指定位置处添加元素后，回头就可以发现可以对这个方法进行重构--添加方法复用， add(size, e); } //有了复用后可以很简单的写在所有元素前添加一个元素了 public void addFirst(int e) { add(0, e); } //向指定位置index处添加一个元素e,数组内部是通过移动实现的 public void add(int index,int e) { if (size == data.length) { throw new IllegalArgumentException("Array is full"); } if (index < 0 || index > size) { throw new IllegalArgumentException("index is not right"); } for (int i = size-1; i >= index; i--) { data[i+1] = data[i]; } data[index] = e; size++; } //获取index索引位置的元素,用户只能使用get方法获取而不能直接通过数组获取，方便程序内部进行判断用户是否合法 public int get(int index) { if (index< 0 || index >= size) { throw new IllegalArgumentException("Get failed. Index is illegal."); } return data[index]; } //修改index索引位置的元素 public void get(int index,int e) { if (index< 0 || index >= size) { throw new IllegalArgumentException("Get failed. Index is illegal."); } data[index] = e; } //查找数组中是否有元素e public boolean contains(int e) { for (int i = 0; i < size; i++) { if (data[i] == e) { return true; } } return false; } //查找数组中元素e所在的索引，如果不存在元素则返回-1.但要注意若数组中含有多个重复元素，只会找到第一个 public int find(int e) { for (int i = 0; i < size; i++) { if (data[i] == e) { return i; } } return -1; } //从数组中删除index位置的元素，返回删除的元素 public int remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed. Index is illegal."); } int ret = data[index]; for(int i = index+1; i < size; i++) { data[i-1] = data[i]; } size--; return ret; } // 从数组中删除第一个元素, 返回删除的元素 public int removeFirst(){ return remove(0); } //从数组中删除最后一个元素，返回删除的元素 public int removeLast(){ return remove(size - 1); } //从数组中删除元素e,同上面的查找一样当有重复时只是删除了第一个 public void removeElement(int e){ int index = find(e); if (index != -1) { remove(index); } } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("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(); } } 02 使用泛型改进
增加了泛型可以使数组类存储任何类型的对象。
package cn.uestc.practice2;//二次封装自己的数组//在01版本的基础上进行使用泛型，这可以用任何字母表示，只是代表这是一个类型public class Array02 { private E[] data; //这个类所封装的数组 private int size; //即表示数组的实际长度，又指向实际元素后的一个位置 //构造函数，传入数组的容量capacity构造Array数组 public Array02(int capacity) { data = (E[])new Object[capacity]; size = 0; } //无参构造，默认数组的容量为10 public Array02() { this(10); //这里调用了有参构造函数 } //获取数组中的元素个数 public int getSize() { return size; } //获取数组的容量 public int getCapacity() { return data.length; } //返回数组是否为空 public boolean isEmpty() { return 0 == size; }//---------------------------------------- //向所有元素后添加一个元素 public void addLast(E e) {// if (size == data.length) {// throw new IllegalArgumentException("Array is full");// }// data[size] = e;// size++;//当写完指定位置处添加元素后，回头就可以发现可以对这个方法进行重构--添加方法复用， add(size, e); } //有了复用后可以很简单的写在所有元素前添加一个元素了 public void addFirst(E e) { add(0, e); } //向指定位置index处添加一个元素e,数组内部是通过移动实现的 public void add(int index,E e) { if (size == data.length) { throw new IllegalArgumentException("Array is full"); } if (index < 0 || index > size) { throw new IllegalArgumentException("index is not right"); } for (int i = size-1; i >= index; i--) { data[i+1] = data[i]; } data[index] = e; size++; } //获取index索引位置的元素,用户只能使用get方法获取而不能直接通过数组获取，方便程序内部进行判断用户是否合法 public E get(int index) { if (index< 0 || index >= size) { throw new IllegalArgumentException("Get failed. Index is illegal."); } return data[index]; } //修改index索引位置的元素 public void get(int index,E e) { if (index< 0 || index >= size) { throw new IllegalArgumentException("Get 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] == e) { return i; } } return -1; } //从数组中删除index位置的元素，返回删除的元素 public E remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed. Index is illegal."); } E ret = data[index]; for(int i = index+1; i < size; i++) { data[i-1] = data[i]; } size--;//向前面提到的，size指向了一个不使用的数据，后面可以直接被覆盖，因此不用管。但因为现在操作对象，需要释放空间，如果可以手动效率更高 data[size]=null;//loitering objects != memory leak 这个操作其实可以不用管的，只是存有引用时JVM暂时无法回收 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("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(); } }
03 使用动态数组
使用动态数组可以不用担心数组溢出问题，只不过这里的动态并不是真正的动态，是建立在静态数组基础上的动态。
package cn.uestc.practice3;//二次封装自己的数组//在01版本的基础上进行使用泛型，这可以用任何字母表示，只是代表这是一个类型//在02版本的基础上使用动态数组public class Array { private E[] data; //这个类所封装的数组 private int size; //即表示数组的实际长度，又指向实际元素后的一个位置 //构造函数，传入数组的容量capacity构造Array数组 public Array(int capacity) { data = (E[])new Object[capacity]; size = 0; } //无参构造，默认数组的容量为10 public Array() { this(10); //这里调用了有参构造函数 } //获取数组中的元素个数 public int getSize() { return size; } //获取数组的容量 public int getCapacity() { return data.length; } //返回数组是否为空 public boolean isEmpty() { return 0 == size; }//---------------------------------------- //向所有元素后添加一个元素 public void addLast(E e) {// if (size == data.length) {// throw new IllegalArgumentException("Array is full");// }// data[size] = e;// size++;//当写完指定位置处添加元素后，回头就可以发现可以对这个方法进行重构--添加方法复用， add(size, e); } //有了复用后可以很简单的写在所有元素前添加一个元素了 public void addFirst(E e) { add(0, e); } //向指定位置index处添加一个元素e,数组内部是通过移动实现的 public void add(int index,E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("index is not right"); } //使用动态数组，进行扩容 if (size == data.length) { resize(2 * data.length); } for (int i = size-1; i >= index; i--) { data[i+1] = data[i]; } data[index] = e; size++; } //获取index索引位置的元素,用户只能使用get方法获取而不能直接通过数组获取，方便程序内部进行判断用户是否合法 public E get(int index) { if (index< 0 || index >= size) { throw new IllegalArgumentException("Get failed. Index is illegal."); } return data[index]; } //修改index索引位置的元素 public void get(int index,E e) { if (index< 0 || index >= size) { throw new IllegalArgumentException("Get 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] == e) { return i; } } return -1; } //从数组中删除index位置的元素，返回删除的元素 public E remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed. Index is illegal."); } E ret = data[index]; for(int i = index+1; i < size; i++) { data[i-1] = data[i]; } size--;//向前面提到的，size指向了一个不使用的数据，后面可以直接被覆盖，因此不用管。但因为现在操作对象，需要释放空间，如果可以手动效率更高 data[size]=null;//loitering objects != memory leak 这个操作其实可以不用管的，只是存有引用时JVM暂时无法回收 // //使用动态数组,为奇数时也没问题// if (size == data.length/2) {// resize(data.length/2);// }//当连续添加删除时继续采用上面的方法就会造成复杂度震荡，可以采取lazy策略,当继续删除至1/4时才缩减一半//还要注意不能为0 if (size == data.length/4 && 0 != data.length/2) { resize(data.length/2); } 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("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(); } public void resize(int newCapacity) { E[] newData = (E[])new Object[newCapacity]; for(int i=0;i
0