java数据结构集合复习之ArrayList与顺序表

news/2024/7/9 19:03:57 标签: java, 数据结构, windows

java_0">前言: 这是我最一年学习java的一部分的回顾总结

1.List

1.1什么是List?

在框架集合中,List是一个接口,继承自Collection。
在这里插入图片描述

Collection也是一个接口，该接口中规范了后序容器中常用的一些方法，具体如下所示
在这里插入图片描述
在这里插入图片描述

--------
boolean add(E e)尾插 e
void add(int index, E element)将 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 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

站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

1.2 List的使用

List是个接口，并不能直接用来实例化
如果要使用，必须去实例化List的实现类

java">import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListExample {
    public static void main(String[] args) {
        // 使用 ArrayList 实现类
        List<String> arrayList = new ArrayList<>();
        arrayList.add("Apple");
        arrayList.add("Banana");
        arrayList.add("Orange");

        System.out.println("ArrayList: " + arrayList);

        // 使用 LinkedList 实现类
        List<String> linkedList = new LinkedList<>();
        linkedList.add("Mango");
        linkedList.add("Kiwi");
        linkedList.add("Grape");

        System.out.println("LinkedList: " + linkedList);
    }
}

List 不能直接实例化是因为接口本身只是一种规范或契约，它定义了一组方法的签名，但并没有提供这些方法的具体实现。
接口的主要目的是为了实现多态性和代码的解耦。通过定义接口，不同的类可以实现相同的接口，从而以统一的方式进行处理。 打个比方，想象 List
接口是一个菜谱，它只规定了要有哪些菜（方法），但没有告诉你具体怎么做这些菜（方法的实现）。只有具体的厨师（实现类），比如 ArrayList
或者 LinkedList ，才能按照这个菜谱做出实际的菜肴（实现方法）。

ArrayList与顺序表

2.1 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储
在这里插入图片描述

在这里插入图片描述

2.2 顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

下面是手动实现一个顺序表的实现

java">package com;

import java.util.Arrays;

public class SeqList {
    private int[] array;
    //记录当前顺序表当中 有多少个有效的数据
    private int size;
    private static final int INIT_CAPACITY = 5;
    // 默认构造方法 将顺序表的底层容量设置为INIT_CAPACITY
    public SeqList(){
        this.array = new int[INIT_CAPACITY];
    }
    //判断当前顺序表是否满了 注意在进行新增操作是都要考虑数组是否需要判断满表
    public boolean isFull(){
        //返回当前表中的元素个数与当前表的长度作比较若相等是ture,反之false
        return size == array.length;
    }
    //给数组扩容 注意在进行新增操作是都要考虑数组是否需要扩容
    private void resize(){
        array = Arrays.copyOf(array,2*array.length);
    }
    // 新增元素,默认在数组最后新增
    public void add(int data){

        if (isFull()){
            resize();
        }
        this.array[size] = data;
        //将当前指针位置＋1,每次新增操作都需要
        size++;
    }
    // 在 pos 位置新增元素
    public void add(int pos,int data){
        //判断pos位置合不合法
        if (pos<0 || pos>this.size){
            throw new PosOutBoundsException("add 元素的时候，pos位置不合法！");
        }
        if(isFull()){
            resize();
        }
        for (int i = size-1; i >= pos; i--) {
            array[i+1] = array[i];
        }
        array[pos] = data;
        size++;
    }
    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i <this.size; i++) {
            if(array[i] == toFind){
                return true;
            }
        }
        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.size; i++) {
            if (array[i] == toFind){
                return i;
            }
        }
        return -1;
    }
    // 获取 pos 位置的元素
    public int get(int pos) {
        if (pos<0 || pos>this.size){
            throw new PosOutBoundsException("pos位置不合法！");
            
        }
        return array[pos];

    }
    // 给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        if (pos<0 || pos>this.size){
            throw new PosOutBoundsException("pos位置不合法！");
        }
        this.array[pos] = value;

    }
    //删除第一次出现的关键字key
    public void remove(int toRemove) {
        if (isEmpty()){
            return;
        }
        int index = indexOf(toRemove);
        if (index == -1){
            System.out.println("没有你要删除的数据");
        }
        for (int i = index; i < this.size-1; i++) {
            this.array[i] = this.array[i+1];
        }
        size--;
    }
    // 获取顺序表长度
    public int size() {
        return size;
    }
    // 清空顺序表
    public void clear() {
       size=0;
    }
    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    public void display() {
        for (int i = 0; i < this.size; i++) {
            System.out.println(this.array[i]+ " ");
        }
    }
    public boolean isEmpty(){
        return this.size == 0;
    }
    public static void main(String[] args) {
        SeqList seqList = new SeqList();
        seqList.add(1);
        seqList.add(2);
        seqList.add(3);
        seqList.add(4);
        seqList.add(1,10000);
        seqList.display();
    }
}

