Java语言----动态顺序表(ArrayList)

简介: Java语言----动态顺序表(ArrayList)

😽个人主页: tq02的博客_CSDN博客-C语言,Java,Java数据结构领域博主

🌈梦的目标:努力学习,向Java进发,拼搏一切,让自己的未来不会有遗憾。

🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝+关注✨

 本章讲解内容:顺序表的讲解


48b44c8bb51a4c12b587a22f8f6c26d1.jpg


使用编译器:IDEA

一.顺序表


879126b6af89446496a80049aaad8b37.png


顺序表(ArrayList):用一段物理地址连续的存储单元依次存储数据元素的线性结构,通常采用数组存储。在数组上完成数据的增删查改


二.顺序表的手动实现

   2.1顺序表的创建


import java.util.Arrays;
public class MyArraysList {
    private int[] elem;
    private int usedSize; // 默认值是0
    private static final int DEFAULT_SIZE = 4; // 定义为常量,更加安全
    // 初始化顺序表
    public MyArraysList() {
        this.elem = new int[DEFAULT_SIZE];
    }
}


 这边是创建顺序表的类,不仅要创建出来,我们还需要学会使用,例如增、删、查、改

   2.2.基本功能的实现

2.2.1扩容顺序表

// 对顺序表进行扩容
    public void expand() {
        this.elem = Arrays.copyOf(this.elem, this.usedSize * 2);
        System.out.println("已经成功扩容至原来的两倍"); // 给用户提醒
    }


注:     在进行增加元素的操作时,当数组满了,则需要扩容,才能容纳下一个元素

 

 2.2.2 判断顺序表是否为满

    /**
     * 判断当前顺序表是不是满了
     * @return true->满了,false->还没满
     */
    public boolean isFull() {
        if (this.usedSize == this.elem.length) return true;
        else return false;
    }


注:扩容前得判断是否数组满了,只有满了,才需要扩容

 

2.2.3 判断顺序表是否为空

     /**
     * 判断当前顺序表是否为空
     * @return true->空的,false->还没空
     */
    public boolean isempty() {
        if (this.usedSize == 0) {
            return true;
        }
        else return false;
    }


注:如果需要删除顺序表的元素,得判断顺序表是否为空,毕竟空的顺序表无法删除元素。

2.2.4打印顺序表

// 打印顺序表
    public void display() {
        for (int i = 0; i < this.elem.length; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
}


注:顺序表存放了数据,得显示出来,展示你存放的数据


2.2.5清空顺序表

 // 清空顺序表
    public void clear() {
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = 0;
        }
        this.usedSize = 0; // 注意有效数组长度也要清零
    }


注:当代码结束之后,需要释放顺序表内存。


2.3四大功能的实现

2.3.1增加元素

