当前位置： 首页 > article >正文

数据结构-ArrayList和顺序表

article 2025/1/19 13:16:36

1.线性表

线性表是n个具有相同类型的数据元素所组成的有限序列，当n=0时，线性表为一个空表。

常见的线性表：顺序表，链表，栈和队列...

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

2.顺序表 

2.1 什么是顺序表 

顺序表是一段连续的存储单元来依次存储线性表中的数据元素。一般情况下采用数组存储。

 

2.2 顺序表的特点 

1.存储连续：顺序表的存储单元在内存中是连续的，这意味着每个元素的地址都是相邻连续的

2.随机访问：由于存储单元是连续的，可以通过元素的下标直接访问该位置的元素，时间复杂度为O(1)

3.存储密度高：顺序表的存储单元只存储数据元素本身，没有额外的存储开销

2.3 实现一个顺序表

public class MySequentialList{
    private int[] array;
    private int size;
    //默认构造方法
    MySequentialList(){}
    //将顺序表的容量设为initCapacity
    MySequentialList(int initCapacity){}
    //在数组末尾新增一个元素
    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(){}
}

实现的思路：

1.MySequentialList(int initCapacity)

只需要将数组初始化大小为initCapacity即可

2.add(int data)

在数组最后的位置新增元素，要注意数组是否已满，如果已满，就要对数组进行扩容操作

3.add(int pos,int data)

首先要判断插入位置pos是否合法，如果pos小于0或pos大于数组的长度，则位置不合法要进行异常处理。如果位置合法，还要判断数组是否已满，进行插入操作时，要注意先将原pos以及pos后面的元素全都向后移动一位，再进行插入操作，如果直接插入，则只是单纯的元素覆盖。插入后，数组的长度加1

4.contains(int toFind)

判断是否包含某个元素，只需要遍历数组并进行比较，看数组中是否有存在要查找的元素，如果有，则返回true，没有则返回false

5.indexOf(int toFind)

遍历数组，看数组中是否存在要查找的元素，如果存在，则返回给元素位置的下标，如果不存在，则返回-1

6.get(int pos)

获取pos位置的元素，首先要判断pos位置是否合法，如果pos小于0或者pos大于数组的长度，则pos不合法，返回-1。如果合法，直接返回下标为pos的元素

7.set(int pos,int value)

给pos位置的元素设置为value，单纯的进行对应下标元素覆盖即可

8.remove(int toRemove)

删除第一次出现关键字key，遍历数组，看key是否存在。如果不存在，则返回-1。如果存在，只需要将该位置后面的所有元素先前移动一位即可

9.size()

直接返回数组的有效长度，有效长度指的是数组中有效元素的个数，不是单纯的数组长度

10.clear()

清空顺序表，重新初始化数组，并将数组的长度置为0

我们后续以ArrayList的实现为例。

3.ArrayList

3.1 什么是ArrayList

在集合框架中，ArrayList是 Java 标准库中的一个非常常用的类，它实现了 List接口，提供了动态数组的功能。 ArrayList内部使用数组来存储元素，因此它具备顺序表的所有特点，是顺序表的一种实现。

 

说明：

1.ArrayList 是以泛型的方式实现的，使用时必须要先实例化

2.ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问

3.ArrayList实现了Cloneable接口，表明ArrayList是可以clone的

4.ArrayList实现了Serializable接口，表面ArrayList是支持序列化的

5.ArrayList是线程不安全的，在单线程下可以使用

6.ArrayList是通过动态的数组实现的，是一段连续的空间，并且可以进行扩容

3.2 ArrayList的构造方法

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

 代码演示：

public class Test {
    public static void main(String[] args) {
        //无参构造
        List<Integer> list1=new ArrayList<>();
        
        //利用其他Collection构建ArrayList
        ArrayList<Integer> arrayList=new ArrayList<>();
        List<Integer> list2=new ArrayList<>(arrayList);
       
        //指定顺序表容量
        List<Integer> list3=new ArrayList<>(10);
        
    }
}

3.3 ArrayList的常见操作

ArrayList常见的方法

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

代码演示：

