Biegral Blog

1.顺序表中按位置随机访问的时间复杂度为O（1）；

2.顺序表中的在给定位置插入或者删除需要移动差不多一半的以上的元素，所以时间复杂度为O（n）；

3.存储密度=数据占用的存储量/整个结点占用的存储量。根据这个公式可以得出顺序表的存储密度为1；

所以可以得出以下结论：线性表一般作为查询频繁，插入或者删除比较少的场景下使用。空间使用率上面是比较高的。

下面直接上代码举例说明：

public class SequenceList {
	//数据结构之顺序线性表
	private int n;//数组中的存储长度
	private Object[] table;//顺序表的数组
	public SequenceList(int length){//带参数的构造方法，
		this.table=new Object[Math.abs(length)];//取length的绝对值
		this.n=0;
	}
	
	public SequenceList(){//无参的构造方法
		this(10);
	}
	
	public boolean isEmpty(){//判断顺序表是否为空
		return this.n==0;
	}
	 
	public int length(){//获取顺序表的长度
		return this.n;
	}
	
	public Object get(int index){//获取顺序表中指定位置的元素
		if(index>=0 && index<this.n){
			return this.table[index];
		}else{
			return null;
		}
	}
	
	public boolean set(int index,Object element){//修改顺序表中指定位置的元素
		if(index>=0 && index<this.n && element!=null){
			this.table[index]=element;
			return true;
		}else{
			return false;
		}
	}
	
	public boolean add(int index,Object element){//在顺序表中指定位置添加元素
		if(element==null){
			return false;
		}
		if(this.n==table.length){
			Object[] temp=this.table;
			this.table=new Object[temp.length*2];
			for(int i=0;i<temp.length;i++){
				this.table[i]=temp[i];
			}
		}
		if(index<0){
			index=0;
		}else if(index>this.n){
			index=this.n;
		}
		for(int i=this.n-1;i>=index;i--){
			this.table[i+1]=table[i];
		}
		this.table[index]=element;
		this.n++;
		return true;
	}
	
	public boolean add(Object element){//在顺序表末尾添加元素
		return add(this.n,element);
	}
	
	public boolean remove(int index){//移除顺序表中的指定位置的元素
		if(this.n!=0 && index>=0 && index<this.n){
			for(int i=index;i<this.n-1;i++){
				this.table[i]=this.table[i+1];
			}
			this.table[this.n-1]=null;
			this.n--;
			return true;
		}else{
			return false;
		}
	}
	
	public void clean(){//清空顺序表
		for(int i=0;i<this.n;i++){
			this.table[i]=null;
		}
		this.n=0;
	}
	
	public void disPlay(){//打印顺序表中的所有元素
		for(int i=0;i<this.n;i++){
			System.out.print(this.table[i]+"\t");
		}
		System.out.println();
	}
	public static void main(String[] args) {//类执行入口，用来做具体调用测试的
		SequenceList s=new SequenceList();
		for(int i=0;i<5;i++){
			s.add(i);
		}
//		s.add(4,55);
//		s.disPlay();
//		s.remove(6);
//		s.disPlay();
//		s.set(-1,12);
//		s.disPlay();
	}
}