头插法:


 // 新增元素,在数组最前面新增
    public void addHead(int data) {
        if (isFull()) {
            System.out.println("数组满了,需要扩容");
            expand();
        }
        else {
            // 从usedSize下标开始,不会数组越界(此时的elem.length > usedSize)
            for (int i = this.usedSize; i > 0; --i) {
                this.elem[i] = this.elem[i - 1]; // 从后往前挪动数据,为的是给顺序表的表头腾出来
            }
            this.elem[0] = data; // 在顺序表开头插入
            this.usedSize++;    // 数组有效长度加一
        }


注:每次增加的元素,都放在顺序表的第一位。

尾插法:

//在数组最后新增
    public void addTail(int data) {
        if (isFull()) {
            System.out.println("数组满了需要扩容");
            expand();
        }
        else this.elem[this.usedSize++] = data;
    }


注:每次插入元素,直接放在顺序表的最后一位。

指定下标值插入:

 // 在 pos 位置新增元素
    public void addPos(int pos, int data) {
        if (pos < 0 || pos > usedSize) {
            System.out.println("pos位置不合法"); return;
        }
        if (isFull()) {
            System.out.println("数组满了需要扩容");
            expand();
        }
        else {
            // 如果插入位置在顺序表的中间,要注意挪动元素,从后向前挪动,这样不会造成元素值的覆盖
            for (int i = this.usedSize - 1; i >= pos; --i) {
                this.elem[i + 1] = this.elem[i];
            }
            this.elem[pos] = data; // 挪动完毕,可以赋值插入
            this.usedSize++;      // 当前元素数加一
        }
    }


若在对应下标插入元素,则下标值后面的所有元素整体向后移一位。

注意:需要判断数组是否满了、插入位置在元素下标范围内。


2.3.2删除元素

头删:

 // 删除表头元素
    public void removeHead() {
        if (isempty()) {
            System.out.println("顺序表为空,删除不合法");
            return;
        }
        // 从第一个元素开始,用后面元素的值覆盖掉前面的值,遍历整个数组就相当于把第一个元素用覆盖的方式抹去了
        for (int i = 1; i < this.usedSize; i++) {
            this.elem[i - 1] = this.elem[i];
        }
        this.elem[this.usedSize - 1] = 0; // 减少了一个元素,所以之前最后一个元素置0
        this.usedSize--; // 不要忘记改变有效数组的长度
    }


注:从第二个元素开始,每一个元素覆盖前面一个,再将最后一个元素清零。

尾删:

    // 删除表尾元素
    public void removeTail() {
        if (isempty()) {
            System.out.println("顺序表为空,删除不合法");
            return;
        }
        this.elem[this.usedSize - 1] = 0; // 直接将最后一个元素置0就完成了尾删
        this.usedSize--; // 不要忘记改变有效数组的长度
    }


注:直接删除末尾元素,将最后一个元素置0

指定下标元素的删除:

 // 指定下标元素的删除
    public void removePos(int pos) {
        if (isempty()) {
            System.out.println("顺序表为空,删除不合法");
            return;
        }
        if (pos < 0 || pos >= this.usedSize) {
            System.out.println("pos下标不合法");
        }
        else {
            for (int i = pos; i < this.usedSize - 1; ++i) {
                this.elem[i] = this.elem[i + 1]; // 从要删除的下标开始,用后边元素的值覆盖掉前面的值,就完成了删除
            }
            this.elem[this.usedSize - 1] = 0; // 最后一个元素置0
            this.usedSize--;// 删除后更改顺序表的有效长度
        }
    }


注:与头删法相似。

删除首次出现的元素:

 //删除第一次出现的关键字key
    public void removeKey(int toRemove) {
        if (isempty()) {
            System.out.println("顺序表为空,删除不合法");
            return;
        }
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toRemove) {
                // 注意是this.usedSize - 1,将此时 i 之后的元素统一往前搬移一个位置
                for (int j = i; j < this.usedSize - 1; ++j) {
                    this.elem[j] = this.elem[j + 1];
                }
                this.elem[this.usedSize - 1] = 0; // 要完整的删除,将挪动的最后一个元素的原本位置 置空
                this.usedSize--; // 删除后不要忘记更改顺序表的有效长度
                return; // 只删除第一次出现的
            }
        }
    }


注:找到对应下标值,然后再进行覆盖,在删除的后面全体元素向前挪一位


2.3.3查找元素

获取指定位置元素:

 // 获取 pos 位置的元素
    public int getPos(int pos) {
        if (pos < 0 || pos >= this.usedSize) { // 注意这里当pos==this.usedSize也是不合法的,因为此时的pos下标所要获取的是顺序表中第usedSize+1个元素
            System.out.println("pos的位置不合法");
            return -1;
        }
        else {
            return this.elem[pos];
        }
    }


注:考虑要获取的位置是否合法、返回指定位置的元素

获取指定元素所在的位置:

 // 查找某个元素所对应顺序表中的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return i;
            }
        }
        System.out.println("在数组中没有找到该元素");
        return -1;
    }


注:返回下标值


2.3.4更改数据

在对应下标值,进行修改:

