目录

往期回顾，专栏一览

🔴 线性表

🔵 顺序表

🍊 概念及结构

🍋 接口实现

🍉 实现

往期回顾，专栏一览

🍉 JavaSE	🍋 AWT	🍑 数据结构
🍅 C1进阶之路	🍒 每日一练	🌽 代码报错
🍈 活动

🍹欢迎各路大佬来到 Nick 主页指点

☀️本期文章将学习 [数据结构] 线性表（顺序表），我是博主Nick。✨

✨我的博客主页：Nick_Bears 🌹꧔ꦿ

🌹꧔ꦿ博文内容如对您有所帮助，还请给个点赞 + 关注 + 收藏✨

🔴 线性表

🔶 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见 的线性表：顺序表、链表、栈、队列、字符串...

   

🔶 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

🔵 顺序表

🍊 概念及结构

    

🔷 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数 据的增删查改。

    

🍑 顺序表一般可以分为：

• 静态顺序表：使用定长数组存储。
• 动态顺序表：使用动态开辟的数组存储。

    

🌽 静态顺序表适用于确定知道需要存多少数据的场景

    

🌽 静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用

  

🍋 接口实现

    

📝 我们来实现一个动态顺序表. 以下是需要支持的接口

public class SeqList {     // 打印顺序表     public void display() {   }     // 在 pos 位置新增元素     public void add(int pos, int data) { }     // 判定是否包含某个元素     public boolean contains(int toFind) { return true; }     // 查找某个元素对应的位置     public int search(int toFind) { return -1; }     // 获取 pos 位置的元素     public int getPos(int pos) { return -1; }     // 给 pos 位置的元素设为 value     public void setPos(int pos, int value) {   }     //删除第一次出现的关键字key     public void remove(int toRemove) {   }     // 获取顺序表长度     public int size() { return 0; }     // 清空顺序表     public void clear() {   } }

      

🍅 难点1：添加元素

思路：

1.添加的索引不能<0或者大于元素当前长度

2.插入添加，一个一个往后移，空出来的填入数据

3.添加完不要忘记++；

    

🍅 难点2：扩容

思路：

1.  Arrays.copyOf(); 需要将拷贝的数组将引用转向原数组

    

🍅 难点3：删除元素

思路：

1.添加的索引不能<0或者大于元素当前长度

2.一个个往前移动，将其覆盖，最后一个元素会保留，下次添加将会覆盖掉，不要担心。

3.删除完不要忘记--；

  

🍉 实现

import java.util.Arrays;public class MyArrayList {    public int[] elem;    public int userSize; // 有效的数据个数    public MyArrayList() { this.elem = new int[2];    }    // 打印顺序表    public void display() { for (int i = 0; i < userSize; i++) {     System.out.print(this.elem[i] + " "); } System.out.println();    }    // 在 pos 位置新增元素    public void add(int pos, int data) { if (pos  userSize) {     System.out.println("post位置不合法");     return; } if (isFull()) {     this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);//扩容 } for (int i = userSize - 1; i >= pos; i--) {     this.elem[i + 1] = this.elem[i]; } this.elem[pos] = data; userSize++;    }    // 判断是否满    public boolean isFull() { return this.userSize == this.elem.length;    }    // 判定是否包含某个元素    public boolean contains(int toFind) { for (int i = 0; i < userSize; i++) {     if (this.elem[i] == toFind) {  return true;     } } return false;    }    // 查找某个元素对应的位置    public int search(int toFind) { try {     for (int i = 0; i < userSize; i++) {  if (this.elem[i] == toFind) {      return i;  }     } } catch (Exception e) {     System.out.println("该元素不存在！"); } return -1;    }    // 获取 pos 位置的元素    public int getPos(int pos) { if (isEmpty()) {     System.out.println("顺序表为空");     return -1; } if (pos = this.userSize) {     System.out.println("pos不合法");     return -1;//所以 这里说明一下，业务上的处理，这里不考虑 } return this.elem[pos];    }    //判断是否为空    public boolean isEmpty() { return this.userSize == 0;    }    // 给 pos 位置的元素设为 value(更新)    public void setPos(int pos, int value) { if (pos = this.userSize) {     System.out.println("pos不合法");     return; } this.elem[pos] = value;    }    //删除第一次出现的关键字key    public void remove(int toRemove) { if (isEmpty()) {     System.out.println("顺序表为空！");     return; } int index = 0; try {     index = search(toRemove);     for (int i = index; i < this.userSize-1; i++) {  this.elem[i] = this.elem[i+1];     }     this.userSize--;     System.out.println("第一次出现的关键字"+toRemove+"已被删除！");// //this.elem[userSize] = null; //如果数组当中是引用数据类型 } catch (Exception e) {     System.out.println("该元素不存在！"); }    }    // 获取顺序表长度    public int size() { return this.elem.length;    }    // 清空顺序表    public void clear() { this.userSize = 0; //引用类型必须令其为null/* for (int i = 0; i < userSize; i++) {     this.elem[i] = null;     this.userSize = 0; }*/    }}

        

🔶 感兴趣的小伙伴可以来测试一下玩玩哦！

public class Demo {    public static void main(String[] args) { MyArrayList myArrayList=new MyArrayList();    }}

🍒顺序表的问题及思考

✨ 顺序表中间/头部的插入删除，时间复杂度为O(N)

  

✨ 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

  

✨ 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续 插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

         

如何解决以上问题呢？

下篇链表的结构带你解决这个问题。