Java语言----动态顺序表（ArrayList）

╰+攻爆jí腚メ 2024-04-20 14:25 58阅读 0赞

**目录**

一.顺序表

二.顺序表的手动实现

2.1顺序表的创建

2.2.基本功能的实现

2.2.1扩容顺序表

2.2.2 判断顺序表是否为满

2.2.3 判断顺序表是否为空

2.2.4打印顺序表

2.2.5清空顺序表

2.3四大功能的实现

2.3.1增加元素

2.3.2删除元素

2.3.3查找元素

2.3.4更改数据

总代码

?MyArraysList.java

?Test.java

一.ArrayList 讲解

--------------------

> > ?个人主页：[ tq02的博客\_CSDN博客-C语言,Java,Java数据结构领域博主][tq02_CSDN_-C_Java_Java]  
> > ?梦的目标：努力学习，向Java进发，拼搏一切，让自己的未来不会有遗憾。  
> > ?欢迎各位→点赞? + 收藏⭐ + 评论?+关注✨  
> > 本章讲解内容：顺序表的讲解
> > 
> > ![48b44c8bb51a4c12b587a22f8f6c26d1.jpeg][]
> > 
> > 使用编译器：IDEA

## 一.顺序表 ##

![879126b6af89446496a80049aaad8b37.png][]

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

###  ###

## 二.顺序表的手动实现 ##

### 2.1顺序表的创建 ###

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

### 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使用的方法 ###

<table style="width:600px;"> 
 <tbody> 
  <tr> 
   <td style="width:300px;">&nbsp; &nbsp; &nbsp; &nbsp; 方法</td> 
   <td style="width:198px;">&nbsp; &nbsp; &nbsp; &nbsp; 解释</td> 
  </tr> 
  <tr> 
   <td style="width:300px;">boolean add(E e)</td> 
   <td style="width:198px;">尾插e</td> 
  </tr> 
  <tr> 
   <td style="width:300px;">void add(int index,E element)</td> 
   <td style="width:198px;">将e插入index的位置</td> 
  </tr> 
  <tr> 
   <td style="width:300px;">boolean addAII(Collection &lt;?extendsE&gt;c</td> 
   <td style="width:198px;">尾插c中的元素</td> 
  </tr> 
  <tr> 
   <td style="width:300px;">E remove(int index)</td> 
   <td style="width:198px;">删除index位置元素</td> 
  </tr> 
  <tr> 
   <td style="width:300px;">boolean remove(Object o)</td> 
   <td style="width:198px;">删除遇见的第一个 o</td> 
  </tr> 
  <tr> 
   <td style="width:300px;">E get(int index)</td> 
   <td style="width:198px;">获取下标index 位置元素</td> 
  </tr> 
  <tr> 
   <td style="width:300px;">E set(int index,E element)</td> 
   <td style="width:198px;">将下标index 位置元素设置为element</td> 
  </tr> 
  <tr> 
   <td style="width:300px;">void clear()</td> 
   <td style="width:198px;">清空</td> 
  </tr> 
  <tr> 
   <td style="width:300px;">boolean contains(Object o)</td> 
   <td style="width:198px;">判断o是否在线性表内</td> 
  </tr> 
 </tbody> 
</table>

代码实现：

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语言的顺序表构建][C]

[tq02_CSDN_-C_Java_Java]: https://blog.csdn.net/m0_74097410?type=blog
[48b44c8bb51a4c12b587a22f8f6c26d1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/544ac5fd7b7e44368101043f685768a9.jpeg
[879126b6af89446496a80049aaad8b37.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/981559a549b04f5596d24bf8fc952d3f.png
[C]: https://blog.csdn.net/m0_74097410/article/details/128453310?spm=1001.2014.3001.5501