💕"世事犹如书籍，一页页被翻过去。人要向前看，少翻历史旧账。"💕
作者：Mylvzi
文章主要内容：数据结构之顺序表的模拟实现
一.线性表
1.概念
线性表(liner list)是n个具有相同特性元素的有限序列的集合
相同特性指的是一个线性表内部存储的数据类型要都是相同的，可以都是Integer，String也可以是其他的引用类型
常见的线性表有：顺序表，链表，栈，队列
2.性质
线性表最大特点在于他是一种连续存储数据的结构，其在逻辑上一定是连续的，但是物理上不一定连续，主要是因为线性表既可以通过数组表示，又可以通过链表实现
二.顺序表(ArrayList)
1.概念：
顺序表是使用物理地址连续的内存存储数据的线性表
2.接口实现
ArrayList中有很多内置的接口，不过这里我们先模拟实现一下
1.顺序表的结构
顺序表最大的特点是它使用"物理地址连续"的内存进行数据的存储，在我们学习过的知识中，数组的存储刚好满足顺序表的特点
// 结构 public int[] elem;// 使用数组来存储数据 public int usedsize;// 有效数据个数 // 初始化顺序表 // 默认大小 public static final int DEFAULT_SIZE = 10; public MyArrayList() { this.elem = new int[DEFAULT_SIZE]; } // 用户指定数组大小 public MyArrayList(int initCapacity) { this.elem = new int[initCapacity]; }
2.顺序表的添加
顺序表的添加就是在顺序表中新增一个数据，但是插入的位置要分类讨论，大致上可分为两类：
- 默认插入:在 顺序表的末尾进行数据的插入
- 在指定位置进行插入
1.默认插入
注意在插入数据这样的操作中，要考虑你要插入的容器的容量是否达到最大值，如果达到最大值需要进行扩容，否则就会发生越界访问
// 默认插入 public void add(int data) { // 插入之前要先检查是否需要扩容 if(isFull()) { this.elem = Arrays.copyOf(this.elem,2*this.elem.length); } // 插入 this.elem[usedsize] = data; this.usedsize++; } public boolean isFull() { // 如果有效的数据个数和数组的长度一致 扩容 return this.elem.length == usedsize; }
2.在指定位置插入数据
要在指定位置插入数据需要考虑的是原有的位置已经存在数据了，要想插入新的数据，就要将插入位置之后的所有元素都往后挪动
图解：
代码实现:
// 在指定位置进行插入 public void addPos(int pos,int data) { // 检查pos是否合法 if(pos < 0 || pos > this.usedsize) { throw new posOutOfBoundException(pos + "位置不合法"); } if(isFull()) { this.elem = Arrays.copyOf(this.elem,2*this.elem.length); } // 挪动数据 for (int i = this.usedsize-1; i >= pos; i--) { this.elem[i+1] = this.elem[i]; } // 插入数据 this.elem[pos] = data; this.usedsize++; }
注意:在pos位置插入数据的时候要检查pos是否合法，即不能产生越界访问
3.判断顺序表中是否包含某个元素
遍历顺序表，包含返回true；不包含，返回false
代码实现：
public boolean contains(int key) { for (int i = 0; i < this.usedsize; i++) { if (this.elem[i] == key) { return true; } } // 没找到 return false; }
4.查找某个元素对应的位置
如果数组包含某个元素，则返回其对应的下标
代码实现:
public int indexOf(int key) { for (int i = 0; i < this.usedsize; i++) { if (this.elem[i] == key) { return i; } } System.out.println("数组不包含该元素"); return -1; }
5.获取pos位置的元素
返回pos位置对应的元素
代码实现
public int get(int pos) { // 检查pos 的位置是否合法 if(pos < 0 || pos >= this.usedsize) { throw new posOutOfBoundException(pos + "位置不合法"); } return this.elem[pos]; }
注意：此处要检查pos是否合法，这里的pos最大只能访问到usedSize-1的元素
6.给pos位置的元素设置为value
即更新pos位置的元素
代码实现
public void set(int pos,int value) { // 检查pos 的位置是否合法 if(pos < 0 || pos >= this.usedsize) { throw new posOutOfBoundException(pos + "位置不合法"); } this.elem[pos] = value; }
7.删除第一次出现的关键字key
遍历顺序表，找到值等于key的元素，删除他(只删除第一次出现的key)
但是该则么删除呢？将要删除的元素设置为0？这显然是行不通的，可以采用"数据覆盖"来进行数据的删除，即应该先找到要删除元素的位置，在从后往前进行数据的覆盖
图解
代码实现
public void remove(int key) { // 1.获取key的pos int pos = indexOf(key); if (pos == -1) { System.out.println("没有你要删除的数据！"); return; } // 2.挪动数据 进行删除 注意范围 for (int i = pos; i < this.usedsize-1; i++) { this.elem[i] = this.elem[i+1]; } this.usedsize--; }
8.获取顺序表的长度
代码实现
public int size() { return this.usedsize; }
9.清空顺序表
代码实现
// 清空顺序表 public void clear() { // 如果是引用类型 要一一置空 // for (int i = 0; i < this.usedsize; i++) { // this.elem[i] = null; // } this.usedsize = 0; }
10.自定义异常
/** * Created with IntelliJ IDEA. * Description: * User: 绿字 */ public class posOutOfBoundException extends RuntimeException{ public posOutOfBoundException() { } public posOutOfBoundException(String message) { super(message); } }
三.ArrayList简介
在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：
源码:
数据结构之ArrayList与顺序表(有源码剖析)（二）+https://developer.aliyun.com/article/1413529
