Java实现顺序表

目录

• 集合框架
• ArrayList

---

1.集合框架

在实现顺序表之前我想先简单介绍一下集合框架，因为先了解这一块的框架，我们才会有目的性的，有方向感的去学习每一个数据结构，自己学了多少让自己心里也有个谱。

1.1.那什么是集合呢？

Java 集合框架 （ Java Collection Framework）  ，又被称为容器 （ container）  ，是定义在 java.util 包下的一组接口 和其实现类，它的主要表现为对单元中的元素进行增删查改 *** 作（CURD）。 类和接口总览

 1.2.容器背后对应的数据结构

该阶段，我们主要学习以下容器，兄弟们，简单了解一下，后续我会跟着我学习的进度不断给大家介绍的。

1. Collection ： 是一个接口，包含了大部分容器常用的一些方法 2. List ： 是一个接口，规范了 ArrayList 和 LinkedList 中要实现的方法

• ArrayList：实现了List接口，底层为动态类型顺序表
• LinkedList ：实现了 List 接口，底层为双向链表

3. Stack ：底层是栈，栈是一种特殊的顺序表 4. Queue ：底层是队列，队列是一种特殊的顺序表 5. Deque ：是一个接口 6. Set ：集合，是一个接口，里面放置的是 K 模型

• HashSet ：底层为哈希桶，查询的时间复杂度为 O(1)
• TreeSet ：底层为红黑树，查询的时间复杂度为 O(log2^N),关于 key 有序的

7. Map ：映射，里面存储的是 K-V 模型的键值对

• HashMap ：底层为哈希桶，查询时间复杂度为 O(1)
• TreeMap ：底层为红黑树，查询的时间复杂度为 O(log2^N)，关于 key 有序

---

  2.ArrayList

 在实现之前，我先给大家讲一下我身边的同学难看的代码风格，前几天我一个同学在问我单链表的实现问题的时候，因为我们学校用的是软件是eclips，它肯定是没有idea好的，然后呢，当我看到他的代码的时候，我真的是惊了，就算我会实现，但当我看到他写的代码的时候，我真的是看不下去了，我是真的后悔没有拍下来，括号括号不对其，然后Java当中的左括号一般是写在当前代码这一行的结束，例如这样：

public  void  func ( )  {     

}

他是像C语言那样两个括号写在下边，其次，他的实现类MyArrayList和主函数写在一块，看的我非常难受，而且还加一大堆printf：请输入XXXXX，我是真的会谢，本来他问的问题，我能帮他解决的，并且很乐意解决，但是这种情况下，我不得不在他面前谦虚了一回🤨

回到正题：

  MyArrayList是需要定义成一个主类的，它的一些相关方法就写在这个类里面，然后我们需要单独定义一个测试类，因为我们在实现的过程中难免会出现一些细节方面的错误，简而言之就是Array List的实现类和测试类分别写在各自的Java文件中，这样代码就不会冗余，而且可读性会非常舒服的，例如这样：

public class MyArrayList {
    private int elem[];
    private int usedSize;
    public static final int DEFAULT_SIZE = 4;

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

    public void display() {
    }

    private boolean isFull() {
        return false;
    }
    .......
}

在这个Java 文件中写主函数，然后通过实例化MyArrayList的对象去调用它的方法，以便我们在实现的过程中遇到的错误，可以进行测试和调试，，，

public class TestDemo {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
    }
}

---

  接下来就进入我们的正题了，经过前面知识的铺垫，我们也大概了解了一下ArrayList。

顺序表：ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表。其实也就相当于一个数组，我们要实现的无非就是增删查改 *** 作。

2.1 增加 *** 作---add

增加 *** 作分两种：1.在元素某位增加，也就是在usedSize位置增加

普通的add

//普通的add，直接在usedSize位置插
    public void add(int data) {
        //1.判断数组是否满了，满了就要扩容
        if(isFull()) {
            this.elem = Arrays.copyOf(this.elem,this.elem.length * 3 / 2);
        }

        this.elem[this.usedSize] = data;

        this.usedSize++;
    }

这里要注意的只有一点，增加的时候，判断一下数组是否满了，满了就要扩容。

任意位置增加的add

//在指定位置插入
    public void add(int pos, int data) {
        //1.判断插入位置是否合法
        if(checkPosInAdd(pos)) {
            throw new MyArrayListPosLegalException("在指定位置插入数据，位置不合法！");
        }
        //2.判断数组是否满了，满了要扩容
        if(isFull()) {
            this.elem = Arrays.copyOf(this.elem,this.elem.length * 3 / 2);
        }
        //3.挪数据
        for (int i = this.usedSize - 1; i >= pos; i++) {
            this.elem[i + 1] = this.elem[i];
        }

        //4.插数据
        this.elem[pos] = data;

        this.usedSize++;
    }

这里要注意三个点：

第一，要判断一下pos是否合法，我们学过异常，pos不合法，可以抛一个自定义异常

第二，要判断数组是否满了，满了就要扩容

第三，在指定位置增加，除了在usedSize位置增加只需考虑扩容，其他位置增加还需要挪数据 

 然后每增加一个元素，我的usedSize就++一下，记录有效数据的个数。

---

 2.2删除 *** 作---remove

    public void remove(int toRemove) {
        //1.判空
        if(isEmpty()) {
            throw new MyArrayListIsEmpty("顺序表为空,不能删除!");
        }
        //2.找到这个值的下标
        int index = indexOf(toRemove);

        //3.判断下标是否合法
        if(index == -1) {
            throw new MyArrayListNoHaveElement("顺序表中没有这个元素！");
        }

        //4.删除--覆盖
        for (int i = index; i < this.usedSize - 1; i++) {
            this.elem[i] = this.elem[i + 1];
        }

        this.usedSize--;
    }