2.3 ArrayList的遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

java">public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        // 使用下标+for遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
        // 借助foreach遍历
        for (Integer integer : list) {
            System.out.print(integer + " ");
        }
        System.out.println();
        Iterator<Integer> it = list.listIterator();
        while (it.hasNext()){
            System.out.print(it.next()+" ");
        }
        System.out.println();
    }

在这里插入图片描述
注意:

  1. ArrayList最常使用的遍历方式是：for循环+下标 以及 foreach
  2. 迭代器是设计模式的一种

2.4ArrayList的扩容机制

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式：

java">private static final int DEFAULT_CAPACITY = 10;// 默认容量大小
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 默认空间
transient Object[] elementData; 存放元素的空间

public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// 获取旧空间大小
int oldCapacity = elementData.length;
// 预计按照1.5倍方式扩容
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用copyOf扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 如果minCapacity小于0，抛出OutOfMemoryError异常
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

总结:

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

2.5 ArrayList的小练习

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
杨辉三角
解法:

java"> public List<List<Integer>> generate(int numRows) {
         List<List<Integer>> allList = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(1);
            for (int j = 1; j < i; j++) {
               list.add(allList.get(i-1).get(j-1)+allList.get(i-1).get(j));
            }
            if(i != 0){
                list.add(1);
            }
            allList.add(list);
        }
        return allList;
    }

2.6ArrayList的问题及思考

问题:

  1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)
  2. 增容需要申请新空间,拷贝数据释放旧空间,会有不小的消耗
  3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考:
如何解决以上问题呢？

  1. 对于频繁的插入或删除元素 我们可以适合的数据结构,例如LinkedList。LinkedList底层使用链表实现，在链表中间进行插入和删除操作的时间复杂度为 O(1)，但它在随机访问元素时的性能相对较差。

  2. 针对增容带来消耗的问题：
    如能预先估计集合可能需要存储的元素数量，在创建ArrayList时指定合适的初始容量，可以减少扩容的次数。或者采用内存池技术：创建一个内存池来管理内存分配和释放。当需要扩容时，从内存池中获取预先分配好的合适大小的内存块，而不是每次都进行新的内存申请和释放操作。

  3. 关于增容导致的空间浪费问题：
    一种解决思路是使用自定义的动态数组实现，根据实际元素数量更精确地控制扩容策略，而非简单地按照固定倍数扩容。例如，可以根据当前元素数量和一个预设的负载因子来决定是否扩容以及扩容的幅度。但这种方式需要自己实现动态数组的相关逻辑，增加了编程的复杂性


http://www.niftyadmin.cn/n/5538989.html

相关文章

12 Dockerfile详解

12 Dockerfile详解

