开发者社区> lwmdrr6ypmnvi> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Java数据结构————顺序表(增删改查详细实现)

简介: 目录 1.什么是顺序表 2.顺序表的基本功能和结构 3.顺序表基本功能的实现和解析 1.判断线性表是否为空 2.获取指定位置的元素 3.向线性表表添加元素 4.在位置i处插入元素 4.删除指定位置的元素,并返回该元素 5.查找t第一次出现的位置 6.手动扩容方法
+关注继续查看

1.什么是顺序表


在程序中,经常需要将一组(通常是同为某个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等。一组数据中包含的元素个数可能发生变化(可以增加或删除元素)。


对于这种需求,最简单的解决方案便是将这样一组元素看成一个序列,用元素在序列里的位置和顺序,表示实际应用中的某种有意义的信息,或者表示数据之间的某种关系。


这样的一组序列元素的组织形式,我们可以将其抽象为线性表。一个线性表是某类元素的一个集合,还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一,在实际程序中应用非常广泛,它还经常被用作更复杂的数据结构的实现基础。


顺序表是建立在数组的基础上的,我们需要在数组的基础上实现它的特定API功能,具体有什么功能以下


2.顺序表的基本功能和结构


public class SequenceList<T> implements Iterable<T> {
    //存储元素的数据
    private T[] arr;
    //记录当前顺序表中的元素个数
    private int N;
    //构造方法
    public SequenceList(int capacity) {
        this.arr= (T[]) new Object[capacity];
        this.N=0;
    }


解析:首先我们需要一个底层的arr数组来存储元素,这里的T指的是泛型,因为我们还没确定放入的元素类型,有可能放int,String等等,所以先用泛型表示,不明白泛型的可以了解了解。其次用一个N来统计顺序表中的元素个数。在构造方法中,capacity表示我们创建时arr的初始长度,因为泛型是无法直接实例化的,这里我们可以new一个Object数组,因为Object是任何类的父类,所以T为任何类型我们都可以将Object强转为我们需要的数组,N刚开始为0即可。


下面是顺序表需要实现的基本功能


public boolean isEmpty()
判断线性表是否为空
public  T get(int i)
获取指定位置的元素
public void add(T t)
向线性表中添加元素t
public void insert(int i,T t)
在i元素处插入元素t
public T remove(int i)
删除指定位置i处的元素,并返回该元素
public int indexOf(T t)
查找t第一次出现的位置
public void reSize(int newLength)
手动实现扩容功能


3.顺序表基本功能的实现和解析


1.判断线性表是否为空    


//将一个线性表置为空表
    public void clear(){
        this.N=0;
    }
    //判断当前线性表是否为空表
    public boolean isEmpty(){
        return N==0;
    }


解析:判断线性表是否为空,我们只需要返回N是否等于0即可。


2.获取指定位置的元素

//获取指定位置的元素
    public  T get(int i){
        return arr[i];
    }

解析:数组可以直接索引对应位置的元素


3.向线性表表添加元素        

//向线性表中添加元素t
    public void add(T t){
        if(N== arr.length){
            reSize(2*N);
        }
        arr[N++]=t;
    }

      解析:添加时,我们首先判断数组arr是否已经装满,如果满了会先调用我们的扩容方法增加数组长度,在后面会详细解析。然后arr[N]这个位置加入元素即可,然后N会自增1,表示元素个数多了一个。


4.在位置i处插入元素

//在i元素处插入元素t
    public void insert(int i,T t){
        if(N== arr.length){
            reSize(2*N);
        }
        //把i元素开始后面的元素都向后移一位
        for(int j=N-1;j>=i;j--){
            arr[j+1]=arr[j];
        }
        N++;
        arr[i]=t;
    }

       解析:插入元素我们仍然需要判断是否需要对数组进行扩容,然后我们需要通过循环将i位置后的元素都向后移一个位置,最后将t放入arr【i】位置即可,别忘记N也需要加1。


5.删除指定位置的元素,并返回该元素

//删除指定位置i处的元素,并返回该元素
    public T remove(int i){
        if(N<arr.length/4){
            reSize(N/2);
        }
        T t=arr[i];
        for(int j=i;j<N;j++){
            arr[j]=arr[j+1];
        }
        N--;
        return t;
    }


解析:在这里我们也调用了扩容方法,但这里其实我们是判断数组是否过长,当我们的存储元素的个数小于数组长度的1/4,我们最好将数组长度缩小一半,以防止对内存的浪费。这里我们先将i处的元素用一个变量t保存。然后将i处后的元素依次向前移动一位,然后让N减1,最后返回变量t即可。


6.查找t第一次出现的位置  

public int indexOf(T t){
        for (int i = 0; i < N; i++) {
            if(arr[i]==t) return i;
        }
        return -1;
    }

解析:这里我们直接使用暴力遍历查找位置,当然有很多更好的查找算法可以实现,比如二分查找等等,元素不多的情况下使用哪种都可以。如果没查询到我们返回一个-1表示该表中没有需要查询的t元素。


7.手动扩容方法

//手写扩容方法
    public void reSize(int newLength){
        T[] a=arr;
        T[] list = (T[]) new Object[N*2];
        for (int i = 0; i < arr.length; i++) {
            list[i]=a[i];
        }
        arr=list;
    }

解析:扩容方法的实现其实非常简单,就是判断直接生成一个长度为原数组两倍的数组,并把旧数组的元素遍历进新数组,然后将新数组赋值给就数组即可。之所以要会手动扩容,因为java中的集合类ArrayList就有自动扩容的功能,它的功能与逻辑结构类似我们的顺序表,懂得手动扩容使我们更容易阅读ArrayList的源码,更好的理解和掌握它。


总结:顺序表是非常简单且入门的一种数据结构,他与我们的数组几乎一致,但越是简单的东西越不能大意,我们需要做到可以熟练的手动写成它的各种功能,达到信手拈来的地步。基础学好才更易于我们学习后面更复杂的数据结构。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
java架构师系列1-数据结构(2)数组
在上一章节中已经对数据结构的基本概念有了了解,主要就是数据结构研究的三个方面(逻辑结构、存储结构、算法)。还有两个重要的词汇:时间效率和空间效率。这一节开始了解最基本的数据结构-数组。
35 0
《Java小子怒闯数据结构九重天》第一重天——数组
自古以来数据结构界就分为九重天,据说冲破这九重天之后就可以去进攻算法界最终修炼最后成佬,受万人敬仰,以下内容先讲述第一重内容。
55 0
Java数据结构--稀疏数组和队列(一)
Java数据结构--稀疏数组和队列(一)
51 0
Java数据结构--稀疏数组和队列(三)
Java数据结构--稀疏数组和队列(三)
44 0
JAVA数据结构--数组
JAVA的一维数组的声明方式:type var[]; 或type[] var; 声明数组时不能指定其长度(数组中元素的个数), Java中使用关键字new创建数组对象,格式为:数组名 = new 数组元素的类型 [数组元素的个数] // orderedArray.
586 0
Coap协议接入物联网平台(java实现)
本文介绍基于开源的CoAP协议进行对称加密自主接入的流程,并提供java示例代码。
1323 0
【OSS最佳实践】JAVA实现RTMP推流上传OSS的签名URL
背景介绍 OSS支持使用RTMP协议推送H264编码的视频流和AAC编码的音频流到OSS。推送到OSS的音视频数据可以点播播放;在对延迟不敏感的应用场景,也可以做直播用途。RTMP推流上传的流程是创建LiveChannel以后生成推流地址,关于这块的介绍在官方帮助文档里也有介绍,具体可以参考文档"RTMP推流上传"。
1836 0
教你快速实现类对象的序列化/反序列化 | 带你学《Java语言高级特性》之七十
上一节中我们通过在类中实现Serializable声明该类能够序列化,本节将带领读者借助ObjectOutputStream类和ObjectInputStream类实现对象的序列化和反序列化。
662 0
System类助力标准IO实现 | 带你学《Java语言高级特性》之六十六
在我们日常的生活中,计算机与我们的沟通主要是通过显示器和键鼠设备来完成的,而在Java中,显示器的输出功能和键鼠设备的输入功能则是依赖于System类的支持,本节将介绍它的相关内容。
712 0
文章
问答
文章排行榜
最热
最新
相关电子书
更多
阿里特邀专家关键:Java无锁集合代码分析
立即下载
Java高级特性入门(二)
立即下载
阿里云MongoDB备份恢复功能说明和原理介绍
立即下载