数据结构---------线性表的实现

接口的实现

package 接口;
import java.util.Comparator;
//实现Iterable接口主要是为了进行foreach迭代
public interface List<E> extends Iterable<E> {//插入一个元素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();//对数组进行排序,可以调用compare()方法public void sort(Comparator<E> c);//通过角标对数组尽心截取public List<E> subList(int fromIndex,int toIndex);
}

ArrayList类的实现

package 动态数组;import 接口.List;import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;public class ArrayList<E> implements List<E> {//创建一个线性表的默认容量private static int DEFAULT_CAPACITY=10;//创建线性表的容器private E [] data;//创建线性表的有效元素个数private int size;//创建一个由用户指定的线性表public ArrayList(int capacity){if (capacity < 0) {throw new IllegalArgumentException("capacity必须大于等于0 ");}//创建容量为capacity的容器data = (E [])new Object[capacity];}//创建一个系统默认的容器public ArrayList(){this(DEFAULT_CAPACITY);}//将一个一维数组转为线性表public ArrayList(E [] arr) {//判断数组是否为空if (arr == null) {throw new IllegalArgumentException("数组为空");}data = (E [])new Object[arr.length];//将数组的元素复制到线性表for(int i=0;i<arr.length;i++){data[i]=arr[i];}size=data.length;}@Overridepublic void add(E element) {//相当于是在数组的尾部添加元素add(size,element);//如果线性表已经满了，就要进行扩容if(size==data.length){resize(data.length*2);}}private void resize(int len) {E [] newData = (E []) new Object[len];//元素的复制操作for(int i=0;i<size;i++){newData[i]=data[i];}data =newData;}@Overridepublic void add(int index, E element) {if(index<0||index>size){//线性表插入元素的最大角标是size(给末尾添加)throw new IllegalArgumentException("角标越界");}for(int i = size-1;i>=index;i--){data[i+1]=data[i];}data[index]=element;size++;}@Overridepublic void remove(E element) {int index =indexOf(element);//如果元素角标存在，就进行删除if(index!=-1){remove(index);}}@Overridepublic E remove(int index) {//判断角标是否存在if(index<0||index>=size){throw new IllegalArgumentException("角标不存在");}E ret =data[index];for(int i=index+1;i<size;i++){data[i-1]=data[i];}size--;//判断是否要缩容//缩容的条件是size==data.length&&data.length>表的默认容量if(size==data.length/4&&data.length>DEFAULT_CAPACITY){resize(data.length/2);}return ret;}//返回该角标处的元素@Overridepublic E get(int index) {if(index<0||index>=size){throw new IllegalArgumentException("角标不存在");}return data[index];}@Overridepublic E set(int index, E element) {if(index<0||index>=size){throw new IllegalArgumentException("角标不存在");}E ret =data[index];data[index]=element;return ret;}@Overridepublic int size() {return size;}//根据元素返回对应的角标@Overridepublic int indexOf(E element) {for(int i=0;i<size;i++){//因为element的是个泛型，所以要用equals来比较if(element.equals(data[i])){return i;}}return -1;}//获取线性表中的容量，不是有效容量哦public int getCapacity(){return data.length;}@Overridepublic boolean contains(E element) {return indexOf(element)!=-1;}@Overridepublic boolean isEmpty() {return size==0;}@Overridepublic void clear() {data =(E []) new Object[DEFAULT_CAPACITY];size=0;}根据比较器的规则对线性表的元素进行排序(插入)@Overridepublic void sort(Comparator<E> c) {//c实现了Comparator接口，所以就可以使用c.compare()方法了if(c==null){throw new IllegalArgumentException("比较器c不能为空");}int j;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[j]=e;}}@Overridepublic List<E> subList(int fromIndex, int toIndex) {//先判断条件是否满足if(fromIndex<0){throw new IllegalArgumentException("fromIndex不能小于0");}if(toIndex>=size){throw new IllegalArgumentException("toIndex不能>=size");}if(toIndex>fromIndex){throw new IllegalArgumentException("toIndex不能大于fromIndex");}//创建一个线性表ArrayList<E> subList =new ArrayList<E>();for(int i=toIndex;i<=fromIndex;i++){//默认在表尾添加subList.add(data[i]);}return subList;}//比较两个线性表是否相等public boolean equals(Object obs){//1,是否比的是自己if(this==obs){return true;}//2,判断是否为空if(obs==null){return false;}//3,判断两者是否是同一类型if(getClass()!=obs.getClass()){return false;}//4,具体内容ArrayList<E> other =(ArrayList<E>) obs;//5,比的就是长度if(size!=other.size()){return false;}//6，比的就是数组的内容return Arrays.equals(data,other.data);}//重写先新表的toString()方法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-1){sb.append(',');}else{sb.append(']');}}}return sb.toString();}//实现hasNext()和next()方法@Overridepublic Iterator<E> iterator() {return new ArrayListIterator();}class ArrayListIterator implements  Iterator<E>{//定义一个游标从0开始int cur =0;@Overridepublic boolean hasNext() {return cur<size;}@Overridepublic E next() {return data[cur++];}}
}

测试类的实现

package 动态数组;import java.util.Iterator;public class TestArrayList {public static void main(String[] args) {ArrayList<String> list =new ArrayList<>();System.out.println(list);for(int i=0;i<10;i++){list.add("num"+i);}System.out.println(list);Iterator<String> it =list.iterator();while(it.hasNext()){System.out.println(it.next());}System.out.println("-------------------------");for(String s:list){System.out.print(s);}}
}

自己觉得写得挺详细的