JavaDS —— 顺序表ArrayList

07-17 1077阅读

顺序表

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

模拟实现

下面是我们要自己模拟实现的方法：

首先我们要创建一个顺序表，顺序表包含一个数组，一个由于计数的计数器，还有一个默认的初始容量，我这里定义初始容量为5，比较好判断扩容是否成功。这里以整型数组为例：

    private int[] array;
    private int usedSize;//目前数据总数
    private static final int DEFAULT_CAPACITY = 5;//默认容量

默认构造方法

这里我们直接在构造方法里给数组进行初始化：

    public MyArrayList() {
        array = new int[DEFAULT_CAPACITY];
    }

尾插

尾插是指直接在所有数据的后面插入新数据，这里我们要注意数组容量是否已满，所以我们先写一个isFull方法判断数组是否容量已满：

    private boolean isFull() {
        if(usedSize == array.length) {
            return true;
        }
        return false;
    }

这个方法设置成private是因为这个方法只是给本类的方法提供的，不需要对外公开。

如果数组已满，那么我们就需要扩容，这里我扩容2倍：

    private void grow() {
        array = Arrays.copyOf(array,array.length * 2);
    }

现在来写尾插代码：

    public void add(int data) {
        //判满
        if(isFull()) {
            grow();
        }
        //插入数据
        array[usedSize++] = data;
    }

pos位置插入数据

首先我们要先检查pos位置是否合法，如果不合法的话就不用进行插入操作，直接抛出异常，我们先写异常代码：

public class PosException extends RuntimeException{
    public PosException(String message) {
        super(message);
    }
}

检查pos位置是否合法：

    private void checkPosInAdd(int pos) throws PosException {
        if(pos  usedSize) {
            throw new PosException("pos位置不合法");
        }
    }

现在写插入代码，首先判断pos是否合法，然后判断是否要扩容，最后我们进行插入操作即可，在插入代码中，我们使用try-catch来处理异常。

    public void add(int pos,int data) {
        try{
            checkPosInAdd(pos);//检查位置是否合法
            if(isFull()) {    //判满
                grow();
            }
            //移动数据
            for (int i = usedSize; i >= pos ; i--) {
                array[i+1] = array[i];
            }
            //插入数据
            array[pos] = data;
            usedSize++;
        }catch (PosException e) {
            System.out.println("pos位置不合法！");
            e.printStackTrace();
        }
    }

contains

是否包含某个元素，使用布尔值进行返回，这里直接遍历数组查找即可。

    public boolean contains(int toFind) {
        for (int i = 0; i  
indexOf 
查找某个元素的下标，找到则返回该元素的下标，没有找到则返回 -1 
    public int indexOf(int toFind) {
        for (int i = 0; i  
get 
找到pos位置的元素，这里要注意先判断pos是否合法,但是这里的检查pos和上面我们写过的checkPosInAdd是不一样的，这里的pos必须是有元素的下标范围，也就是不包含usedSize这个下标，因为这个是没有有效数据的，是待插入的空位，所以我们要再写一个检查pos方法： 
    private void checkPosInFind(int pos) throws PosException {
        if(pos = usedSize) {
            throw new PosException("pos位置不合法");
        }
    }
 
    public int get(int pos) {
        try{
            checkPosInFind(pos);
            return array[pos];
        }catch (PosException e) {
            System.out.println("pos位置不合法！");
            e.printStackTrace();
        }
        return -1;
    }
 
set 
更新pos位置的数据，还是要判断pos位置是否合法，这里使用发判断方法应该为checkPosInFind 
    public void set(int pos, int data) {
        try{
            checkPosInFind(pos);
            array[pos] = data;
        }catch (PosException e) {
            System.out.println("pos位置不合法！");
            e.printStackTrace();
        }
    }
 
remove 
删除第一次出现的关键字key 
    public void remove(int key) {
        for (int i = 0; i  
size 
获取顺序表的长度,这里直接返回usedSize即可 
    public int size() {
        return usedSize;
    }
 
display 
打印顺序表，该方法是便于测试，真正的顺序表并没有这个方法 
    public void display() {
        for (int i = 0; i  
clear 
清空顺序表，直接将usedSize赋值为0即可，下次使用的时候，会直接覆盖之前的数据的。 
    public void clear() {
        usedSize = 0;
    }
 
完整代码 
import java.util.Arrays;
public class MyArrayList {
    private int[] array;
    private int usedSize;//目前数据总数
    private static final int DEFAULT_CAPACITY = 5;//默认容量
    public MyArrayList() {
        array = new int[DEFAULT_CAPACITY];
    }
    /*
    判满，满则返回true,否则返回false
     */
    private boolean isFull() {
        if(usedSize == array.length) {
            return true;
        }
        return false;
    }
    //扩容 2倍扩容
    private void grow() {
        array = Arrays.copyOf(array,array.length * 2);
    }
    //尾插
    public void add(int data) {
        //判满
        if(isFull()) {
            grow();
        }
        //插入数据
        array[usedSize++] = data;
    }
    //判断pos是否合法
    /*
      不合法则抛出异常
      增加方法
    */
    private void checkPosInAdd(int pos) throws PosException {
        if(pos  usedSize) {
            throw new PosException("pos位置不合法");
        }
    }
    //指定pos位置插入数据
    public void add(int pos,int data) {
        try{
            checkPosInAdd(pos);//检查位置是否合法
            if(isFull()) {    //判满
                grow();
            }
            //移动数据
            for (int i = usedSize; i >= pos ; i--) {
                array[i+1] = array[i];
            }
            //插入数据
            array[pos] = data;
            usedSize++;
        }catch (PosException e) {
            System.out.println("pos位置不合法！");
            e.printStackTrace();
        }
    }
    //是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i = usedSize) {
            throw new PosException("pos位置不合法");
        }
    }
    //获取pos位置的元素
    public int get(int pos) {
        try{
            checkPosInFind(pos);
            return array[pos];
        }catch (PosException e) {
            System.out.println("pos位置不合法！");
            e.printStackTrace();
        }
        return -1;
    }
    //更新pos位置的数据
    public void set(int pos, int data) {
        try{
            checkPosInFind(pos);
            array[pos] = data;
        }catch (PosException e) {
            System.out.println("pos位置不合法！");
            e.printStackTrace();
        }
    }
    //删除第一次出现的关键字key
    public void remove(int key) {
        for (int i = 0; i  
ArrayList 的使用 
Java已经封装好顺序表供我们使用，就是ArrayList，现在我们来列举其中的常用的方法。