// 给 pos 位置的元素设为 value
    public void setPos(int pos, int value) {
        if (pos < 0 || pos > this.usedSize) {
            System.out.println("pos位置不合法");
            return;
        }
        if (pos == this.usedSize) { // 对这种情况要单独处理,此时相等于增加元素
            this.elem[pos] = value;
            this.usedSize++;
        }
        else {
            this.elem[pos] = value;
        }
    }


几乎是查找的步骤上,对其修改。


总代码

📝MyArraysList.java

  MyArraysList.java用于顺序表的实现

import java.util.Arrays;
public class MyArraysList {
    private int[] elem;
    private int usedSize; // 默认值是0
    private static final int DEFAULT_SIZE = 4; // 定义为常量,更加安全
    // 初始化顺序表
    public MyArraysList() {
        this.elem = new int[4];
    }
    // 对顺序表进行扩容
    public void expand() {
        this.elem = Arrays.copyOf(this.elem, this.usedSize * 2);
        System.out.println("已经成功扩容至原来的两倍"); // 给用户提醒
    }
    /**
     * 判断当前顺序表是否为空
     * @return true->空的,false->还没空
     */
    public boolean isempty() {
        if (this.usedSize == 0) {
            return true;
        }
        else return false;
    }
    /**
     * 判断当前顺序表是不是满了
     * @return true->满了,false->还没满
     */
    public boolean isFull() {
        if (this.usedSize == this.elem.length) return true;
        else return false;
    }
    // 打印顺序表
    public void display() {
        for (int i = 0; i < this.elem.length; i++) {
            System.out.print(this.elem[i] + " ");
        }
        // System.out.println(Arrays.toString(this.elem));或者用Arrays.toString打印也行
        System.out.println();
    }
    // 新增元素,默认在数组最后新增
    public void addTail(int data) {
        if (isFull()) {
            System.out.println("数组满了需要扩容");
            expand();
        }
        else this.elem[this.usedSize++] = data;
    }
    // 新增元素,在数组最前面新增
    public void addHead(int data) {
        if (isFull()) {
            System.out.println("数组满了,需要扩容");
            expand();
        }
        else {
            // 从usedSize下标开始,不会数组越界(此时的elem.length > usedSize)
            for (int i = this.usedSize; i > 0; --i) {
                this.elem[i] = this.elem[i - 1]; // 从后往前挪动数据,为的是给顺序表的表头腾出来
            }
            this.elem[0] = data; // 在顺序表开头插入
            this.usedSize++;    // 数组有效长度加一
        }
    }
    // 1、判断pos位置是否合法(在顺序表中,数据是连续的,中间不能有空缺)
    // 2、判断顺序表是否满了,如果满了,需要扩容
    // 3、插入数据(可能需要挪作元素)
    // 在 pos 位置新增元素
    public void addPos(int pos, int data) {
        if (pos < 0 || pos > usedSize) {
            System.out.println("pos位置不合法"); return;
        }
        if (isFull()) {
            System.out.println("数组满了需要扩容");
            expand();
        }
        else {
            // 如果插入位置在顺序表的中间,要注意挪动元素,从后向前挪动,这样不会造成元素值的覆盖
            for (int i = this.usedSize - 1; i >= pos; --i) {
                this.elem[i + 1] = this.elem[i];
            }
            this.elem[pos] = data; // 挪动完毕,可以赋值插入
            this.usedSize++;      // 当前元素数加一
        }
    }
    // 删除表头元素
    public void removeHead() {
        if (isempty()) {
            System.out.println("顺序表为空,删除不合法");
            return;
        }
        // 从第一个元素开始,用后面元素的值覆盖掉前面的值,遍历整个数组就相当于把第一个元素用覆盖的方式抹去了
        for (int i = 1; i < this.usedSize; i++) {
            this.elem[i - 1] = this.elem[i];
        }
        this.elem[this.usedSize - 1] = 0; // 现在的最后一个元素是原来的倒数第二个元素, 所以原来的最后一个有效元素要置0
        this.usedSize--; // 不要忘记改变有效数组的长度
    }
    // 删除表尾元素
    public void removeTail() {
        if (isempty()) {
            System.out.println("顺序表为空,删除不合法");
            return;
        }
        this.elem[this.usedSize - 1] = 0; // 直接将最后一个元素置0就完成了尾删
        this.usedSize--; // 不要忘记改变有效数组的长度
    }
    // 指定下标元素的删除
    public void removePos(int pos) {
        if (isempty()) {
            System.out.println("顺序表为空,删除不合法");
            return;
        }
        if (pos < 0 || pos >= this.usedSize) {
            System.out.println("pos下标不合法");
        }
        else {
            for (int i = pos; i < this.usedSize - 1; ++i) {
                this.elem[i] = this.elem[i + 1]; // 从要删除的下标开始,用后边元素的值覆盖掉前面的值,就完成了删除
            }
            this.elem[this.usedSize - 1] = 0; // 要完整的删除,将挪动的最后一个元素的原本位置 置空
            this.usedSize--;// 删除后不要忘记更改顺序表的有效长度
        }
    }
    //删除第一次出现的关键字key
    public void removeKey(int toRemove) {
        if (isempty()) {
            System.out.println("顺序表为空,删除不合法");
            return;
        }
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toRemove) {
                // 注意是this.usedSize - 1,将此时 i 之后的元素统一往前搬移一个位置
                for (int j = i; j < this.usedSize - 1; ++j) {
                    this.elem[j] = this.elem[j + 1];
                }
                this.elem[this.usedSize - 1] = 0; // 要完整的删除,将挪动的最后一个元素的原本位置 置空
                this.usedSize--; // 删除后不要忘记更改顺序表的有效长度
                return; // 只删除第一次出现的
            }
        }
    }
    /**
     * /判定是否包含某个元素
     * @param toFind 要查找的元素
     * @return true->包含, false->不包含
     */
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind)  return true;
        }
        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return i;
            }
        }
        System.out.println("在数组中没有找到该元素");
        return -1;
    }
    // 获取 pos 位置的元素
    public int getPos(int pos) {
        if (pos < 0 || pos >= this.usedSize) {
            System.out.println("pos的位置不合法");
            return -1;
        }
        else {
            return this.elem[pos];
        }
    }
    // 给 pos 位置的元素设为 value
    public void setPos(int pos, int value) {
        if (pos < 0 || pos > this.usedSize) {
            System.out.println("pos位置不合法");
            return;
        }
        if (pos == this.usedSize) { // 对这种情况要单独处理,此时相等于增加元素
            this.elem[pos] = value;
            this.usedSize++;
        }
        else {
            this.elem[pos] = value;
        }
    }
    // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }
    // 清空顺序表
    public void clear() {
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = 0;
        }
        this.usedSize = 0; // 注意有效数组长度也要清零
    }
}


