三分钟“手撕”顺序表与ArrayList

码农世界 2024-05-28 后端 75 次浏览 0个评论

前言：

实现顺序表的代码放开头，供大家更好的查阅，每个方法都有代码的实现。

其次我会讲解Java自带的ArrayList的实例，扩容机制ArrayList使用方法，遍历以及它的优缺点。

一、自己实现的顺序表

二、Java的ArrayList实例的扩容机制

三、ArrayList的使用

四、ArrayList的遍历

六、ArrayList的优缺点

一、自己实现的顺序表

package myarraylist;
//IList.java   
public interface IList {
    // 新增元素,默认在数组最后新增
    void add(int data);
    // 在 pos 位置新增元素
    void add(int pos, int data);
    // 判定是否包含某个元素
    boolean contains(int toFind);
    // 查找某个元素对应的位置
    int indexOf(int toFind);
    // 获取 pos 位置的元素
    int get(int pos);
    // 给 pos 位置的元素设为 value
    void set(int pos, int value);
    //删除第一次出现的关键字toRemove
    void remove(int toRemove);
    //删除全部出现的关键字toRemove
    void removeAll(int toRemove);
    // 获取顺序表长度
    int size();
    // 清空顺序表
    void clear();
    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    void display();
    //判断数组满了没，能不能继续插入数据
    Boolean isFull();
}

package myarraylist;
//posNotLegalException.java
public class posNotLegalException extends RuntimeException{
    public posNotLegalException(){
    }
    public posNotLegalException(String msg){
        super(msg);
    }
}

package myarraylist;
//MyArrayList.java
import java.util.Arrays;
public class MyArrayList implements IList {
    public int[] elem;
    int usesize;
    public MyArrayList() {
        this.elem = new int[10];
    }
    //尾插
    @Override
    public void add(int data) {
        if (isFull()) {
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        this.elem[usesize] = data;
        this.usesize++;
    }
    @Override
    public void add(int pos, int data) {
        try {
            posException(pos);
        } catch (posNotLegalException e) {
            e.printStackTrace();
        }
        if (isFull()) {
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        for (int i = usesize - 1; i >= pos; i--) {
            elem[i + 1] = elem[i];
        }
        elem[pos] = data;
        usesize++;
    }
    private void posException(int pos) throws posNotLegalException {
        if (pos < 0 || pos > usesize) {
            throw new posNotLegalException("pos位置不合法");
        }
    }
    @Override
    public boolean contains(int toFind) {
        for (int i = 0; i < usesize; i++) {
            if (elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }
    @Override
    public int indexOf(int toFind) {
        for (int i = 0; i < usesize; i++) {
            if (elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }
    @Override
    public int get(int pos) {
        try {
            posExceptionOfGetAndSet(pos);
        } catch (posNotLegalException e) {
            e.printStackTrace();
        }
        return elem[pos];
    }
    @Override
    public void set(int pos, int value) {
        try {
            posExceptionOfGetAndSet(pos);
        } catch (posNotLegalException e) {
            e.printStackTrace();
        }
        elem[pos] = value;
    }
    private void posExceptionOfGetAndSet(int pos) throws posNotLegalException{
        if (pos < 0 || pos >= usesize) {
            throw new posNotLegalException("get and set的pos位置不合法");
        }
    }
    @Override
    public void remove(int toRemove) {
        int pos = indexOf(toRemove);
        if (pos == -1) {
            System.out.println("没有你要找的数据");
            return;
        }
        for (int i = pos; i < usesize - 1; i++) {
            elem[i] = elem[i + 1];
        }
        usesize--;
    }
    @Override
    public void removeAll(int toRemove) {
        for (int i = 0; i < usedSize; i++) {
            if (elme[i] == toRemove) {
                for (int j = i; j < usedSize -1; j++) {
                    elme[j] = elme[j + 1];
                }
                usedSize--;
            }
        }
    }
    @Override
    public int size() {
        return usesize;
    }
    @Override
    public void clear() {
        usesize = 0;
    }
    @Override
    public void display() {
        for (int i = 0; i < usesize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }
    @Override
    public Boolean isFull() {
        return usesize == elem.length;
    }
}

二、Java的ArrayList实例的扩容机制

ArrayList是一个类，它有三个构造函数

既然分配的是0空间，为什么可以add元素呢？

当调用不带参数的构造方法进行add方法的时候，第一次add会分配大小为10内存，若内存，就会按照1.5倍扩容。

【总结】

1. 检测是否真正需要扩容，如果是调用grow准备扩容

2. 预估需要扩容的大小初步预估按照1.5倍大小扩容如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容真正扩容之前检测是否能扩容成功，防止太大导致扩容失败

3. 使用copyOf进行扩容

    public static void main(String[] args) {
        //构建一个空的列表
        List list1=new ArrayList<>();
        //十个容量的列表
        List list2=new ArrayList<>(10);
        list2.add(1);
        list2.add(2);
        list2.add(3);
        //list3构建好之后，与list中的元素一致
        ArrayList list3=new ArrayList<>(list1);
        //不要省略类型，因为里面什么都可以放，很混乱
        List list4=new ArrayList();
        list4.add("111");
        list4.add(123);
    }

ArrayList和List有什么区别 ?

List是一个接口类型，ArrayList是一个类，这是他们两本质区别。

其次接口它能访问到的方法比较少，而ArrayList是当前对象的方法，所以ArrayList能访问到的方法比List多。

三、ArrayList的使用

Java自带的ArrayList常见的方法：

方法	功能
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
void clear(）	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)	截取部分 list（左闭右开）

上面的E指的是泛型的种类（具体请看我之前的博客），

public static void main(String[] args) {
        ArrayList list=new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(0,0);
        list.remove(0);
        list.remove(1);
        System.out.println(list);
        System.out.println(list.contains(3));
        list.get(2);
        list.set(1,2);
        System.out.println(list);
        ArrayList list1=new ArrayList<>();
        list1.addAll(list);
        System.out.println(list1);
        //左闭右开
        System.out.println(list.subList(1, 3));
    }

其实，我们自己实现的顺序表方法的功能跟这个也大差不差，我们自己实现一遍顺序表基本上就游刃有余了。这个表格也不要刻意去背，我们需要的时候顺着表格找就行了。

四、ArrayList的遍历

public static void main(String[] args) {
         List list=new ArrayList<>();
         list.add(1);
         list.add(2);
         list.add(3);
         list.add(4);
         //for循环遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i)+" ");
        }
        System.out.println();
        //foreach遍历
        for (Integer integer:list) {
            System.out.println(integer+" ");
        }
        System.out.println();
        //迭代器
        Iterator it=list.listIterator();
        while (it.hasNext()){
            System.out.println(it.next()+" ");
        }
        System.out.println();
    }

用的比较多的是for和foreach（第一种和第二种），第三种简单了解就好了。

但是这里有个问题，为什么list要用get（i），不能直接list[i]呢？

答：list里面存的是Integer，而这东西是类，它不是简单的数据类型，Integer存的是地址，而不是值，相当于把值装箱（装箱也在我泛型博客右具体介绍）

六、ArrayList的优缺点

优点：

给了下标，找值特别快，复杂度是O（1）

缺点：

1.如果在任意位置插元素，删除元素。你需要用for循环，复杂度是O（N）

2.增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3.增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

问题：那有没有一种数据结构，可以解决顺序表的缺点？

答：有，那就是链表。（下一篇博客）

转载请注明来自码农世界，本文标题：《三分钟“手撕”顺序表与ArrayList》