import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        List<Integer> list=new ArrayList<>();
        System.out.println(list);
        //在尾部插入元素
        list.add(1);
        list.add(5);
        list.add(3);
        list.add(5);
        list.add(10);
        System.out.println(list);
        //在下标为2的位置增加元素
        list.add(2,4);
        System.out.println(list);
        //删除下标为2的元素
        list.remove(2);
        System.out.println(list);
        //删除遇到的第一个5元素
        Integer a=5;
        list.remove(a);
        System.out.println(list);
        //获取下标为1的元素
        int e=list.get(1);
        System.out.println(e);
        //将下标为1的元素设置为99
        list.set(1,99);
        System.out.println(list);
        //判断5是否在线性表中
        System.out.println(list.contains(5));
        //返回第一个5所在的下标
        e=list.indexOf(5);
        System.out.println(e);
        //返回最后一个5所在的下标
        e= list.lastIndexOf(5);
        System.out.println(e);
        //截取部分list,左闭右开
        List<Integer> newList=new ArrayList<>();
        newList=list.subList(1,3);
        System.out.println(newList);
        //将newList中的元素全部添加入list中
        list.addAll(newList);
        System.out.println(list);
        //清空list
        list.clear();
        System.out.println(list);
    }
}

 

3.4 ArrayList的遍历 

ArrayList的遍历方式主要分为3种：

1.for循环搭配下标

2.foreach

3.使用迭代器

public class Test {
    public static void main(String[] args) {
        List<String> list=new ArrayList<>();
        list.add("hajimi");
        list.add("is");
        list.add("a");
        list.add("cat");
        //使用for循环搭配下标
        for(int i=0;i<list.size();i++){
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        //使用foreach遍历
        for(String s:list){
            System.out.print(s+" ");
        }
        System.out.println();
        //使用迭代器遍历
        Iterator<String> it=list.listIterator();
        while(it.hasNext()){
            System.out.print(it.next()+" ");
        }
    }
}

 

 

4.深度理解ArrayList 的扩容机制

观察原码：

int DEFAULT_CAPACITY表示默认的容量大小

Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示默认的空间

Object[] elementData表示存放元素的空间

 ArrayList的无参构造函数，将elementData初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这是一个空数组，用于创建一个具有默认容量为 10的空ArrayList

ArrayList的add方法首先调用ensureCapacityInternal(size+1)，size表示当前顺序表的有效长度，size+1表示添加元素后应有的长度 

 size+1的值传递给ensureCapacityInternal的形参minCapacity，ensureCapacityInternal先调用calculateCapacity(Object[] element,int minCapacity)传入存放元素的空间elementData和minCapacity

calculateCapacity(Object[] elementData,int minCapacity)用来计算ArrayList需要增长到的最小容量。判断elementData是否等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果相等则意味着ArrayList当前没有分配任何容量，是空的。在这种情况下，方法返回DEFAULT_CAPACITY(10)和minCapacity中的较大值。如果element不是空数组，则意味着ArrayList已经有了一些容量，这种情况下，直接返回minCapacity，可以保证它至少增长到minCapacity即可

 calculateCapacity的返回值传递给ensureExplicitCapacity的形参minCapacity，判断当前是否需要扩容，如果minCapacity大于数组的长度，则表示需要进行扩充

 ArrayList的扩容函数grow(int minCapacity)用于增加ArrayList的内部数组elementData的容量，使其至少容纳minCapacity个元素。

int newCapacity=oldCapacity+(oldCapacity >> 1)计算新的容量，通常是当前容量的1.5倍

if(newCapacity - minCapacity < 0)判断新容量是否满足最小的需求，如果计算出的容量仍然小于最小的容量，则将newCapacity设置为minCapacity

if(newCapacity-MAX_ARRAY_SIZE > 0)检查新容量是否超出最大数组的大小，如果超过了调用hugeCapacity处理这种情况(将新容量设为Integer.MAX_VALUES)

elementData = Arrays.copyOf(elementData,newCapacity)使用copyOf创建一个新的数组，并将就数组中的元素复制到新数组中。

总结：

1.首先判断是否需要进行扩容，如果需要进行扩容，调用grow方法

2.计算扩容所需的最小的容量

初步预估按照1.5倍大小进行扩容

如果用户所需大小大于预估的1.5倍，则按照用户所需大小进行扩容

扩容前检查是否可以扩容成功，防止太大导致扩容失败

3.使用Arrays.copyOf进行扩容

5.实现一个ArrayList

package datastructure;

import java.util.Arrays;

public class MyArrayList {
    public int[] elem;
    public int usedSize;//0
    //默认容量
    private static final int DEFAULT_SIZE = 2;

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

