1、顺序表和链表都属于数据结构的一部分。
2、数据结构:C的数据结构和JAVA的数据结构有什么不一样啊?
数据结构只是一个单独的学科，和语言没有关系。
用不同的语言实现一样的逻辑。

一、线性表

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

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

二、顺序表 - ArrayList

2.1、概念及结构

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

顺序表一般可以分为：

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

静态顺序表适用于确定知道需要存多少数据的场景.
静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用
相比之下动态顺序表更灵活, 根据需要动态的分配空间大小.

2.2、模拟实现顺序表 - MyArrayList

2.2.1、顺序表的属性

public class MyArrayList {//存储数据的数组public int[] elem;//usedSize 拿到的是 数组元素的有效个数public int usedSize;public MyArrayList(){//构造方法，初始化数组的大小为10this.elem = new int[10];}
}

2.2.2、顺序表的方法

打印顺序表

// 打印顺序表public void display() {for(int i = 0; i < usedSize; i++){System.out.print(elem[i] + " ");}System.out.println();}

获取顺序表长度

// 获取顺序表长度public int size() {//usedSize 就是数组元素的有效数据个数，所以这就是顺序表的长度return usedSize;}

在 pos 位置新增元素

// 在 pos 位置新增元素public void add(int pos, int data) {if(pos < 0 || pos > usedSize){System.out.println(pos + "位置不合法，增加失败！");return;}if(isFull()) {//扩容，如果顺序表满了，就扩容，没有满就不扩容this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}//向后移元素for (int i = usedSize - 1; i > pos ; i--) {this.elem[i+1] = this.elem[i];}//插入元素this.elem[pos] = data;//有效数据+1usedSize++;}//判断数组是否满了,如果满了返回true，没有满返回falsepublic boolean isFull(){return this.usedSize == this.elem.length;}

判定是否包含某个元素

// 判定是否包含某个元素public boolean contains(int toFind) {for(int i = 0; i < usedSize; i++){if(elem[i] == toFind){return true;}}return false;}

查找某个元素对应的位置

 // 查找某个元素对应的位置,找到返回该元素下标，没找到返回-1public int search(int toFind) {for(int i = 0; i < this.usedSize; i++){if(elem[i] == toFind){return i;}}return -1;}

获取 pos 位置的元素

// 获取 pos 位置的元素public int getPos(int pos) {if(pos < 0 || pos > this.usedSize){System.out.println("pos位置不合法！");return -1;}return this.elem[pos];}

给 pos 位置的元素设为 value

// 给 pos 位置的元素设为 valuepublic void setPos(int pos, int value) {if(pos < 0 || pos > this.usedSize){System.out.println("pos位置不合法！");return;}this.elem[pos] = value;}

删除第一次出现的关键字

// 查找某个元素对应的位置,找到返回该元素下标，没找到返回-1public int search(int toFind) {for(int i = 0; i < this.usedSize; i++){if(elem[i] == toFind){return i;}}return -1;}//删除第一次出现的关键字keypublic void remove(int toRemove) {//判断顺序表是否为空if(this.usedSize == 0){System.out.println("顺序表为空，删除失败");return;}//index == -1,说明没有这个数据int index = search(toRemove);if(index == -1){System.out.println("没有你要找的数据");return;}//移动元素for(int i = index; i < this.usedSize-1; i++){this.elem[i] = this.elem[i+1];}//记录有效数据this.usedSize--;}

清空顺序表

public void clear() {this.usedSize = 0;}

测试

在进行测试的时候，两边中间都要测试

public class TestDome {public static void main(String[] args) {MyArrayList myArrayList = new MyArrayList();myArrayList.add(0,55);myArrayList.add(1,30);myArrayList.add(2,5);myArrayList.add(3,5);myArrayList.display();myArrayList.remove(55);myArrayList.display();myArrayList.clear();myArrayList.display();}
}

模拟实现 - MyArrayList

public class MyArrayList {//存储数据的数组public int[] elem;//usedSize 拿到的是 数组元素的有效个数public int usedSize;public MyArrayList(){//构造方法，初始化数组的大小为10this.elem = new int[10];}// 打印顺序表public void display() {for(int i = 0; i < usedSize; i++){System.out.print(elem[i] + " ");}System.out.println();}// 获取顺序表长度public int size() {return usedSize;}// 在 pos 位置新增元素public void add(int pos, int data) {if(pos < 0 || pos > usedSize){System.out.println(pos + "位置不合法，增加失败！");return;}if(isFull()) {//扩容，如果顺序表满了，就扩容，没有满就不扩容this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}//向后移元素for (int i = usedSize - 1; i > pos ; i--) {this.elem[i+1] = this.elem[i];}//插入元素this.elem[pos] = data;//有效数据+1usedSize++;}//判断数组是否满了,如果满了返回true，没有满返回falsepublic boolean isFull(){return this.usedSize == this.elem.length;}//扩容，如果顺序表满了，就扩容public void dilatation(){if(this.usedSize == this.elem.length){this.elem = Arrays.copyOf(this.elem,this.elem.length*2);}}// 判定是否包含某个元素public boolean contains(int toFind) {for(int i = 0; i < usedSize; i++){if(elem[i] == toFind){return true;}}return false;}// 获取 pos 位置的元素public int getPos(int pos) {if(pos < 0 || pos > this.usedSize){System.out.println("pos位置不合法！");return -1;}return this.elem[pos];}// 给 pos 位置的元素设为 valuepublic void setPos(int pos, int value) {if(pos < 0 || pos > this.usedSize){System.out.println("pos位置不合法！");return;}this.elem[pos] = value;}// 查找某个元素对应的位置,找到返回该元素下标，没找到返回-1public int search(int toFind) {for(int i = 0; i < this.usedSize; i++){if(elem[i] == toFind){return i;}}return -1;}//删除第一次出现的关键字keypublic void remove(int toRemove) {//判断顺序表是否为空if(this.usedSize == 0){System.out.println("顺序表为空，删除失败");return;}//index == -1,说明没有这个数据int index = search(toRemove);if(index == -1){System.out.println("没有你要找的数据");return;}//移动元素for(int i = index; i < this.usedSize-1; i++){this.elem[i] = this.elem[i+1];}//记录有效数据this.usedSize--;}// 清空顺序表public void clear() {
//        for(int i = this.usedSize - 1; i <= 0; i--){
//            this.elem[i] = 0;
//        }this.usedSize = 0;}
}