行业知识
【java-数据结构】模拟顺序表，掌握背后的实现逻辑
2026-10-19 01:56:17
来源：互联网转载
���程环境：idea
【java-数据结构】模拟顺序表，掌握背后的实现逻辑
- 1.顺序表是啥
- 2.回忆一下数组是如何存数据的？
- 3.用java语言模拟实现一个顺序表(以存int类型数据为例)
- 3.1描述顺序表
- 用三个成员变量描述顺序表：
- 区分顺序表的最大长度和有效长度
- 区分有效长度usedSize和数组下标
- 3.2显示顺序表中的所有数据
- 3.3在顺序表的最后位置新增一个元素
- 3.4在pos位置新增一个元素
- 3.5判断顺序表中是否包含某个元素
- 3.6查找某个元素对应的位置
- 3.7获取pos位置的元素
- 3.8把pos位置的元素更新为value值
- 3.9删除顺序表中的指定值toRemove
- 3.10清空顺序表中的所有数据
- 3.11获取顺序表的当前长度
- 4.顺序表的优缺点及使用场景
- 5.附完整源码
1.顺序表是啥
官方是这么定义顺序表的：
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。顺序表是线性表的顺序存储结构。
顺序表，底层结构其实就是数组。用数组保存一组相同类型的数据，操作数组就是对数据进行增删改查。
顺序表的物理结构和逻辑结构都可以理解成数组。所以顺序表学起来很简单，也被称为最简单的数据结构。
2.回忆一下数组是如何存数据的？
数组是引用数据类型，数组类型的变量空间里存的是一个地址，该地址指向数据真正所在的空间。
物理地址连续指的就是，数据真正所在的空间是一块连续的内存，这块内存由有限个挨在一起的内存单元构成，数据依次存储在内存单元中。
引用类型的成员变量默认值为null（不指向任何内存）。int类型的成员变量默认值为0 。
数组，线性表，数据结构的基础知识等内容这里不再过多赘述，详情参考评论区链接文章。
3.用java语言模拟实现一个顺序表(以存int类型数据为例)
用java语言模拟实现一个顺序表，首先必定要先创建一个类来表示这个顺序表。类里面有三个成员变量和若干个成员方法，通过这些成员变量完成对顺序表的描述，通过成员方法可以对顺序表进行增删改查等操作。
public class MyArrayList { //顺序表在内存中的起始位置 private int[] elem; //顺序表的有效长度 private int usedSize; //在创建顺序表的时候规定顺序表的最大长度 private static final int DEFAULT_SIZE = 10; public MyArrayList(){ this.elem = new int[DEFAULT_SIZE]; } //根据需求指定顺序表的最大长度 public MyArrayList(int initCapacity){ this.elem = new int[initCapacity]; } //显示顺序表中的所有数据 public void display(){ } //在顺序表的最后位置新增一个元素data public void add(int data){ } //在pos位置新增一个元素data public void add(int pos,int data){ } //判断顺序表中是否包含某个元素 public boolean contains(int toFind){ } //查找某个元素对应的位置 public int indexOf(int toFind){ } //获取pos位置的元素 public int get(int pos){ } //把pos位置的元素更新为value值 public void set(int pos,int value){ } //删除顺序表中的指定值toRemove public void remove(int remove){ } //获取顺序表的当前长度 public int getUsedSize() { return usedSize; } //清空顺序表中的所有数据 public void clear(){ }}3.1描述顺序表
用三个成员变量描述顺序表：
- 数组类型的变量elme存一个地址，指向存储在顺序表中的第一个数据所在的空间。
- 整型变量usedSize是数组的有效长度
- 静态1常量DEFAULT_SIZE和形参initCapacity都是数组的最大长度，前者是实例化一个具体顺序表时（没有指定顺序表的最大长度时）默认规定的，后者是实例化一个具体顺序表的时候指定的。
//顺序表在内存中的起始位置 private int[] elem; //顺序表的有效长度 private int usedSize; //在创建顺序表的时候规定顺序表的最大长度 private static final int DEFAULT_SIZE = 10; public MyArrayList(){ this.elem = new int[DEFAULT_SIZE]; } //根据需求指定顺序表的最大长度 public MyArrayList(int initCapacity){ this.elem = new int[initCapacity]; }区分顺序表的最大长度和有效长度
该顺序表的有效长度为0，最大长度为6
这就不是顺序表。顺序表底层是数组，数组是依次存储相同数据类型的元素的一种线性结构。
该顺序表的有效长度为5，最大长度为6
区分有效长度usedSize和数组下标
usedSize，从1开始。
数组下标，从0开始。
usedSize比数组下标快一个数字。
3.2显示顺序表中的所有数据
思路：遍历顺序表的有效数据，并打印。
时间复杂度：O(n)，n为数组当前长度。
public void display(){ for (int i = 0; i3.3在顺序表的最后位置新增一个元素
以下面这个顺序表为例，怎么在它的最后位置新增一个元素data？
思路：数组的最后一个位置就是数组下标为usedSize的位置。把data数据放在数组下标为usedSize的位置。
时间复杂度：O(1)。
有两个注意点：
- 在顺序表中新增元素后，顺序表的usedSize也要对应++。
- 当顺序表已满，如果要执行新增元素的操作，数组会发生越界访问(数组下标只能到usedSize-1)。为了避免这种情况，在执行新增元素的操作前，先判断一下顺序表是否已满。如果顺序表已满，先扩容2，再新增元素。
//在顺序表的最后位置新增一个元素datapublic void add(int data){ if(isFull()){ this.elem = Arrays.copyOf(this.elem,this.elem.length); } this.elem[this.usedSize] = data; this.usedSize++; }public boolean isFull(){ if(this.usedSize == this.elem.length){ return true; } return false; }3.4在pos位置新增一个元素
以下面这个顺序表为例，怎么在下标为1的位置新增一个元素199？肯定不能把元素199直接放到1下标对应的位置，如果这样，就不是新增元素，而变成更新元素了。
思路：
- 从最后一个有效数据开始向前遍历，一直遍历到pos位置，
- 分别依次把他们都向后移一个数据。（最后一个有效数据的下标是usedSize-1）
- 把要新增的元素填入pos位置。
移动元素的时间复杂度：
- 最好情况下，pos位置是数组有效元素后的第一个位置，意味着不需要移动元素，直接把元素插入到pos位置，时间复杂度为O（1）。
- 最坏情况下，pos位置是第一个位置，意味着要把顺序表中的所有元素向后移动，时间复杂度为O(n)。n是有效元素个数。
- 平均情况下，根据概率原理，pos位置是(0,usedSize-1)之间的可能性是相同的。所以pos位置取数组中间位置可以代表平均情况。意味着要把顺序表中一半元素向后移，移动次数是(n-1)/2，所以时间复杂度是O(n)。n是有效元素个数。
有三个注意点：
- 在顺序表中新增元素后，顺序表的usedSize也要对应要++。
- 当顺序表已满，理论上不能再向顺序表里面新增数据。为了避免这种情况，向顺序表里新增数据前，先先判断一下顺序表是否已满。如果顺序表已满，先扩容，再新增元素。
- 检查pos位置是否合法：
- pos肯定不能是负数。
- pos可以等于usedSize，当pos等于usedSize时，相当于顺序表已满的情况下向数组中新增数据。
- pos不能大于usedSize，当pos大于usedSize时，就不是顺序表了。
public boolean isFull(){ if(this.usedSize == this.elem.length){ return true; } return false; } //在pos位置新增一个元素data public void add(int pos,int data){ if(posusedSize ){ System.out.println(pos +"位置不合法"); return; } if(isFull()){ this.elem = Arrays.copyOf(this.elem,this.elem.length); } for (int i = usedSize-1; i >=pos ; i--) { elem[i+1] = elem[i]; } elem[pos] = data; }3.5判断顺序表中是否包含某个元素
思路：
- 遍历顺序表中的有效元素
- 把数组中的元素和要查找的元素依次做比较
时间复杂度：
- 最坏情况下，顺序表中不包含该元素，时间复杂度为O(n).
- 最好情况下，该元素在顺序表的0下标位置，时间复杂度为O(1)。
- 平均情况下，根据概率原理，该元素在(0,usedSize-1)位置之间的可能性是相同的。所以假设该元素在数组中间位置可以代表平均情况。意味着要进行(n-1)/2比较，所以时间复杂度是O(n)。n是有效元素个数。
有一个注意点：
两个元素之间做比较，如果元素是基本数据类型，可以直接用==进行比较。如果元素是引用数据类型，要用equals()方法或compareTo接口进行比较。equals()方法的返回值是boolean类型，compareTo接口的返回值是整型。==，equals()方法，compareTo接口等关于对象比较的的具体内容见评论区链接文章
//判断顺序表中是否包含某个元素toFind public boolean contains(int toFind){ for (int i = 0; i3.6查找某个元素对应的位置
思路：
- 遍历顺序表中的有效元素
- 把数组中的元素和要查找的元素依次做比较
- 找到了，返回下标；没找到，返回-1。
时间复杂度：
- 最坏情况下，顺序表中不包含该元素，时间复杂度为O(n).
- 最好情况下，该元素在顺序表的0下标位置，时间复杂度为O(1)。
- 平均情况下，根据概率原理，该元素在(0,usedSize-1)位置之间的可能性是相同的。所以假设该元素在数组中间位置可以代表平均情况。意味着要进行(n-1)/2比较，所以时间复杂度是O(n)。n是有效元素个数。
//查找某个元素对应的位置 public int indexOf(int toFind){ for (int i = 0; i3.7获取pos位置的元素
思路：已知pos下标，可以直接获取数组中pos下标的元素
有一个注意点：检查pos位置是否合法
时间复杂度：O(1)。
- pos肯定不能是负数
- pos不能等于usedSize，usedSize比数组下标快一个数字，当pos等于usedSize时，数组越界访问。
- pos不能大于usedSize。
//获取pos位置的元素 public int get(int pos){ if(pos=this.usedSize){ System.out.println(pos+"位置不合法"); return -1; } return this.elem[pos]; }3.8把pos位置的元素更新为value值
思路：已知pos下标，通过赋值，可以直接把pos位置的元素更新为value值。
时间复杂度：O(1)。
有一个注意点：检查pos位置是否合法
- pos肯定不能是负数
- pos不能等于usedSize，usedSize比数组下标快一个数字，当pos等于usedSize时，数组越界访问。
- pos不能大于usedSize。
//把pos位置的元素更新为value值 public void set(int pos,int value){ if(pos=this.usedSize){ System.out.println(pos+"位置不合法"); return; } this.elem[pos] = value; }3.9删除顺序表中的指定值toRemove
以下面这个顺序表为例，怎么删除元素23？
思路：
- 先查找要删除的值在数组中对应的位置（这里可以直接调用3.6中的成员方法indexOf()），获取位置下标index
- 从index位置开始向后遍历，一直遍历到数组的倒数第二个元素所在的位置，
- 分别依次用他们的后一个数据覆盖他们原有的数据。
- 直接usedSize–或者把usedSize-1的位置设置为nulll值
挪动元素的时间复杂度：
- 最好情况下，要删除的元素在数组中的最后一个有效元素，意味着不需要移动元素，直接usedSize–或者把usedSize-1的位置设置为nulll值，时间复杂度为O（1）。
- 最坏情况下，要删除的元素在数组的0下标位置，意味着要把顺序表中的所有元素向前移动，时间复杂度为O(n)。n是有效元素个数。
- 平均情况下，根据概率原理，index在(0,usedSize-1)之间的可能性是相同的。所以index取数组中间位置可以代表平均情况。意味着要把顺序表中一半元素向前移，移动次数是(n-1)/2，所以时间复杂度是O(n)。n是有效元素个数。
有两个注意点：
- 获取到下标index后，要进行判断，index是否存在。
-
- 当前创建的顺序表中，存储是的int类型的数据。遍历结束后，直接usedSize–。当下一次向数组中新增元素的时候，原来usedSize位置的元素就会被覆盖，从而真正达到删除的目的。
- 但是如果顺序表中存储的是地址，直接usedSize–，会导致内存泄漏。即使下一次新增元素的时候，usedSize位置的原地址会被新增地址覆盖，但是原地址指向的空间依然存在，没有被释放，新增地址可能会指向一个新的空间，也可能指向一个已经存在的空间。所以如果顺序表存储的是引用数据类型，此时必须要把usedSize-1的位置设置为nulll值（达到删除该元素的目的并且释放了该元素地址指向的空间），而不能直接usedSize–。
//删除顺序表中的指定值toRemove public void remove(int toRemove){ int index = indexOf(toRemove); if(index == -1){ System.out.println("没有这个数据！"); return; } for (int i = index; i3.10清空顺序表中的所有数据
思路：如果顺序表中存储的是基本数据类型，直接令usedSize为0。如果顺序表中存储的是引用数据类型，把顺序表中的所有有效元素设置为null。
//清空顺序表中的所有数据 public void clear(){ this.usedSize = 0; /*for (int i = 0; i3.11获取顺序表的当前长度
思路：即获取usedSize的值
//获取顺序表的当前长度 public int getUsedSize() { return usedSize; }4.顺序表的优缺点及使用场景
顺序表的优点：
- 底层是连续的数组，通过下标进行随机访问元素很方便，时间复杂度是O(1)。
顺序表的缺点：
- 向顺序表中添加和删除元素，都要进行挪动元素，平均时间复杂度是O(n)。无法做到不移动就能向顺序表中添加或删除元素，时间复杂度降到O(1)。
- 还有扩容的时候：无法做到随用随分配。主要体现在以下两点：
- 向顺序表中新添加元素时，只能按照一定倍数扩容，会浪费空间。
- 扩容最终是调用Arrays.copyOf()实现的。需要申请新空间，也就是先拷贝全部数据，然后把全部数据放到一个新申请的更大的空间中，再释放旧空间。这个过程会有不小的消耗。
顺序表的使用场景：
顺序表适合存储静态数据，即经常对数据进行查找和更新的操作。
5.附完整源码
import java.util.Arrays;public class MyArrayList { //顺序表在内存中的起始位置 private int[] elem; //顺序表的当前长度 private int usedSize; //顺序表的最大长度 private static final int DEFAULT_SIZE = 10; public MyArrayList(){ this.elem = new int[DEFAULT_SIZE]; } //根据需求指定顺序表的最大长度 public MyArrayList(int initCapacity){ this.elem = new int[initCapacity]; } //显示顺序表中的所有数据 public void display(){ for (int i = 0; i =pos ; i--) { elem[i+1] = elem[i]; } elem[pos] = data; } //判断顺序表中是否包含某个元素 public boolean contains(int toFind){ for (int i = 0; iDEFAULT_SIZE为什么是静态常量？static修饰成员变量，表明该变量是类的属性，无论这个类实例化多少个对象，所有对象都共享这个属性。 ↩︎
给数组扩容：借助工具包Arrays中的copyOf()方法给数组扩容。 ↩︎
上一篇：如何建立服务器可放网页？
下一篇：服务器怎么使用mod?