    /**
     * 打印顺序表:
     *   根据usedSize判断即可
     */
    public void display() {

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

    // 新增元素,默认在数组最后新增
    public void add(int data) {
        if(isFull()){
            //扩容
            this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize]=data;
        this.usedSize++;
    }

    /**
     * 判断当前的顺序表是不是满的！
     * true:满   false代表空
     */
    public boolean isFull() {
        if(this.usedSize==this.elem.length){
            return true;
        }
        return false;
    }


    private boolean checkPosInAdd(int pos) {
        if(pos<0||pos>usedSize){
            System.out.println("位置不合法");
            return false;
        }
        return true;//合法
    }

    // 在 pos 位置新增元素
    //移动数据，从后向前防止数值被覆盖
    public void add(int pos, int data) {
        if(pos<0||pos>this.usedSize){
            System.out.println("位置不合法");
            return;
        }
        if(isFull()){
            //扩容
            this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
        }
        for(int i=this.usedSize-1;i>=pos;i--){
            this.elem[i+1]=this.elem[i];
        }
        this.elem[pos]=data;
        usedSize++;
    }

    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for(int i=0;i<this.usedSize;i++){
            if(elem[i]==toFind){
                return true;
            }
        }
        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        if(isEmpty()){
            System.out.println("表中没有元素");
            return -1;
        }
        for(int i=0;i<usedSize;i++){
            if(elem[i]==toFind){
                return i;
            }
        }
        System.out.println("没找到");
        return -1;
    }

    // 获取 pos 位置的元素
    public int get(int pos) {
        if(pos<0&&pos>=usedSize){
            System.out.println("输入不合法！");
            return -1;
        }
        if(!isEmpty()){
            return elem[pos];
        }
        return -1;
    }

    private boolean isEmpty() {
        if(usedSize==0){
            return true;
        }
        return false;
    }
    // 给 pos 位置的元素设为【更新为】 value
    public void set(int pos, int value) {
        if(pos<0||pos>=usedSize)
            return;
        elem[pos]=value;
    }

    /**
     * 删除第一次出现的关键字key
     * @param key
     */
    public void remove(int key) {
        int index=indexOf(key);
        if(index==-1){
            return;
        }
        for(int i=index;i<usedSize-1;i++){
            this.elem[i]=this.elem[i+1];
        }
        this.usedSize--;
    }

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

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

6.ArrayList的特点

1.基于数组实现：

ArrayList使用一个动态数组来存储元素

2.动态数组容量

ArrayList可以根据添加元素的情况进行自动扩容，默认情况下是按照当前容量的1.5倍进行扩容

3.随机访问效率高，时间复杂度为O(1)

ArrayList基于数组实现，支持随机访问，时间复杂度为O(1)

4.插入和删除操作时间复杂度为O(n)

在ArrayList的中间位置插入或删除元素效率不高，这些操作会移动插入点之后的所有元素，时间复杂度为O(n)，但是在末尾插入或删除元素的时间复杂度为O(1)

5.允许有重复的元素

6.允许存储null元素

7.ArrayList是线程不安全的


http://www.kler.cn/a/509301.html

相关文章：

  • 探索与创作：2024年CSDN平台上的成长与突破
  • AI 大爆发时代，音视频未来路在何方？
  • 高性能、并发安全的 Go 嵌入式缓存库 如何使用？
  • MQ消息队列
  • 向harbor中上传镜像（向harbor上传image）
  • C#中无法在串口serialPort1_DataReceived启动定时器的解决方法
  • SSM课设-学生管理系统
  • 免费送源码：Java+ssm+MySQL 基于PHP在线考试系统的设计与实现 计算机毕业设计原创定制
  • 青少年编程与数学 02-007 PostgreSQL数据库应用 07课题、表的操作
  • 基于金融新闻的大型语言模型强化学习在投资组合管理中的应用
  • 了解 .mgJSON 文件
  • 语音技术在播客领域的应用（2）
  • 网络编程-UDP套接字
  • python学opencv|读取图像（三十五）反阈值处理
  • 上位机知识篇---常见Windows操作
  • PortSwigger靶场练习---第二关-查找和利用未使用的 API 端点
  • 在IDEA中使用通义灵码插件：全面提升开发效率的智能助手
  • ubuntu常见指令详解
  • 在线图片像素颜色拾取工具
  • references配置项详解
  • Vue2+OpenLayers实现添加多边形覆盖物（提供Gitee源码）
  • 医药新零售的下半场，叮当健康找到增长搭子
  • Three.js+Vue3+Vite应用lil-GUI调试开发3D效果（三）
  • 【AI论文】迈向大型语言模型（LLM）训练开放数据集的最佳实践
  • 20250118面试鸭特训营第26天
  • 初学stm32 --- RS485