[数据结构与算法]01初级实现-顺序表-线性表-数据结构和算法

1 概述

1.1 线性表

• 线性表定义：

  • 线性表*（linear list）*是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。[1]

• 相关概念：长度，空表，索引（位序），前驱元素，后继元素

  • 线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。[1]

    线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱 。[1]

• 优点：线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。[2]

• 分类：线性表中的存储方式可以是顺序存储，也可以是连式存储。根据存储方式的不同分为顺序表和链表。

1.2 顺序表

• 顺序表定义：

  • 顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。[2]

  存储图示：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-083Mqsq4-1664893241022)(L:\study\DataStructureAndAlgorithms\java\data-structure\linear\2022-10-02-array.drawio.png)]

2 API设计

? 了解了顺序表的概念特点及应用后，我们自己来设计下顺序表的API。

3 初级实现和测试

3.1 构造方法

• 空参，源码

  public SequenceListJunior() {
          this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
      }
  

  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA ：默认的空顺序表实例，区别于EMPTY_ELEMENTDATA，用于第一次添加元素。

• 带参-容量，源码：

  /**
       * 指定容量
       * @param initialCapacity   初始容量
       */
      public SequenceListJunior(int initialCapacity) {
          this.elementData = new Object[initialCapacity];        
      }
  

3.2 成员方法

• clear：情况顺序表

  public void clear() {
          if (this.size > 0) {
              for (int i = 0; i < this.size; i++) {
                  // 每个元素置空
                  this.elementData[i] = null;
              }
              this.size = 0;
          }
      }
  

• isEmpty：判断顺序表是否为空

  /**
       * 判断顺序表是否为空
       * @return          true如果顺序表为空;否则false
       */
      public boolean isEmpty() {
          return this.size == 0;
      }
  

  • 如果顺序表对象为null呢？那么调用该方法就会报NullPointerException异常

• size：获取顺序表大小，就是实际存储了多少个元素

  /**
       * 获取顺序表大小
       * @return      顺序表大小
       */
      public int size() { return this.size; }
  

• add(E e)：顺序表添加元素e

  /**
       * 插入元素
       * @param e     插入顺序表的元素
       */
      public boolean add(E e) {
          // 默认末尾插入
          this.elementData[size++] = e;
          return true;
      }
  

  • 如果顺序表容量不够怎么办？
  • 为啥方法要返回boolean呢？参考ArrayList源码

• add(int index,E e)：指定位置插入元素

  /**
       * 在指定索引处插入元素
       * @param index
       * @param e         待添加元素
       */
      public void add(int index, E e) {
          // 索引i之后元素后移
          for (int i = this.size; i > index; i--) {
              this.elementData[i] = this.elementData[i - 1];
          }
          // 设置索引i位置元素为e
          elementData[index] = e;
          // 数组大小加1
          size++;
      }
  

  • 如果顺序表容量不够怎么办？
  • 如果指定的索引index不在0~size内怎么办？
  • 元素后移操作，i = this.size不会索引越界吗？下面改进

• remove(int index)：移除指定位置的元素

  /**
       * 删除指定索引处元素
       * @param index
       * @return
       */
      public E remove(int index) {
          // 保留要删除的元素
          Object o = this.elementData[index];
          // 元素迁移
          for (int i = index; i < this.size - 1; i++) {
              this.elementData[i] = this.elementData[i + 1];
          }
          // 顺序表大小减1
          this.elementData[size--] = null;
          return (E) o;
      }
  

  • 索引index越界问题
  • 元素迁移是否可以优化，元素迁移是否越界

• toString()：

  @Override
      public String toString() {
          StringBuilder sb = new StringBuilder();
          sb.append("[");
          for (int i = 0; i < this.size; i++) {
              if (i == this.size - 1) {
                  sb.append(this.elementData[i]);
              } else {
                  sb.append(this.elementData[i]).append(", ");
              }
          }
          sb.append("]");
          return sb.toString();
      }
  

3.3 简单测试

• 源码：

public class TestSequenceList {
    public static void main(String[] args) {
        SequenceListJunior<Integer> slj = new SequenceListJunior<>(5);
        slj.add(22);
        slj.add(5242);
        slj.add(52);
        System.out.println(slj);
        System.out.println("原数组大小: " + slj.size() );
        System.out.println("====移除索引为0的元素: " + slj.remove(0));
        System.out.println(slj);
        System.out.println("移除后数组大小: " + slj.size());
    }
}

• 输出：

  [22, 5242, 52]
  原数组大小: 3
  ====移除索引为0的元素: 22
  [5242, 52]
  移除后数组大小: 2
  

4 后记

? 以上为顺序表的初级实现，有很多问题和不完善的地方，后面我们参考ArrayList源码对上述代码进行改进。完整源代码在下面代码仓库。

QQ:806797785

源代码仓库地址：https://gitee.com/gaogzhen/algorithm

参考：

[1]百度百科.线性表[EB/OL].2022-05-08/2022-10-02.

[2]百度百科.顺序表[EB/OL].2022-05-09/2022-10-02.

[3]黑马程序员.黑马程序员Java数据结构与java算法全套教程，数据结构+算法教程全资料发布，包含154张java数据结构图[CP/OL].2020-01-18/2022-10-02.