话不多说，直接上代码
创建List接口
package 数据结构接口; import java.util.Comparator; public interface Listextends Iterable { public void add(E element); public void add(int index, E element); public void remove(E element); public E remove(int index); public E get(int index); public E set(int index, E element); public int size(); public int indexOf(E element); public boolean contains(E element); public boolean isEmpty(); public void clear(); public void sort(Comparator c); public List subList(int formIndex, int toIndex); }
创建ArrayList类并继承List接口
package par_01实现; import 数据结构接口.List; import java.util.Arrays; import java.util.Comparator; import java.util.Iterator; public class ArrayListimplements List { //线性表的默认容量 private static int DEFAULT_CAPACITY = 10; //线性表储存元素的容器 data.length 容器的最大容量 private E[] data; //线性表中元素的有效个数， 也表示新来元素默认在尾部添加的角标 private int size; //默认创建一个容量为DEFAULT_CAPACITY的线性表 public ArrayList(){ this(DEFAULT_CAPACITY); } //创建一个有用户指定容量capacity的线性表 public ArrayList( int capacity){ if(capacity < 0){ throw new IllegalArgumentException("初始化的线性表的默认值必须大于等于0"); } data = (E[]) new Object[capacity]; size = 0; } //将一个一维数组转换成一个线性表 public ArrayList(E[] arr){ if(arr == null){ throw new IllegalArgumentException("初始化的值不能设置为空"); } data = (E[]) new Object[arr.length]; for (int a = 0; a < arr.length; a++) { data[a] = arr[a]; } size = arr.length; } //在线性表的末尾添加一个元素 @Override public void add(E element) { add(size, element); } //在线性表指定的位置上添加一个元素 @Override public void add(int index, E element) { if(index < 0 || index > size){ throw new IndexOutOfBoundsException("下标越界异常"); } //判断线性表是否已经满了 if (size == data.length){ resize(data.length * 2); } for (int i = size - 1; i >= index ; i--) { data[i + 1] = data[i]; } data[index] = element; size++; } private void resize(int newLength) { //1.先创建一个新数组 E[] newData = (E[]) new Object[newLength]; //2.将原数组daat中的元素复制到新数组newData中 for (int i = 0; i < size; i++) { newData[i] = data[i]; } data = newData; } //删除指定元素 @Override public void remove(E element) { //获取该元素的角标 int index = indexOf(element); //判断元素的存在性，如果存在就根据角标删除该元素 if(index != -1){ remove(index); } } //删除指定角标的元素，并返回被删除元素的值 @Override public E remove(int index) { if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("下标越界异常"); } E ret = data[index]; for (int i = index + 1; i < size; i++) { data[i-1] = data[i]; } size--; //判断是否要缩容， 不要缩容的太厉害 至少保证一个最小的值（DEFAULT_CAPACITY） //如果有效元素的个数是容量的1/4，且当前数组的长度大于10，则缩容 if (size == data.length / 4 && data.length > DEFAULT_CAPACITY){ resize(data.length / 2); } return ret; } //获取线性表中指定角标处的元素 @Override public E get(int index) { if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("下标越界异常"); } return data[index]; } //将线性表中指定角标出的值改为element，并返回原值 @Override public E set(int index, E element) { if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("下标越界异常"); } E ret = data[index]; data[index] = element; return ret; } @Override public int size() { return size; } //获取线性表中数组的容量 //这并没有重写List接口的方法，List是链表不存在数组，所以这是ArrayList的私有方法 public int getCapacity(){ return data.length; } //在线性表中查找指定元素element的角标，并返回 //从左到右第一次出现的位置，如果该元素不存在则返回-1 @Override public int indexOf(E element) { for (int i = 0; i < size; i++){ if (element.equals(data[i])) { return i; } } return -1; } //判断线性表中是否包含元素element @Override public boolean contains(E element) { return indexOf(element) != -1; } @Override public boolean isEmpty() { return size == 0; } @Override public void clear() { data = (E[]) new Object[DEFAULT_CAPACITY]; size = 0; } @Override public void sort(Comparator c) { if(c == null){ throw new IllegalArgumentException("comparator can not be null"); } int j = 0; E e = null; for (int i = 1; i < size; i++) { e = data[i]; for (j = i; j > 0 && c.compare(data[j - 1], e) > 0 ; j++) { data[j] = data[j - 1]; } data[i] = e; } } @Override public List subList(int formIndex, int toIndex) { if(formIndex < 0){ throw new IndexOutOfBoundsException("formIndex must >= 0 "); } if(formIndex > toIndex){ throw new IndexOutOfBoundsException("formIndex must <= toIndex"); } if(toIndex >= size){ throw new IndexOutOfBoundsException("toIndex must < size"); } ArrayList subList = new ArrayList<>(); for (int i = formIndex; i <= toIndex; i++){ //默认在末尾添加 subList.add(data[i]); } return subList; } //继承自Object的方法 @Override public boolean equals(Object obj){ //判断是否是自己 if (this == obj) return true; //判断obj是否和ArrayList是同一个类型 if (getClass() != obj.getClass()) return false; //判断哦比较是否为空 if (obj == null) return false; //具体比较 ArrayList other = (ArrayList) obj; //比较长度 if (size != other.size) return false; //比较内容 return Arrays.equals(data, other.data); } //继承自Object的方法 @Override public String toString(){ StringBuilder sb = new StringBuilder(String.format("ArrayList :%d/%d[", size, data.length)); if(isEmpty()){ sb.append(']'); } else { for (int i = 0; i < size; i++){ sb.append(data[i]); if (i != size){ sb.append(','); }else { sb.append(']'); } } } return sb.toString(); } @Override public Iterator iterator() { return new ArrayListIterator(); } class ArrayListIterator implements Iterator { private int cur = 0; //判断之后是否有元素 @Override public boolean hasNext() { return cur < size; } //先把元素返回然后再后移 @Override public E next() { return data[cur++]; } } }
