数据结构-线性表-线性表

1. 线性表

   1. what:

      线性表指的是零个或多个数据元素构成的线性序列

   2. others:

      1. 线性表的长度：线性表中数据元素个数n;

      2. 空表：数据元素为0，即n为0；

      3. 线性表常用关系:

         1. 前一项是后一项的直接前驱

         2. 后一项是前一项的直接后继

         3. 第一个元素没有直接前驱

         4. 最后一个元素没有直接后继

         5. 除了第一个和最后一个元素，其他元素有且仅有一个直接前驱和一个直接后继元素

      4. 存储结构

         1. 顺序表

            1. 使用连续的存储空间，按照数据元素在线性表中的序号依次存储数据元素。采用顺序结构存储的线性表称为顺序表。(逻辑上相邻的数据，物理上也相邻)

            2. 常用实现为一维数组

   3. 顺序存储的优缺点：

      1. 优点：存储空间利用率高

      2. 缺点：插入、删除效率低；必须按照实现估计的最大元素个数分配连续的存储空间，难以临时扩大。

   4. 常用顺序表的基本运算

   5. 插入数据：

      1. 需要将其后的数据后移，再将数据放入，此时为可插入情况时。

      2. 代码实现

         /**
          * .
          * 插入元素
          *
          * @param objects 需要插入数据的对象
          * @param o       需要插入的元素对象
          * @param index   需要插入的位置
          * @return 插入是否成功
          */
         private static Object[] insertElement(Object[] objects, Object o, int index) {
                    // 检查数据合法性
                    checkData(objects, index);
                    // 给数据扩容一个单位
                    Object[] newObjects = new Object[objects.length + 1];
                    // 将所有数据取出并存储进新的容器
                    for (int i = 0; i <= objects.length; i++) {
                         // 符合索引位置，直接将元素放入
                         if (i == index) {
                            // 放入数据
                            newObjects[i] = o;
                            // 然后跳过循环
                            continue;
                         }
                       // 将源数据放入新的数据，如果是大于索引的则需要后退一位放入
                       newObjects[i] = objects[i index ? i - 1 : i];
                     }
                     // 返回新的数组对象
                     return newObjects;
         }                
         

   6. 删除数据

      1. 基本原理：非删除对象时我们只需要按照规则放入变量即可，遇到需要删除的对象时，我们直接跳过，将其后的新数组索引前移一位即可，取数据的索引不变

      2. 代码实现如下

         /**
          * .
          * 删除数据元素
          *
          * @param arrays 需要删除的数组
          * @param index  需要删除的位置
          * @return 一个删除后的数组
          */
         private static Object @NotNull [] deleteElement(Object @NotNull [] arrays, int index) {
               // 初始化一个删除后的元素容器
               Object[] newArrays = new Object[arrays.length - 1];
               // 遍历数组元素
               for (int i = 0; i < arrays.length; i++) {
                     // 判断索引是否目标索引
                     if (i == index) {
                       // 如果是则直接跳过
                       continue;
                     }
                // 如果不是则将元素放入
                newArrays[i index ? i - 1 : i] = arrays[i];
               }
                // 返回新的数组
                return newArrays;
         }