📝Test.java

Test.java用于顺序表的各个接口的测试

/**
 * 对顺序表进行测试的代码
 */
public class Test {
    public static void main(String[] args) {
        MyArraysList myArraysList = new MyArraysList();
        // 尾插四个数字
        myArraysList.addTail(12);
        myArraysList.addTail(32);
        myArraysList.addTail(17);
        myArraysList.addTail(32);
        // 进行扩容
        myArraysList.expand();
        // 指定在pos位置新增元素
        myArraysList.addPos(1, 777);
        // 打印当前的顺序表
        System.out.print("第一次测试的顺序表为:");
        myArraysList.display();
        // 删除顺序表中首次出现的元素32
        myArraysList.removeKey(32);
        // 获取顺序表中 1下标的元素值
        int tmp = myArraysList.getPos(1);
        System.out.println("顺序表中下标为1的元素的值为:" + tmp);
        // 给顺序表中1下标的元素设为value
        myArraysList.setPos(1, 100);
        // 打印此时的顺序表
        System.out.print("修改后第二次测试的顺序表为:"); // 此时1下标的值为100
        myArraysList.display();
        // 顺序表此时的有效长度
        System.out.println("顺序表的有效长度为:" + myArraysList.size());
        // 清空顺序表
        myArraysList.clear();
        System.out.print("第三次测试的顺序表为:");
        myArraysList.display();
        System.out.println("清空顺序表后,顺序表的有效长度为:" + myArraysList.size());
    }
}


