数据结构入门到入土——ArrayList与顺序表

目录

一，线性表

二，顺序表

1.接口实现

三，ArrayList简介

四，ArrayList使用

1.ArrayList的构造

2.ArrayList常见操作

3.ArrayList的遍历

4.ArrayList的扩容机制

五，ArrayLisit的具体使用

杨辉三角

一，线性表

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

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

二，顺序表

1.接口实现

接口部分：

public interface IList {
    // 新增元素,默认在数组最后新增
    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 isFull();
    //判断顺序表是否为空
    public boolean isEmpty();
}

接口实现：

import java.util.Arrays;

public class MyArrayList implements IList{
    public int[] elem;
    public int usedSize;
    public static final int DEFINE_SIZE = 10;

    public MyArrayList() {
        this.elem = new int[DEFINE_SIZE];
    }

    public MyArrayList(int capacity) {
        this.usedSize = capacity;
    }

    @Override
    //新增元素,默认在数组最后新增
    //1.检查数组是否已满
    //2.满了扩容，未满新增
    //usedSize++
    public void add(int data) {
        if (isFull()) {
            elem = Arrays.copyOf(elem,2 * elem.length);
        }
        this.elem[this.usedSize] = data;
        this.usedSize++;
    }

    public boolean isFull() {
        return this.usedSize ==elem.length;
    }
    @Override
    //在 pos 位置新增元素
    //1.检查数组是否已满
    //2.满了扩容
    //3.未满：在指定位置新增，原位置有元素就向后挪
    //4.usedSize++
    public void add(int pos, int data) {
        if (isFull()) {
            elem = Arrays.copyOf(elem,2 * elem.length);
        }
        //新增
        int i = this.usedSize;
        while (i > pos) {
            elem[i] = elem[i-1];
            i--;
        }
        this.elem[pos] = data;
        usedSize++;
    }

    @Override
    // 判定是否包含某个元素
    //1.顺序表是否为空
    //2.查找元素
    public boolean contains(int toFind) {
        if (isEmpty()) {
            return false;
        }
        //查找元素
        if (findVal(toFind) != 0) {
            return true;
        }
        return false;
    }

    public int findVal(int val) {
        for (int i = 0; i < elem.length; i++) {
            if (elem[i] == val) {
                return i;
            }
        }
        return 0;
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }

    @Override
    // 查找某个元素对应的位置
    // 1.判断是否为空
    // 2.为空抛空List异常
    // 3.查找元素
    // 4.获取下标
    public int indexOf(int toFind) throws EmptyListException{
        if (isEmpty()) {
            throw new EmptyListException("空List异常");
        }
        //查找
        if (findVal(toFind) == 0) {
            //查询不到异常
            throw new NotFindException("NotFindException");
        }
        return findVal(toFind);
    }

    @Override
    // 获取 pos 位置的元素
    // 1.判断是否为空
    // 2.判断pos位置是否合法
    // 3.获取
    public int get(int pos) {
        if (isEmpty()) {
            throw new EmptyListException("空List异常");
        }
        if (checkPos(pos)) {
            //pos位置不合法
            throw new PosException("pos位置不合法");
        }
        return this.elem[pos];
    }

    private boolean checkPos(int pos) {
        if (pos < 0 || pos >= this.usedSize) {
            return true;
        }
        return false;
    }
    @Override
    // 给 pos 位置的元素设为 value
    // 1.判断是否为空
    // 2.判断pos位置是否合法
    // 3.设置
    public void set(int pos, int value) {
        if (isEmpty()) {
            throw new EmptyListException("空List异常");
        }
        if (checkPos(pos)) {
            //pos位置不合法
            throw new PosException("pos位置不合法");
        }
        this.elem[pos] = value;
    }

    @Override
    // 删除第一次出现的关键字key
    // 是否为空？
    // 查找关键字
    public void remove(int toRemove) {
        if (isEmpty()) {
            throw new EmptyListException("空List异常");
        }
        for (int i = indexOf(toRemove);i < this.usedSize - 1;i++) {
            elem[i] = elem[i+1];
        }
        usedSize--;
    }

    @Override
    // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }

    @Override
    // 清空顺序表
    public void clear() {
        this.usedSize = 0;
    }

    @Override
    public void display() {
        System.out.print("[");
        if (this.usedSize == 0) {
            System.out.println("]");
        }
        for (int i = 0; i < this.usedSize; i++) {
            if (i == this.usedSize - 1) {
                System.out.println(this.elem[i] + "]");
            } else {
                System.out.print(this.elem[i] + ",");
            }
        }
    }
}

三，ArrayList简介

class Solution {
    //求杨辉三角方法
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();//二维数组
        List<Integer> list = new ArrayList<>();
        list.add(1);
        ret.add(list);
        for (int i = 1; i < numRows; i++) {
            List<Integer> curRow = new ArrayList<>();//当前行
            List<Integer> prevRow = ret.get(i-1);//上一行
            curRow.add(1);//当前行首个元素为1
            for (int j = 1; j < i; j++) {
                int val = prevRow.get(j-1) + prevRow.get(j);
                curRow.add(val);
            }
            curRow.add(1);//当前行最后一个元素为1
            ret.add(curRow);
        }
        return ret;
    }
}
public class Test {
    //方法使用
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> mylist = new ArrayList<>();
        mylist = solution.generate(3);
        for (int i = 0; i < 3; i++) {
            List<Integer> arr = mylist.get(i);
            System.out.println(arr);
        }
    }
}