目录
顺序表的实现
顺序表的遍历
顺序表的容量可变
顺序表的时间复杂度
java中ArrayList实现
线性表是n个具有相同特性的数据元素的有限序列。常见的线性表有:顺序表、链表、栈、队列等。
线性表的分类：顺序表(数组)和链表
顺序表的实现
顺序表API设计:
顺序表的代码实现
//顺序表实现 public class SequenceList<T>{ private T[] array; //存储元素的数组 private int N; //记录当前顺序表的元素个数 //构造方法 public SequenceList(int capacity){ array=(T[])new Object[capacity]; N=0; } //清除线性表 public void clear(){ N=0; } //判断当前线性表是否为空表 public boolean isEmpty(){ return N==0; } //获取线性表的长度 public int length(){ return N; } //获取指定位置的元素 public T get(int i){ if(i<0||i>=N){ throw new RuntimeException("当前元素不存在"); } return array[i]; } //向线性表中添加元素t public void insert(T t){ if(N==array.length){ throw new RuntimeException("当前表已满"); } array[N++]=t; } //在i元素处插入元素t public void insert(int i,T t){ if(i==array.length){ throw new RuntimeException("当前表已满"); } if(i<0||i>N){ throw new RuntimeException("插入的位置不合法"); } //把i位置空出来, i位置及后面的元素依次向后移动一位 for(int index=N;index>i;index--){ array[index]=array[index-1]; } //把t放到i处 array[i]=t; //元素的数量+1 N++; } //删除指定位置i处的元素，并返回该元素 public T remove(int i){ if(i<0||i>N-1){ throw new RuntimeException("当前要删除的元素不存在"); } //记录i位置处的元素 T result=array[i]; //将后一个元素往前移动 for(int index=i;index<N-1;index++){ array[index]=array[index++]; } //元素数量-1 N--; return result; } //查询t元素第一次出现的位置 public int indexOf(T t){ if(t==null){ throw new RuntimeException("查找的元素不合法"); } for(int i=0;i<N;i++){ if(array[i].equals(t)){ return i; } } return -1; } } class SequenceListTest{ public static void main(String[] args) { SequenceList<String> s1=new SequenceList<>(10); s1.insert("龍弟"); s1.insert("龍龍"); s1.insert("龍哥"); //测试获取 String getResult = s1.get(1); System.out.println("获取索引1处的结果为:"+getResult); //测试删除 String remove = s1.remove(0); System.out.println("删除的元素为:"+remove); s1.clear(); System.out.println("清空后的线性表中的元素个数为:"+s1.length()); } }
顺序表的遍历
在java中，遍历集合的方式一般都是用的是foreach循环，如果想让我们的SequenceList也能支持foreach循环，则 需要做如下操作：
1.让SequenceList实现Iterable接口，重写iterator方法；
2.在SequenceList内部提供一个内部类SIterator,实现Iterator接口，重写hasNext方法和next方法；
//顺序表代码 public class SequenceList<T> implements Iterable<T>{ //存储元素的数组 private T[] array; //记录当前顺序表中的元素个数 private int N; //构造方法 public SequenceList(int capacity){ array = (T[])new Object[capacity]; N=0; } //将一个线性表置为空表 public void clear(){ N=0; } //判断当前线性表是否为空表 public boolean isEmpty(){ return N==0; } //获取线性表的长度 public int length(){ return N; } //获取指定位置的元素 public T get(int i){ if (i<0 || i>=N){ throw new RuntimeException("当前元素不存在！"); } return array[i]; } //向线型表中添加元素t public void insert(T t){ if (N==array.length){ throw new RuntimeException("当前表已满"); } array[N++] = t; } //在i元素处插入元素t public void insert(int i,T t){ if (i==array.length){ throw new RuntimeException("当前表已满"); } if (i<0 || i>N){ throw new RuntimeException("插入的位置不合法"); } //把i位置空出来，i位置及其后面的元素依次向后移动一位 for (int index=N;index>i;index--){ array[index]=array[index-1]; } //把t放到i位置处 array[i]=t; //元素数量+1 N++; } //删除指定位置i处的元素，并返回该元素 public T remove(int i){ if (i<0 || i>N-1){ throw new RuntimeException("当前要删除的元素不存在"); } //记录i位置处的元素 T result = array[i]; //把i位置后面的元素都向前移动一位 for (int index=i;index<N-1;index++){ array[index]=array[index+1]; } //元素数量-1 N--; return result; } //查找t元素第一次出现的位置 public int indexOf(T t){ if(t==null){ throw new RuntimeException("查找的元素不合法"); } for (int i = 0; i < N; i++) { if (array[i].equals(t)){ return i; } } return -1; } //打印当前线性表的元素 public void showEles(){ for (int i = 0; i < N; i++) { System.out.print(array[i]+" "); } System.out.println(); } @Override public Iterator iterator() { return new SIterator(); } private class SIterator implements Iterator{ private int cur; public SIterator(){ this.cur=0; } @Override public boolean hasNext() { return cur<N; } @Override public T next() { return array[cur++]; } } } //测试代码 public class Test { public static void main(String[] args) throws Exception { SequenceList<String> squence = new SequenceList<>(5); //测试遍历 squence.insert(0, "龍龍"); squence.insert(1, "龍弟"); squence.insert(2, "龍帝"); squence.insert(3, "龍哥"); squence.insert(4, "龍龍"); for (String s : squence) { System.out.println(s); } } }
顺序表的容量可变
1.添加元素时：
添加元素时，应该检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我 们这里创建一个是原数组两倍容量的新数组存储元素。
2.移除元素时：
移除元素时，应该检查当前数组的大小是否太大，比如正在用100个容量的数组存储10个元素，这样就会造成内存 空间的浪费，应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建 一个是原数组容量的1/2的新数组存储元素。
//顺序表代码 public class SequenceList<T> implements Iterable<T>{ //存储元素的数组 private T[] array; //记录当前顺序表中的元素个数 private int N; //构造方法 public SequenceList(int capacity){ array = (T[])new Object[capacity]; N=0; } //将一个线性表置为空表 public void clear(){ N=0; } //判断当前线性表是否为空表 public boolean isEmpty(){ return N==0; } //获取线性表的长度 public int length(){ return N; } //获取指定位置的元素 public T get(int i){ if (i<0 || i>=N){ throw new RuntimeException("当前元素不存在！"); } return array[i]; } //向线型表中添加元素t public void insert(T t){ if (N==array.length){ resize(array.length*2); } array[N++] = t; } //在i元素处插入元素t public void insert(int i,T t){ if (i<0 || i>N){ throw new RuntimeException("插入的位置不合法"); } //元素已经放满了数组，需要扩容 if (N==array.length){ resize(array.length*2); } //把i位置空出来，i位置及其后面的元素依次向后移动一位 for (int index=N-1;index>i;index--){ array[index]=array[index-1]; } //把t放到i位置处 array[i]=t; //元素数量+1 N++; } //删除指定位置i处的元素，并返回该元素 public T remove(int i){ if (i<0 || i>N-1){ throw new RuntimeException("当前要删除的元素不存在"); } //记录i位置处的元素 T result = array[i]; //把i位置后面的元素都向前移动一位 for (int index=i;index<N-1;index++){ array[index]=array[index+1]; } //当前元素数量-1 N--; //当元素已经不足数组大小的1/4,则重置数组的大小 if (N>0 && N<array.length/4){ resize(array.length/2); } return result; } //查找t元素第一次出现的位置 public int indexOf(T t) if(t==null){ throw new RuntimeException("查找的元素不合法"); } for (int i = 0; i < N; i++) { if (array[i].equals(t)){ return i; } } return -1; } //打印当前线性表的元素 public void showEles(){ for (int i = 0; i < N; i++) { System.out.print(array[i]+" "); } System.out.println(); } @Override public Iterator iterator() { return new SIterator(); } private class SIterator implements Iterator{ private int cur; public SIterator(){ this.cur=0; } @Override public boolean hasNext() { return cur<N; } @Override public T next() { return array[cur++]; } } //改变容量 private void resize(int newSize){ //记录旧数组 T[] temp = array; //创建新数组 eles = (T[]) new Object[newSize]; //把旧数组中的元素拷贝到新数组 for (int i = 0; i < N; i++) { array[i] = temp[i]; } } public int capacity(){ return array.length; } } //测试代码 public class Test { public static void main(String[] args) throws Exception { SequenceList<String> squence = new SequenceList<>(5); //测试遍历 squence.insert(0, "龍弟"); squence.insert(1, "龍龍"); squence.insert(2, "龍弟"); squence.insert(3, "龍哥"); squence.insert(4, "龍龍"); System.out.println(squence.capacity()); squence.insert(5,"aa"); System.out.println(squence.capacity()); squence.insert(5,"aa"); squence.insert(5,"aa"); squence.insert(5,"aa"); squence.insert(5,"aa"); squence.insert(5,"aa"); System.out.println(squence.capacity()); squence.remove(1); squence.remove(1); squence.remove(1); squence.remove(1); squence.remove(1); squence.remove(1); squence.remove(1); System.out.println(squence.capacity()); } }
顺序表的时间复杂度
get(i):无论数据元素量N有多大，只需要一次array[i]就可以获取到对应的元素，时间复杂度为O(1);
insert(int i,T t):每一次插入，都需要把i位置后面的元素移动一次，随着元素数量N的增大，移动的元素也越多，时间复杂为O(n);
remove(int i):每一次删除，都需要把i位置后面的元素移动一次，随着数据量N的增大,移动的元素也越多，时间复 杂度为O(n);
由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显
java中ArrayList实现
java中ArrayList集合的底层也是一种顺序表，使用数组实现，同样提供了增删改查以及扩容等功能。
1.是否用数组实现；
2.有没有扩容操作；
3.有没有提供遍历方式；