ArrayList顺序表零基础详解（上）

              hello呀！各位，这里是Sunlightʊə。

目前大三，主要在学习Java语言。可以一起交流呀！

相关文章：

数据结构第一课 —— 时间和空间复杂度

Java数据结构第三课 —— 泛型（2）

Java数据结构第二课 —— 泛型（1）

最新文章：

新学期，新Java

---

目录

前言：

 一、线性表

二、顺序表

1、接口的实现

三、ArrayList简介

---

前言：

上次我们谈到了数据结构的一大特殊参数化类型——>泛型。

首先，我们要明确，数据结构中有三个重要组成： 逻辑结构、存储结构、数据运算 。

逻辑结构：指的是数据之间的逻辑关系，从逻辑关系上去描述数据。逻辑结构包括线性结构和非线性结构两种。其中包括集合、线性结构、树形结构、图形结构。

逻辑结构是一种“依赖关系”，描述的仅仅是数据元素之间的关系，除了描述数据元素之间的关系外，再也没有其他的含义了。

特别注意：逻辑结构与存储结构无关。

 存储结构：也称为数据的物理结构，是数据元素及其关系在计算机中的存储方式，有：顺序存储、链式存储、散列存储和索引存储。

 数据运算：是对数据依某种模式而建立起来的关系进行处理的过程。是指对数据实施的操作，数据运算最终需要在对立的存储结构上用算法实现，所以数据运算分为运算定义和运算实现两个层面。（这里我们暂不深究。

 那么，逻辑结构中的线性表又是什么呐？

 一、线性表

线性表：指的是N个具有相同特性的数据元素的有限序列。

 线性表在逻辑结构中呈现线性结构，也就是说它是一条连续的直线。

但是，线性表在物理结构上（也就是说在存储结构上）并不一定是连续的，线性表在物理上存储时，通常会以数组和链式结构的形式进行存储。

 

二、顺序表

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

 也就是说顺序表的底层其实是一个动态的数组。

ArrayList底层其实是一个动态的数组，称为顺序表。

1、接口的实现

public class MyArrayList {
    public int[] elem;//数组
    public int usedSize;//记录有效元素的个数
    public static final int DEFAULT_SIZE=10;
 
    public MyArrayList(){
        this.elem=new int[DEFAULT_SIZE];
    }
 
    // 新增元素,默认在数组最后新增
    public void add(int data) {
        //考虑越界和扩容
        //1.检查当前顺序表是不是满了
        if(isFull()){
            //2.如果满了就要进行扩容
            this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
        }
        //3.
        this.elem[this.usedSize]=data;
        //4.
        this.usedSize++;
    }
 
    public boolean isFull(){
        if(size()>=this.elem.length){
            return true;
        }
        return false;
 
    }
 
    // 在 pos 位置新增元素
    public void add(int pos, int data) throws PosWrongfulException {
        //1.下标为负数
        //2.下标超过了数组的长度
        //3.满
        //4.不能隔着元素放 要存储的位置前面一定是有元素的
        if(isFull()){
            System.out.println("满了");
            this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
        }
        if(pos<0||pos>this.usedSize){
            System.out.println("注意：pos位置不合法!!!");
            throw new PosWrongfulException("注意：pos位置不合法!!!");
        }
        //pos合法
        //1.开始挪动数据
        for (int i = this.usedSize-1; i >=pos ; i--) {
            this.elem[i+1]=this.elem[i];
        }
        //2.插入数据
        this.elem[pos]=data;
        //3.usedSize++
        this.usedSize++;
 
    }
 
 
    //判断是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < this.size(); i++) {
            if(this.elem[i]==toFind){
                return true;
            }
        }return false;
    }
 
 
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.size(); i++) {
            if(this.elem[i]==toFind){
                return i;
            }
        }return -1;
    }
 
    // 获取 pos 位置的元素
    public int get(int pos) {
        if(isEmpty()){
            throw new EmptyException("注意:当前顺序表为空!!!");
 
        }
        if(pos<0||pos>=this.usedSize){
            throw new PosWrongfulException("注意:当前pos位置不合法！！！");
        }
        return this.elem[pos];
    }
    public boolean isEmpty(){
 
        return size()==0;
    }
 
    // 给 pos 位置的元素更新为value
    public void set(int pos, int value) {
        //1.pos是否越界
        if(isEmpty()){
            throw new EmptyException("注意:当前顺序表为空!!!");
 
        }
        if(pos<0||pos>=this.usedSize){
            throw new PosWrongfulException("注意:当前pos位置不合法！！！");
        }
        this.elem[pos]=value;
    }
 
    // 删除第一次出现的关键字key
    public void remove(int key) {
        //空的顺序表没有key
        if(isEmpty()){
            throw new EmptyException("注意:当前顺序表为空!!!");
        }
        //1.先找到key，知道下标
        int num=this.indexOf(key);
        if(num==-1){
            System.out.println("没有这个数字");
            return;
        }//2.挪动数据
        for (int i = num; i < size()-1; i++) {
            this.elem[i]=this.elem[i+1];
        }
        //3.usedSize--
        usedSize--;
 
    }
 
    // 获取顺序表长度
    public int size() {
 
        return this.usedSize;
    }
 
    // 清空顺序表
    public void clear() {
 
        this.usedSize=0;
    }
 
    // 打印顺序表
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.printf(this.elem[i]+" ");
        }
        System.out.println();
    }
 
}

三、ArrayList简介

 上图说明以下几点：

1.ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问。（根据下标进行访问）

2.ArrayList实现了Cloneable接口，表明ArrayList是可以clone的。

3.ArrayList实现了Serializable接口，表明ArrayList是支持序列化的。

4.和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程下可以选择Vector或者CopyOnWriteArrayList。

5.ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表。

6.ArrayList 继承了 AbstractList ，并实现了 List 接口。

其中，ArrayList 类位于 java.util 包中，使用前需要引入它。

import java.util.Arrays;

ArrayList是以泛型方式实现的，使用前必须要先进行实例化：

ArrayList objectName =new ArrayList<>();

• E：表示泛型数据类型，用于设置 objectName 的数据类型，只能为引用数据类型。
• objectName： 对象名。