[Java数据结构与算法]顺序表详解—模拟实现顺序表

木井巳

发布于 2025-12-16 09:31:06

1060

一、引言

在计算机科学中，线性表是最基本、最常用的一种数据结构。线性表是n个具有相同特性的数据元素的有限序列，常见的线性表包括顺序表、链表、栈和队列等。在Java集合框架中，ArrayList作为最常用的动态数组实现，基于顺序表的理念提供了丰富的操作方法。本文将深入探讨顺序表的实现原理。

二、什么是顺序表？

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。顺序表在内存中占用连续的空间，这使得它能够通过下标直接访问元素，时间复杂度为O(1)。

顺序表的主要操作包括：

public void add(int data)	默认在末尾增加元素
public void add(int pos, int data)	在下标为pos的元素前增加
public boolean contains(int data)	判断是否含有某个元素
public int indexOf(int data)	查找某个元素的对应下标
public int get(int pos)	获取下标为pos的值
public void set(int pos, int data)	将下标为pos的元素设置为data
public void remove(int data)	删除第一次出现的data
public int size()	获取顺序表的长度
public void clear()	清除顺序表
public void display()	打印顺序表

三、顺序表的模拟实现

顺序表的底层逻辑是数组，因此我们可以定义一个数组，大小暂定为10；为了方便统计数组的元素个数,我们定义一个整形变量usedSize用于记录顺序表已有元素的个数。

public class MyArrayList {
    int[] array;
    int usedSize;    //默认初始化为0
    
