自己实现集合框架(二):顺序表的实现

这是系列文章，每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现，从而对常用的数据结构和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)。

所以，顺序表具有下列特点：

① 元素的物理存储顺序直接反映表中元素的逻辑顺序，可以随机存取元素。

② 插入和删除效率低。每次插入或者删除一个元素，可能需要移动大量元素，其平均移动次数是顺序表长度的一半。再者，数组容量不可更改，存在因容量小造成数据溢出，或因容量过大造成内存资源浪费的问题。解决数据溢出的办法是，申请另一个更大容量的数组，并进行数组元素复制，但插入效率很低。

五.源代码示例

github地址：点击查看
码云地址：点击查看

打赏

微信扫一扫，打赏作者吧～

欢迎关注人生设计师的微信公众账号
公众号ID：longjiazuoA

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