三.ArrayList 讲解


       实现了List接口,底层为动态类型顺序表,也就是说在Java中,已经写好了顺序表,我们可以在了解顺序表的基础原理之后,我们就可以更好的使用该类。

代码实现:

public static void main(String[] args) {
// ArrayList创建,推荐写法
// 构造一个空的列表
List<Integer> list1 = new ArrayList<>();
// 构造一个具有10个容量的列表
List<Integer> list2 = new ArrayList<>(10);
list2.add(1);
list2.add(2);
list2.add(3);
// list2.add("hello"); // 编译失败,List<Integer>已经限定了,list2中只能存储整形元素
// list3构造好之后,与list中的元素一致
ArrayList<Integer> list3 = new ArrayList<>(list2);
// 避免省略类型,否则:任意类型的元素都可以存放,使用时将是一场灾难
List list4 = new ArrayList();
list4.add("111");
list4.add(100);
}


ArrayList使用的方法


 方法         解释
boolean add(E e) 尾插e
void add(int index,E element) 将e插入index的位置
boolean addAII(Collection <?extendsE>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是否在线性表内



代码实现:

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("JavaSE");
    list.add("JavaWeb");
    list.add("JavaEE");
    list.add("JVM");
    list.add("测试课程");
    System.out.println(list);
// 获取list中有效元素个数
System.out.println(list.size());
// 获取和设置index位置上的元素,注意index必须介于[0, size)间
System.out.println(list.get(1));
list.set(1, "JavaWEB");
System.out.println(list.get(1));
// 在list的index位置插入指定元素,index及后续的元素统一往后搬移一个位置
list.add(1, "Java数据结构");
System.out.println(list);
// 删除指定元素,找到了就删除,该元素之后的元素统一往前搬移一个位置
list.remove("JVM");
System.out.println(list);
// 删除list中index位置上的元素,注意index不要超过list中有效元素个数,否则会抛出下标越界异常
list.remove(list.size()-1);
System.out.println(list);
// 检测list中是否包含指定元素,包含返回true,否则返回false
if(list.contains("测试课程")){
list.add("测试课程");
} 
}



四.总结


      数据结构是一门单独的学科,千位千位不要理解为只有Java才有,C语言等其他语言也能够实现此物理逻辑,C语言实现顺序表:C语言的顺序表构建