    public MyArrayList(int[] array) {
        //使用构造方法新建一个数组，长度为10
        this.array = new int[10];  //关于this关键字的用法可以去看我之前写过的类与对象那篇文章
    }
｝

接下来我们开始实现add方法：

前面已经说过，add方法默认是在数组末尾新增元素，并且我们已经有一个变量记录元素个数，因此我们只需在数组的最后一个元素后面利用下标插入新元素即可（最后一个元素的下标刚好是usedSize）。
需要考虑的是当数组已经满了的时候，该怎么操作？
我们可以再写一个扩容的方法，当数组已满，我们就调用该方法将数组扩容（通常是扩容至原来长度的两倍）。

因此add方法的部分可以写成如下：

public void add(int data) {
    if (isFull()) {
        expand();
    }
    this.array[usedSize] = data;
    this.usedSize++;
}

其中 isFull方法和 expand方法分别是数组判满方法和数组扩容方法，具体实现如下：

public boolean isFull() {
    return this.usedSize == this.array.length;
}

private void expand() {
    //扩容为原来长度的两倍
    this.array = Arrays.copyOf(this.array,2*this.array.length);
}

第二个add其实是第一个add的重载，接下来我们来实现：

因为涉及到下标，我们就必须要考虑下标的合法性，以防止空指针异常；
当然了，如果数组满了，我们也需要对数组进行扩容操作；
重点是插入新元素的操作，我们可以将数组以pos位置为界看成两部分：前半部分是不需要改动的，中间是分界线pos，后半部分是需要改动的部分。
利用循环将后半部分的元素一个个往后移，比如现在pos是4，表示我要在下标为4的位置插入一个新元素，那么就将目前在下标为4的位置上的元素往后移到下标为5的位置，这样一来，下标为4的位置就空出来可以放入新元素了。

具体代码实现如下：

public add(int pos, int data) {
    try {
        addCheckPos(pos);    //检查下标合法性
        if (isFull()) {   //数组判满
            expand();     //扩容
        }
        for (int i = usedSize; i >= pos; i--) {
            this.array[i] = this.array[i-1];
        }
        this.array[pos] = data;
        usedSize++;
    } catch (PositionIllegalException e) {
        e.printStackTrace();         //异常处理，当异常出现时会告诉用户出现异常的代码行数
    }
}

其中 try...catch...语句是用于可能出现异常的代码，常用于捕捉异常并抛出。

addCheck方法是用于检查下标合法性的方法，具体实现如下：

private void addCheckPos(int pos) {
    if (pos<0 || pos>usedSize) {
        throw new PositionIllegalException("Illegal position!");
    }
}

接着我们来看看异常的编写：

public class PositionIllegalException extends RuntimeException {
    public PositionIllegalException() {
        super();
    }
    public PositionIllegalException(String message) {
        super(message);
    }
}

其中RuntimeException表示运行时异常，是在程序运行时出现会异常，当该异常被检测到时将会终止程序并抛出异常。

然后是 contains方法的实现：

我们只需要遍历顺序表，找到对应元素即可

具体实现如下：

public boolean contains(int data) {
    for (int i = 0; i < this.array.length; i++) {
        if (array[i] == data) {
            return true;
        }
    }
    return false;
}

indexOf方法的实现其实与 contains方法的实现十分相似：

遍历顺序表，找到对应元素后，返回下标即可
若没有找到对应元素，返回-1，因为数组没有下标为-1的位置

具体实现如下：

public int indexOf(int data) {
    for (int i = 0; i < this.array.length; i++) {
        if (this.array[i] == data) {
            return i;
        }
    }
    return -1;
}

对于 get方法，我们可以：

判断顺序表是否为空
判断下标的合法性，在这个方法中，pos不可以等于usedSize，因为usedSize位置上没有元素
如果前面两个都没问题的话，就返回顺序表中对应下标的值

具体实现如下：

public int public get(int pos) {
    try {
        isEmpty();
        CheckPos(pos);
        return this.array[pos];
    } catch (EmptyException e) {
        e.printStackTrace();
    } catch (PositionIllegalException e) {
        e.printStackTrace();
    }
    return -1;
}

其中 isEmpty方法、CheckPos方法和EmptyException异常的具体实现如下：

public void isEmpty() {
    if (usedSize == 0) {
        throw new EpmtyException("This arraylist is empty!");
    }
}

public void CheckPos(int pos) {
    if (pos<0 || pos>=usedSize) {
        throw new PositionIllegalException("Illegal position!");
    }
}

public class EpmtyException extends RuntimeException {
    public EpmtyException() {
        super();
    }
    public EpmtyException(String message) {
        super(message);
    }
}

set方法与 get方法大体差不多：

检查该顺序表是否为空
检查下标pos是否合法
如果以上都正常，直接将顺序表中的pos位置的元素设置为data即可

具体实现如下：

public void set(int pos, int data) {
    try {
        isEmpty();
        CheckPos(pos);
        this.array[pos] = data;
    } catch (EmptyException e) {
        e.printStackTrace();
    } catch (PositionIllegalException) {
        e.printStackTrace();
    }
}

接下来的 remove方法算是最后一个较复杂的方法了：

我们首先判断顺序表是否为空
然后通过 indexOf方法获取 data 的对应下标
有了下标之后自然需要检查下标的合法性
删除对应下标的元素操作可以逆向操作第二个 add的思路：让需要被删除的元素被后面的元素覆盖即可。那我们就采用遍历的方式，将后面的元素一个个往前移动

具体实现如下：

public void remove(int data) {
    try {
        isEmpty();
        int pos = indexOf(data);
        CheckPos(pos);
        for (int i = pos; i < usedSize-1; i++) {
            this.array[i] = this.array[i+1];
        }
        usedSize--;
    } catch (EmptyException e) {
        e.printStackTrace();
    } catch(PosIllegalException e) {
        e.printStackTrace();
    }
}

接下来的 size方法比较简单：我们只需要返回 usedSize的大小即可

具体实现如下：

public int size() {
    return this.usedSize;
}

clear方法只需要将usedSize置0即可：

public void clear() {
    this.usedSize = 0;
}

display方法只需要遍历顺序表然后逐个打印即可：

public void display() {
    for (int i = 0; i < this.usedSize; i++) {
        System.out.print(this.array[i] + " ");
    }
    System.out.println();
}

至此，顺序表的基本功能我们就全都模拟实现了。

完

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-19，如有侵权请联系 cloudcommunity@tencent.com 删除

int