专栏首页ZackSockJava数据结构告诉你如何选用数据集合(2)顺序表

Java数据结构告诉你如何选用数据集合(2)顺序表

今天接着上次的内容详细讲,用Java实现一个顺序表。名字就取MyArrayList,有点随便。上次讲了,顺序表的实现是使用数组实现的,那么在编写顺序表的时候就需要一个成员数组。但是数组是定长的,要怎么实现增删呢?实现思路如下,后面再具体解释:

1、定义一个变量size,用来表示数组的长度,取一个合理的初始值

2、1、先创建一个定长的数组,长度为size

3、定义一个变量length代表MyArrayList的长度(这里要注意,不是数组的长度)

那么怎么实现的,首先创建MyArrayList的时候把数组创建出来。这个时候数组长度是size,而MyArrayList的长度是0。在MyArrayList当中,size和length是两个不同的值。size是实际数组的长度,而length是我们告知别人这个顺序表的长度。那么这个类的成员变量如下:

public class MyArrayList<T> {
    //用来存数据的数组
    private T[] data;
    //数组的长度
    private int size = 100;
    //顺序表的长度
    private int length = 0;

    /**
    *    构造方法
    */
    public MyArrayList(){
        //在创建MyArrayList时,创建数组
        data = (T[])new Object[size];
    }
}

上面的代码很简单,因为要代码通用利用了泛型。那么我们来实现一下其他几个重要的方法,先是在队尾添加:

/**
* 将数据插入到队尾
* @param value 插入的值
*/
public void add(T value){
    //如果长度没有超过size,就直接添加元素
    if(length < size){
        data[length] = value;
    }else{
        //原数组不够用
        moreData();
        data[length] = value;
    }
    //长度增长
    length++;
}

长度没超过size的时候大家都知道,直接在数组最后面加一个元素就好了。但是大于size再添加的话,会下标越界,这个时候就需要另外处理。这里使用自定义的moreData()方法,因为后面还有指定位置添加数据也要用到这个方法。下面一起给大家讲,再来看看指定位置添加数据:

/**
* 指定下标插入
* @param value 插入的值
* @param index 插入的下标
*/
public void add(T value, int index){
    if(index >= size){
        System.out.println("下标越界无法添加");
    }else if(length + 1 > size){
        moreData();
        addDataByIndex(value, index);
    } else{
        addDataByIndex(value, index);
    }
}

先是判断是否越界,再判断数组长度够不够。这里的话又有一个自定义方法addDataByIndex(),因为重复的关系,抽了出来。下面我们分别看一下moreData()和addDataByIndex():

/**
* 当元素组不够用时调用此方法
*/
private void moreData(){
    //把data数组原有的数据取出
    T[] temp = data.clone();
    //从新创建一个更长数组
    size += 50;
    data = (T[])new Object[size];
    //把temp中的数据复制回来并添加新的值
    for (int i = 0; i < temp.length; i++){
        data[i] = temp[i];
    }
}

因为数组长度不能改变的缘故,当长度不够时,只能重新创建一个数组。但是在创建之前,要先把数组原数据记录下来(这里用了temp数组),然后再把原数据放入变长后的data数组。

接下来是addDataByIndex()方法:

/**
* 通过下标添加数据的实现
* @param value 插入的值
* @param index 插入的下标
*/
private void addDataByIndex(T value, int index){
    //创建一个数组存储index后面的数据
    T[] temp = (T[])new Object[length - index];
    for(int i = index, j = 0; i < length; i++, j++){
        temp[j] = data[i];
    }
    //插入数据
    data[index] = value;
    //补足后面数据
    for(int i = index + 1, j = 0; i < length+1; i++, j++){
        data[i] = temp[j];
    }
    length++;
}

先把从index开始的数据保存下来,然后在index插入要插入的数据,然后再把index后面的数据重新赋值原先的。其实实际上就是从index个元素开始后移。

接下来就是删除数据。这里的话我图方便,简化了一下,没有考虑size的大小:

