目录
顺序表的实现
顺序表的遍历
顺序表的容量可变
顺序表的时间复杂度
java中ArrayList实现
线性表是n个具有相同特性的数据元素的有限序列。常见的线性表有:顺序表、链表、栈、队列等。
线性表的分类：顺序表(数组)和链表
顺序表的实现
顺序表API设计:
| 类名 | SeqenceList |
| 构造方法 | SequenceList(int capacity):创建容量为capacity的SequenceList对象 |
| 成员方法 | 1.public void clear():清除线性表 2.public boolean isEmpty:判断线性表是否为空 3.public int length():获取线性表中元素的个数 4.public T get(i):读取并返回线性表的第i个元素 5.public void insert(int i,T t):在线性表的第i个元素之前插入一个值为t的数据元素 6.public void insert(T t):在线性表中添加一个元素t 7.public T remove(int i):删除并返回线性表中第i个数据元素 8.public int indexOf(T t):返回线性表中首次出现该元素的序号 |
| 成员变量 | 1.private T[] array:存储元素的数组 2.private int N :当前线性表的长度 |
顺序表的代码实现
//顺序表实现
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.有没有提供遍历方式；