删除 *** 作需要三个步骤：

1.删除之前，需要判断数组是否为空，，

2.需要在数组中找到待删除元素的下标，如果下标合法，表示数组中有这个元素，可以进行删除，     反之没有，直接抛异常，，

3.如果下标合法，就进行覆盖 *** 作，覆盖 *** 作就类似刚刚的任意位置增加函数一样，只不过是反过     来的，删除最后一个元素，就不影响

---

  2.3查找 *** 作---contains/indexOf

contians：

    public boolean contains(int toFind) {
        //1.判断顺序表是否为空
        if(isEmpty()) {
            throw new MyArrayListIsEmpty("顺序表为空！");
        }
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

indexOf：

    public int indexOf(int toFind) {
        //1.判空
        if(isEmpty()) {
            throw new MyArrayListIsEmpty("顺序表为空！");
        }
        //2.查找有无这个元素
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

---

 2.4更新 *** 作---set

    public void set(int pos, int value) {
        //1.判断设置位置是否合法
        if(checkPosInGet(pos)) {
            throw new MyArrayListPosLegalException("指定位置更新顺序表的值时，位置不合法！");
        }
        this.elem[pos] = value;
    }

以上的几个方法都挺简单的，就不细说了，另外就剩几个简单的 *** 作了---打印，获取pos位置的元素，获取顺序表的大小，以及清空顺序表的 *** 作，，，

打印：

public void display() {
    for (int i = 0; i < this.usedSize; i++) {
        System.out.print(this.elem[i]+" ");
    }
    System.out.println();
}

  获取pos位置的元素：（判断位置的合法性，判空都跟前面的一样）

    public int get(int pos) {
        //1.判断位置是否合法
        if(checkPosInGet(pos)) {
            throw new MyArrayListPosLegalException("获取顺序表元素时，位置不合法！");
        }
        //2.判断顺序表是否为空
        if(isEmpty()) {
            throw new MyArrayListIsEmpty("顺序表为空！");
        }
        return this.elem[pos];
    }

获取顺序表的大小：

    public int size() {
        return this.usedSize;
    }

清空顺序表：

public void clear() {
        /*如果数组中存放的是引用类型，需要一个一个置为null
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = null;
        }
        this.usedSize = 0;*/
        this.usedSize = 0;
    }

清空顺序表要注意：如果顺序表中存放的是引用类型，则需要将数组中的元素一个一个置为null，否则会产生大量的内存碎片。这时候又有人问了，我能不能直接把数组置为空---》 elem = null？

    //当我们只是将一个一个元素置空时，我们的顺序表还是可以放元素的
    public void clear() {
        /*如果数组中存放的是引用类型，需要一个一个置为null
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = null;
        }
        this.usedSize = 0;
        */
        
        //this.elem = null;
        this.usedSize = 0;
    }

运行结果为：

 如果你把数组置为空，你想再添加元素就不可能了，你连数组的内存都不知道了，就相当于你这个顺序表只玩了一次就不能玩了，，，

你可以看运行结果：

---

  2.5.ArrayList的构造方法

方法	解释
ArrayList()	无参构造
ArrayList(Collection c)	利用其他Collection构建ArrayList
ArrayList(int initialCapacity)	指定顺序表初始容量

public class Test {
    public static void main(String[] args) {
        // 构造一个空的列表
        List list1 = new ArrayList<>();

        // 构造一个具有10个容量的列表
        List list2 = new ArrayList<>(10);
        list2.add(1);
        list2.add(2);
        list2.add(3);

        // list3构造好之后，与list中的元素一致
        ArrayList list3 = new ArrayList<>(list2);
    }
}

注意：ArrayList后面一定要加上尖括号，否则什么类型都能放，就不好控制了，，，

---

2.6 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（左闭右开）

演示addAll，remove（Object o），和一个subList，剩下一两个不会的大家可以查一下帮助手册，挺简单的，，，

addAll:

public class Test {
    public static void main(String[] args) {
        ArrayList list = new ArrayList<>();
        list.add(0,1);
        list.add(1,2);
        list.add(2,3);
        System.out.println(list);
        //addAll里面的参数类型必须是Integer或者它的子类
        ArrayList list1 = new ArrayList<>();
        list1.addAll(list);
        list1.add(4);
        System.out.println(list1);
    }
}

提示：直接输出ArrayList的对象，就能打印，说明ArrayList或者它的父类实现了toString方法。

remove(Object o):

 我们发现我想删除99这个元素，而编译器默认是删除99下标的元素，我们观察remove的参数是一个对象，所以我们这样做就能解决问题了，，，

public class Test {
    public static void main(String[] args) {
        ArrayList list = new ArrayList<>();
        list.add(0,1);
        list.add(1,22);
        list.add(2,99);
        list.remove(new Integer(99));
        System.out.println(list);
    }
}

---

 2.7ArrayList的三种遍历方式

public class Test {
    public static void main(String[] args) {
        ArrayList list = new ArrayList<>();
        list.add(0,1);
        list.add(1,22);
        list.add(2,99);
        list.add(45);
        //for循环遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
        System.out.println("==========");
        //foreach遍历
        for (Integer x : list) {
            System.out.print(x + " ");
        }
        System.out.println();
        System.out.println("=====使用迭代器=====");
        //使用迭代器打印
        Iterator it = list.iterator();
        while(it.hasNext()) {
            System.out.print(it.next() + " ");
        }
    }
}

这里说一下迭代器，实现了Iterator接口的都可以使用迭代器进行打印，它实现打印的具体过程：

 有关ArrayList的介绍就到这里了，希望对大家有帮助！！！