/**
* 删除队尾的数据
*/
public void delete(){
    if(length > 0){
        length--;
        //复制数组中的数据
        T[] temp = data.clone();
        data = (T[])new Object[size];
        for(int i = 0; i < length; i++){
            data[i] = temp[i];
        }
    }else{
        System.out.println("没有可以删除的元素了");
    }
}

这里就是把数据复制到temp当中,然后重新创建了一个data。再把除队尾的数据赋值回data。应该还有其它办法,这里只作为参考。

然后是通过下标删除:

/**
* 删除指定位置的数据
* @param index 下标
*/
public void delete(int index){
    if(index < 0 || index > length - 1){
        System.out.println("下标越界了");
    }else{
        length--;
        T[] temp = data.clone();
        data = (T[])new Object[size];
        for(int i = 0; i < length; i++){
            if(i < index){
                data[i] = temp[i];
            }else{
                data[i] = temp[i + 1];
            }
        }
    }
}

这里就是要以index为界限了,前面的是照常赋值,之后的就要赋值后面一(i + 1)个了。还有一些其它方法大致,这里也就不详细实现了。

下面来解决两个问题:

①为什么顺序表查询快?

这里我们没有去实现查询方法,但是我们知道顺序表的底层实现是通过数组的。可以说顺序表的查询就是数组的查询,而且数据存储在相邻的内存,所以查询的时候快。

②为什么顺序表插入慢?

我们已经实现了插入和删除方法,会发现有多次复制。我们在对中插入,大概是这么一个步骤:保存index到队尾的数据->插入数据->把保存的数据赋值回来。删除大概也是这么个类似的流程。这样就消耗了很多资源,所以速度要慢。在数据少的时候感觉不到什么,数据量一大就有天朗之别。所以学习数据结构还是非常有必要的,今天就先到这里。

本文分享自微信公众号 - ZackSock(AndrewRubin),作者:ZackSock

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java增强原有方法的三种方式

    这个比较容易理解,而且我们也用的挺多的。但是用这个方法有一个前提,就是我们能控制类的创建。这种时候,才能这么做。比如工场模式就不能这样。

    ZackSock
  • JavaScript快速实现手动轮播

    这个实现起来还是非常简单的,实现方法也多种多样。今天给大家介绍一个非常巧妙的方法,利用JS中的this。

    ZackSock
  • C语言指针(上)

    定义指针变量的符合为*,如下定义了三个指针变量。它们的变量名为pi、pj、pf,而不是*pi、*pj、*pf。*号在此只用来声明。

    ZackSock
  • Java实现基本数据结构(一)——数组

    首先,我们先设计一个静态的数组,以int数组为例。不考虑扩容,先从最简单的类来理解数组的基本功能。 数组可以表示为下图:

    星如月勿忘初心
  • 封装数组之改进为泛型数组

    前言:通过上一节我们对我们需要封装的数组,进行了基本的增删改查的封装,但只局限于int类型的操作,为了能提供多种类型数组的操作,我们可以将其进一步封装为泛型数组...

    wfaceboss
  • 搞定数据结构-数组结构

    从数组存储的内存模型来看,“下标”最确切的定义应该是”偏移”,如果用a来表示数组的首地址,a0 就是偏移为0的位置,也就是首地址,a k就表示偏移k个type_...

    用户3045442
  • 算法学习之动态数组类

    让我们的数据结构可以放置“任何”数据类型 不可以是基本数据类型,只能是类对象 boolean,byte , char,short,int,long,floa...

    慕白
  • C++ 手把手教你实现可变长的数组

    假设我们要实现一个会自动扩展的数组类,我们需要实现函数呢?先从下面 main 函数使用的功能,看看有什么函数是需要我们实现的。

    小林coding
  • 看得见的数据结构Android版之表的数组实现(数据结构篇)

    张风捷特烈
  • 几种常用的JS类定义方法

    // 方法1 对象直接量 var obj1 = { v1 : "", get_v1 : function() { return ...

    joshua317

扫码关注云+社区

领取腾讯云代金券