目录
相关文章
|
5月前
|
人工智能 安全 JavaScript
Java ArrayList:动态数组
本文探讨Java中的数组,对比C/C++、JS/PHP/Python等语言的数组特性。文章分析了Java数组的定义、创建方式及其规范,指出其优缺点。Java数组作为引用类型,在堆上分配内存,支持动态大小,避免了C/C++中裸数组的常见问题(如越界访问)。然而,Java数组也存在性能瓶颈和设计缺陷,例如运行时的安全检查影响速度,无法创建超大数组或泛型数组,且多线程场景下缺乏同步机制。作者建议在实际开发中用集合替代数组以规避这些问题。
119 1
|
6月前
|
人工智能 安全 Java
智慧工地源码,Java语言开发,微服务架构,支持分布式和集群部署,多端覆盖
智慧工地是“互联网+建筑工地”的创新模式,基于物联网、移动互联网、BIM、大数据、人工智能等技术,实现对施工现场人员、设备、材料、安全等环节的智能化管理。其解决方案涵盖数据大屏、移动APP和PC管理端,采用高性能Java微服务架构,支持分布式与集群部署,结合Redis、消息队列等技术确保系统稳定高效。通过大数据驱动决策、物联网实时监测预警及AI智能视频监控,消除数据孤岛,提升项目可控性与安全性。智慧工地提供专家级远程管理服务,助力施工质量和安全管理升级,同时依托可扩展平台、多端应用和丰富设备接口,满足多样化需求,推动建筑行业数字化转型。
212 5
|
3月前
|
Java 索引
Java ArrayList中的常见删除操作及方法详解。
通过这些方法,Java `ArrayList` 提供了灵活而强大的操作来处理元素的移除,这些方法能够满足不同场景下的需求。
395 30
|
3月前
|
监控 Java API
Java语言按文件创建日期排序及获取最新文件的技术
这段代码实现了文件创建时间的读取、文件列表的获取与排序以及获取最新文件的需求。它具备良好的效率和可读性,对于绝大多数处理文件属性相关的需求来说足够健壮。在实际应用中,根据具体情况,可能还需要进一步处理如访问权限不足、文件系统不支持某些属性等边界情况。
209 14
|
4月前
|
Java 编译器 应用服务中间件
为什么说 Java 语言编译与解释并存的原因
在编程语言的世界里,Java以其独特的“编译与解释并存”特性独树一帜。这一特性不仅赋予了Java强大的跨平台能力,还使其在性能和灵活性上达到了很好的平衡。接下来,我们将深入探讨Java语言这一特性的本质、原理以及在实际应用中的体现。
97 6
|
3月前
|
JSON JavaScript 前端开发
Python+JAVA+PHP语言,苏宁商品详情API
调用苏宁商品详情API,可通过HTTP/HTTPS发送请求并解析响应数据,支持多种编程语言,如JavaScript、Java、PHP、C#、Ruby等。核心步骤包括构造请求URL、发送GET/POST请求及解析JSON/XML响应。不同语言示例展示了如何获取商品名称与价格等信息,实际使用时请参考苏宁开放平台最新文档以确保兼容性。
|
4月前
|
分布式计算 Java 大数据
Java 语言基础概念与常识之主要特点解析
Java是一种广泛应用于企业级开发、移动应用(如Android)、大数据处理及云计算等领域的编程语言。其核心特点包括跨平台性(一次编写,到处运行)、面向对象设计、自动垃圾回收、多线程支持和高性能表现。Java通过JVM实现跨平台,具备强大的健壮性和安全性,同时拥有丰富的标准库与活跃的开发者社区。本文深入解析Java的技术优势及其在电商系统、大数据处理和云计算中的实际应用,并提供相关面试资料供学习参考。
128 0
|
4月前
|
网络协议 安全 Java
实现Java语言的文件断点续传功能的技术方案。
像这样,我们就完成了一项看似高科技、实则亲民的小工程。这样的技术实现不仅具备实用性,也能在面对网络不稳定的挑战时,稳稳地、不失乐趣地完成工作。
253 0
|
7月前
|
存储 Java 数据安全/隐私保护
Java语言位运算符详解
Java语言提供了7种位运算符:按位与(&)、按位或(|)、按位异或(^)、取反(~)、左移(&lt;&lt;)、带符号右移(&gt;&gt;)和无符号右移(&gt;&gt;&gt;)。这些运算符主要用于对long、int、short、byte和char类型的数据进行二进制位级别的操作,不能用于double、float和boolean类型。文中详细讲解了每种运算符的规则和应用场景,并指出位运算在实际开发中有重要应用价值,不仅限于面试。
299 2
|
7月前
|
Java 开发者
课时2:Java语言特点
课时2介绍了Java语言的多个关键特性。作为开源且半开源的产品,Java成为通用技术标准,拥有透明的开发环境。其面向对象的设计、自动内存回收、简化指针处理(使用引用)、支持多线程编程、高效的网络处理能力(如NIO)及良好的可移植性,共同促成了Java的强大生态系统和广泛应用。

热门文章

最新文章