目录 1. Dockerfile 2. Dockerfile构建过程 2.1. Dockerfile编写规则&#xff1a; 2.2. Docker执行Dockerfile的大致流程 2.3. 总结 3. Dockerfile指令 3.1. FROM 3.2. MAINTAINER 3.3. RUN 3.4. EXPOSE 3.5. WORKDIR 3.6. USER 3.7. ENV 3.8. VOLUME 3.9. ADD …
阅读更多...
Servlet与Servlet容器

Servlet与Servlet容器

什么是Servlet? Servlet是Java EE&#xff08;现称Jakarta EE&#xff09;中的一个组件&#xff0c;通常用于创建动态Web内容。Servlet是运行在Web服务器上的Java程序&#xff0c;它处理客户端的请求并生成响应。Servlet的核心功能是处理HTTP请求和响应。下面是一个servlet例…
阅读更多...
14-8 小型语言模型的兴起

14-8 小型语言模型的兴起

过去几年&#xff0c;我们看到人工智能能力呈爆炸式增长&#xff0c;其中很大一部分是由大型语言模型 (LLM) 的进步推动的。GPT-3 等模型包含 1750 亿个参数&#xff0c;已经展示了生成类似人类的文本、回答问题、总结文档等能力。然而&#xff0c;虽然 LLM 的能力令人印象深刻…
阅读更多...
mac软件卸载后的残留文件删除 mac如何卸载应用程序

mac软件卸载后的残留文件删除 mac如何卸载应用程序

很多人都不知道&#xff0c;mac使用系统方式卸载后会有残留文件未被删除&#xff0c;久而久之就会占用大量的磁盘空间。今天小编就来教大家如何删除mac软件卸载后的残留文件&#xff0c;如果你想不留痕迹的删除&#xff0c;mac又该如何正确卸载应用程序&#xff0c;本文将一一为…
阅读更多...
阿里国际站

阿里国际站

营业额流量 x 转化 x 客单价 x 复购率 x 新机会 流量&#xff0c;代表的是进店买家数&#xff0c;它取决于店铺或产品在买家面前的曝光和推荐是否精准有效 转化率,代表进店买家最终有多大比例转化为成交客户 客单价&#xff1a;代表买家一次购买的货值 复购率&#xff1a;…
阅读更多...
泰勒公式中拉格朗日余项和佩亚诺余项的区别及具体的应用场景案例

泰勒公式中拉格朗日余项和佩亚诺余项的区别及具体的应用场景案例

泰勒公式是微积分中的一个重要工具&#xff0c;用于将一个函数在某一点附近展开成多项式形式&#xff0c;以便于近似计算和分析。泰勒公式的一般形式为&#xff1a; f ( x ) f ( a ) f ′ ( a ) ( x − a ) f ′ ′ ( a ) 2 ! ( x − a ) 2 ⋯ f ( n ) ( a ) n ! ( x − a…
阅读更多...
EtherCAT主站IGH-- 8 -- IGH之domain.h/c文件解析

EtherCAT主站IGH-- 8 -- IGH之domain.h/c文件解析

EtherCAT主站IGH-- 8 -- IGH之domain.h/c文件解析 0 预览一 该文件功能`domain.c` 文件功能函数预览二 函数功能介绍1. `ec_domain_init`2. `ec_domain_clear`3. `ec_domain_add_fmmu_config`4. `ec_domain_add_datagram_pair`5. `ec_domain_finish`6. `ecrt_domain_reg_pdo_en…
阅读更多...
工地/矿区/电力/工厂/环卫视频智能安全监控反光衣AI检测算法的原理及场景应用

工地/矿区/电力/工厂/环卫视频智能安全监控反光衣AI检测算法的原理及场景应用

一、引言 随着科技的快速发展&#xff0c;特别是在智能交通和安全生产领域&#xff0c;对于夜间或弱光环境下的人员识别和安全监控需求日益凸显。反光衣作为一种重要的安全装备&#xff0c;被广泛应用于道路施工、工地作业、夜间巡逻、安全生产等场景&#xff0c;旨在提高人员的…
阅读更多...
最新文章

Copyright @ 2022~2023