这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现,从而对常用的数据结构和
java
集合有个大概的了解。当然实现没有java
集合的实现那么复杂,功能也没有那么强大,但是可以通过这些简单的实现窥探到底层的一些共性原理。
在之前的文章自己实现集合框架(一):线性表接口中已经定义了线性表的接口,那么下面具体说下顺序表的实现。
一. 顺序表的存储结构
顺序表通常采用数组存储数据元素,数据元素在数组中的物理顺序与逻辑顺序完全相同。
数组是顺序存储的随机存取结构,它占用一组连续的存储单元,通过下标识别元素,元素地址是下标的线性函数。一个下标能够唯一确定一个元素,所以存取任何一个元素所花费的时间复杂度是O(1)
。数组一旦占用一片存储空间,这片存储空间的地址和长度是确定的,不能更改。数组的内存分配有静态和动态两种方式,静态数组和动态数组都是定长的,当数容量不够时,都不能就地扩容。
二. 顺序表类的实现
顺序表类SeqList
是线性表顺序存储结构的一种实现,类似于java
集合框架里的ArrayList
的实现,它有两个私有成员变量table
和n
,table
是一个存放表元素的对象数组;n
为线性表长度,n≤table.length
。SeqList
声明如下,它实现了线性表接口LList。
1. 定义类并实现LList接口,添加构造函数
package org.light4j.dataStructure.linearList.seqList;
import org.light4j.dataStructure.linearList.LList;
public class SeqList<E> implements LList<E> { //顺序表类,实现线性表接口
private Object[] table; // 对象数组,私有成员
private int n; //顺序表长度
/**
* 指定空表的默认容量
*/
public SeqList(){
this(16);
}
/**
* 构造方法,创建指定容量的空表
* Math.abs(i)返回参数的绝对值
*/
public SeqList(int capacity){
this.table=new Object[Math.abs(capacity)];
this.n=0;
}
}
代码解释:
①
SeqList
类声明为实现线性表接口LList
的泛型类,泛型参数E
表示线性表元素的数据类型。当声明SeqList
类的一个对象并创建实例时,指定泛型参数E
为一个确定的类。泛型E
的实际参数必须是类,不能是基本数据类型。如果需要表示基本数据类型,则必须采用数据类型包装类,如Integer
等。
2. 判断顺序表是否为空
/**
* 判断顺序表是否为空,若空返回true
*/
@Override
public boolean isEmpty() {
return this.n==0;
}
3. 返回顺序表长度
/**
* 返回顺序表长度
*/
@Override
public int length() {
return this.n;
}
4. 返回指定位置的对象
/**
* 返回index(初始值為0)位置的对象,若序号无效,返回null
*/
@Override
public E get(int index) {
if(index>=0&&index<this.n){
return (E) this.table[index];
}
return null;
}
代码解释:
① 当
get(index)
等方法的参数index
所指定序号不正确时,不能正常执行操作,将产生错误,需要传递错误信息。解决的方案有两种:一种是方法返回错误信息,另外一种是抛出异常。为了简化程序,这里选择第一种解决方案,当方法返回null
值时表示操作不成功。因此约定,线性表中数据元素不能是空对象(null
)。
5. 给指定位置赋值
/**
* 设置index位置的对象为element,若操作成功,返回原对象,否则返回null
*/
@Override
public E set(int index, E element) {
if(index>=0&&index<this.n&&element!=null){
E old=(E)this.table[index];
this.table[index]=element;
return old;
}
return null;
}
6. 在指定位置插入值
/**
* 在index位置插入element对象,若操作成功返回true,不能插入null
*/
@Override
public boolean add(int index, E element) {
if(element==null){
return false; //不能插入null
}
if(this.n==this.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]; //复制数组元素,O(n)
}
}
if(index<0){
index=0; //下标容错
}
if(index>this.n){
index=this.n; //下标容错
}
for(int j=this.n-1;j>=index;j--){ //元素后移,平均移动n/2
this.table[j+1]=this.table[j];
}
this.table[index] = element;
this.n++;
return true;
}
代码解释:
① 顺序表的插入操作要移动数据元素。在顺序表元素
ai
位置插入元素element
,首先必须将元素ai
以及后面的元素向后移动,空出一个位置,然后将element
插入。② 当插入一个元素时,如果数组
table
已经装满,为了能够使插入操作正常运行,需要自动扩充容量,add()
方法创建一个容量为原数组两倍的新数组。并将原数组中的元素复制到新数组中。若使用new
申请存储空间失败,java
虚拟机将产生内存溢出错误,并终止程序运行。
7. 在末尾位置插入值
/**
* 在顺序表最好插入element对象
*/
@Override
public boolean add(E element) {
return this.add(this.n, element);
}
8. 移除元素
/**
* 移去index位置的对象,若操作成功,则返回被移去对象,否则返回null
*/
@Override
public E remove(int index) {
if(this.n!=0&&index>=0&&index<this.n){
E old = (E)this.table[index];
for(int i=index;i<this.n-1;i++){ //元素前移,平均移动n/2
this.table[i]=this.table[i+1];
}
this.table[this.n-1]=null;
this.n--;
return old; //若操作成功,则返回被移除对象
}
return null; //未找到删除对象,操作不成功,返回null
}
代码解释
① 顺序表的删除操作要移动数据元素。删除顺序表元素
ai
,必须将元素ai+1
以及后面的元素向前移动。
9. 清空顺序表
/**
* 清空顺序表
*/
@Override
public void clear() {
if(this.n!=0){
for(int i=0;i<this.n;i++){
this.table[i]=null;
}
this.n=0;
}
}
10. 重写toString()方法
/**
* 重写toString()方法
*/
@Override
public String toString() {
String str="(";
if(this.n!=0){
for(int i=0;i<this.n-1;i++){
str+=this.table[i].toString()+",";
}
str+=this.table[this.n-1].toString();
}
return str+")";
}
三.测试
测试代码如下:
package org.light4j.dataStructure.linearList.seqList;
import org.light4j.dataStructure.linearList.LList;
public class Test {
public static void main(String[] args) {
// 初始化默认值容量的SeqList
LList<String> defalutValueList = new SeqList<String>();
// 添加A,B,C三个元素
defalutValueList.add("A");
defalutValueList.add("B");
defalutValueList.add("C");
// 输出元素个数
System.out.println("defalutValueList线性表元素个数:"+defalutValueList.length());
// 初始化容量值为10的SeqList
LList<String> specifiedValueList = new SeqList<String>(10);
// 添加D,E,F,G四个元素
specifiedValueList.add("D");
specifiedValueList.add("E");
specifiedValueList.add("F");
specifiedValueList.add("G");
// 输出元素个数
System.out.println("specifiedValueList线性表元素个数:"+specifiedValueList.length());
}
}
运行结果如下图所示:
四.顺序表操作的效率分析
顺序表是一种随机存取结构,存取任何一个元素的get()
,set()
方法的时间复杂度是O(1)
。
对顺序表进行插入或者删除操作时,算法所花费的时间主要用于移动元素。设表长度为n
,若在第一个位置插入新元素,则需要移动n
个元素;若在表的最后一个元素之后插入新元素,则不需要移动元素。在等概率情况下,插入一个元素平均需要移动一半的元素,时间复杂度为O(n)
。同理,删除一个元素的时间复杂度也为O(n)
。
所以,顺序表具有下列特点:
① 元素的物理存储顺序直接反映表中元素的逻辑顺序,可以随机存取元素。
② 插入和删除效率低。每次插入或者删除一个元素,可能需要移动大量元素,其平均移动次数是顺序表长度的一半。再者,数组容量不可更改,存在因容量小造成数据溢出,或因容量过大造成内存资源浪费的问题。解决数据溢出的办法是,申请另一个更大容量的数组,并进行数组元素复制,但插入效率很低。
五.源代码示例
公众号ID:longjiazuoA

未经允许不得转载:人生设计师 » 自己实现集合框架(二):顺序表的实现