目录
一、线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
二、顺序表
2.1、顺序表的定义
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
2.2、顺序表的接口实现
public interface List {
// 新增元素,默认在数组最后新增
public void add(int data);
// 在 pos 位置新增元素
public void add(int pos, int data);
// 判定是否包含某个元素
public boolean contains(int toFind);
// 查找某个元素对应的位置
public int indexOf(int toFind);
// 获取 pos 位置的元素
public int get(int pos);
// 给 pos 位置的元素设为 value
public void set(int pos, int value);
//删除第一次出现的关键字key
public void remove(int toRemove);
// 获取顺序表长度
public int size();
// 清空顺序表
public void clear();
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
public void display();
//判断数组是否满了
public boolean isFulled();
}
三、ArrayList
3.1、 ArrayList简介
在集合框架中，ArrayList是一个普通的类，实现了List接口。
注意：
1. ArrayList是以泛型方式实现的，使用时必须要先实例化
2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者 CopyOnWriteArrayList
6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
3.2、ArrayList的实现
在实现顺序表之前，我们要先定义一个数组、一个整型变量和一个构造方法：
public int[] als;
public int usedSize;
public MyArrayList() {
this.als =new int[10];
}
//新增一个元素，默认在数组最后新增
//新增一个元素，默认在数组最后新增
@Override
public void add(int data) {
if(isFulled()){
reSize();
}
als[usedSize]=data;
usedSize++;
}//判断顺序表是否已满
//判断顺序表是否已满
@Override
public boolean isFulled() {
return usedSize==als.length;
}
//若顺序表已满，进行扩容
private void reSize(){
als= Arrays.copyOf(als,2*als.length);
}//在pos位置新增元素data
//在pos位置新增元素data
@Override
public void add(int pos, int data) {
if(pos<=usedSize&&pos>=0){
if(isFulled()){
reSize();
}
for(int i=usedSize-1;i>=pos;i--){
als[i+1]=als[i];
}
als[pos]=data;
usedSize++;
}else{
throw new PosOutOfException("数据不合法");//该异常为我自身设定，各位使用时需另外设定
}
}异常设置的代码：
public class PosOutOfException extends RuntimeException{
public PosOutOfException(String message) {
super(message);
}
}
//判断是否包含元素toFind
//判断是否包含元素toFind
@Override
public boolean contains(int toFind) {
for(int i=0;i<usedSize;i++){
if(als[i]==toFind){
return true;
}
}
return false;
}
//查找某个元素对应的位置,如果未找到，返回-1
//查找某个元素对应的位置,如果未找到，返回-1
@Override
public int indexOf(int toFind) {
int num=-1;
for(int i=0;i<usedSize;i++){
if(als[i]==toFind){
num=i;
break;
}
}
return num;
}// 获取 pos 位置的元素
// 获取 pos 位置的元素
@Override
public int get(int pos) {
if(pos>=0&&pos<usedSize){
return als[pos];
}else{
throw new PosOutOfException("pos位置不合法");
}
}// 给 pos 位置的元素设为 value
// 给 pos 位置的元素设为 value
@Override
public void set(int pos, int value) {
if(pos>=0&&pos<usedSize){
als[pos]=value;
}else{
throw new PosOutOfException("pos位置不合法");
}
}
//删除第一次出现的关键字toRemove
//删除第一次出现的关键字toRemove
@Override
public void remove(int toRemove) {
int index=indexOf(toRemove);
if(index==-1){
return;
}
for(int i=index;i<usedSize-1;i++){
als[i]=als[i+1];
}
usedSize--;
}// 获取顺序表长度
// 获取顺序表长度
@Override
public int size() {
return this.usedSize;
}// 清空顺序表
// 清空顺序表
@Override
public void clear() {
usedSize=0;
}// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
@Override
public void display() {
for(int i=0;i<usedSize;i++){
System.out.print(als[i]+" ");
}
}注意：调用方法时用“.”来调用，以下以display()为例：
public class Main {
public static void main(String[] args) {
MyArrayList myArrayList=new MyArrayList();
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(66);
myArrayList.display();
}
}结果如下：
3.3、ArrayList实现的完整代码
import java.util.Arrays;
public class MyArrayList implements List{
public int[] als;
public int usedSize;
public MyArrayList() {
this.als =new int[10];
}
//新增一个元素，默认在数组最后新增
@Override
public void add(int data) {
if(isFulled()){
reSize();
}
als[usedSize]=data;
usedSize++;
}
//判断顺序表是否已满
@Override
public boolean isFulled() {
return usedSize==als.length;
}
//若顺序表已满，进行扩容
private void reSize(){
als= Arrays.copyOf(als,2*als.length);
}
//在pos位置新增元素data
@Override
public void add(int pos, int data) {
if(pos<=usedSize&&pos>=0){
if(isFulled()){
reSize();
}
for(int i=usedSize-1;i>=pos;i--){
als[i+1]=als[i];
}
als[pos]=data;
usedSize++;
}else{
throw new PosOutOfException("数据不合法");//该异常为我自身设定，各位使用时需另外设定
}
}
//判断是否包含元素toFind
@Override
public boolean contains(int toFind) {
for(int i=0;i<usedSize;i++){
if(als[i]==toFind){
return true;
}
}
return false;
}
//查找某个元素对应的位置,如果未找到，返回-1
@Override
public int indexOf(int toFind) {
int num=-1;
for(int i=0;i<usedSize;i++){
if(als[i]==toFind){
num=i;
break;
}
}
return num;
}
// 获取 pos 位置的元素
@Override
public int get(int pos) {
if(pos>=0&&pos<usedSize){
return als[pos];
}else{
throw new PosOutOfException("pos位置不合法");
}
}
// 给 pos 位置的元素设为 value
@Override
public void set(int pos, int value) {
if(pos>=0&&pos<usedSize){
als[pos]=value;
}else{
throw new PosOutOfException("pos位置不合法");
}
}
//删除第一次出现的关键字toRemove
@Override
public void remove(int toRemove) {
int index=indexOf(toRemove);
if(index==-1){
return;
}
for(int i=index;i<usedSize-1;i++){
als[i]=als[i+1];
}
usedSize--;
}
// 获取顺序表长度
@Override
public int size() {
return this.usedSize;
}
// 清空顺序表
@Override
public void clear() {
usedSize=0;
}
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
@Override
public void display() {
for(int i=0;i<usedSize;i++){
System.out.print(als[i]+" ");
}
}
}
以上便是本篇文章的全部内容，感谢大家的支持！下期见~~~
标签：顺序,Java,int,ArrayList,pos,als,---,数据结构,public From： https://blog.csdn.net/huangtiandi11/article/details/143105241