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

【Java 数据结构】List，ArrayList与顺序表

ds 2025/5/7 8:06:40

目录

一. List

1.1 什么是List

1.2 List 的常见方法

1.3 List 的使用

二. 顺序表

2.1 什么是顺序表

2.2 实现自己的顺序表

2.2.1 接口实现

2.2.2 实现顺序表

三. ArrayList

3.1 ArrayList简介

3.2 ArrayList的三个构造方法

3.2.1 无参构造方法

3.2.2 带一个参数的构造方法

3.3 ArrayList的常见方法

3.4 ArrayList 的遍历

3.4.1 直接打印

3.4.2 for循环遍历

3.4.3 借助for-each遍历

3.4.4 迭代器遍历

一. List

1.1 什么是List

在集合框架中，List是一个接口，继承自Collect

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

1.2 List 的常见方法

下面是List接口中的一些常见方法

1.3 List 的使用

由于List 是一个接口，不能直接实例化对象，但是在集合框架中，ArrayList和LinkedList都实现了List接口

二. 顺序表

2.1 什么是顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储，ArrayList就是顺序表的一种实现形式

2.2 实现自己的顺序表

在学习ArrayList之前，我们可以先试着写一个自己实现的顺序表，能帮助我们在使用ArrayList的方法以及了解它时更加得心应手

2.2.1 接口实现

public class IList {public void add(int data) { }// 在 pos 位置新增元素public void add(int pos, int data) { }// 判定是否包含某个元素public boolean contains(int toFind) { return true; }// 查找某个元素对应的位置public int indexOf(int toFind) { return -1; }// 获取 pos 位置的元素public int get(int pos) { return -1; }// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) { }//删除第⼀次出现的关键字keypublic void remove(int toRemove) { }// 获取顺序表⻓度public int size() { return 0; }// 清空顺序表public void clear() { }// 打印顺序表，注意：该⽅法并不是顺序表中的⽅法，为了⽅便看测试结果给出的public void display() { }
}

下面，我们自己的顺序表将会实现并重写IList中的所有方法

2.2.2 实现顺序表

import java.util.Arrays;class EmptyListException extends RuntimeException{public EmptyListException(String message) {super(message);}
}class IndexException extends RuntimeException{public IndexException(String message) {super(message);}
}
public class MyArrayList implements IList{public int arr[];public final int Initial_Capacity=10;public int Used_size;public MyArrayList() {this.arr = new int [Initial_Capacity];}@Overridepublic void add(int data) {if(is_full()){grow();}this.arr[Used_size]=data;Used_size++;}@Overridepublic void add(int pos, int data) {if(is_full()){grow();}checkPos(pos);for (int i =Used_size-1; i>=pos; i--) {arr[i+1]=arr[i];}arr[pos]=data;Used_size++;}public boolean is_full(){if(arr.length==Used_size){return true;}return false;}public void grow(){this.arr= Arrays.copyOf(arr,arr.length*2);}@Overridepublic boolean contains(int toFind) {for (int i = 0; i <arr.length; i++) {if(arr[i]==toFind){return true;}}return false;}@Overridepublic int indexOf(int toFind) {for (int i = 0; i <arr.length; i++) {if (arr[i] == toFind) {return i;}}return -1;}@Overridepublic int get(int pos) {check(pos);isEmpty();return arr[pos];}public void check(int pos){if(pos<0||pos>=Used_size){throw new IndexException(pos+"位置下标访问不合法");}}public void checkPos(int pos){if(pos<0||pos>Used_size){throw new IndexException(pos+"位置下标访问不合法");}}public void isEmpty(){if(Used_size==0){throw new EmptyListException("该表为空表");}}@Overridepublic void set(int pos, int value) {check(pos);arr[pos]= value;}@Overridepublic void remove(int toRemove) {int index=indexOf(toRemove);if(index==-1){System.out.println("没有要删除的元素");return;}for (int i =index; i <Used_size-1; i++) {arr[i]=arr[i+1];}Used_size--;}@Overridepublic int size() {return Used_size;}@Overridepublic void clear() {for (int i = 0; i <Used_size; i++) {arr[i]=0;}Used_size=0;//如果数组中的是引用数据类型的元素时，一定要将其全部置为null（避免空间造成浪费）}@Overridepublic void display() {for (int i = 0; i <this.Used_size; i++) {System.out.print(arr[i]+" ");}System.out.println();}
}

注意：

  • 在删除和特定位置添加元素的方法中采用的是覆盖的思想，下面是添加元素到特定位置的流程图（将6添加到3下标位置）

  • 在 clear（）中如果要清空的顺序表是存放引用数据类型的话，一定要将其全部设置为null

三. ArrayList

3.1 ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口。具体框架如下：

注意：

  • ArrayList是以泛型的形式实现的，使用时必须要先实例化
  • ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

3.2 ArrayList的三个构造方法

3.2.1 无参构造方法

下面是ArrayList类中的源码截取：

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}private Object[] grow(int minCapacity) {int oldCapacity = elementData.length;if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */oldCapacity >> 1           /* preferred growth */);return elementData = Arrays.copyOf(elementData, newCapacity);} else {return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}}public void add(int index, E element) {rangeCheckForAdd(index);modCount++;final int s;Object[] elementData;if ((s = size) == (elementData = this.elementData).length)elementData = grow();System.arraycopy(elementData, index,elementData, index + 1,s - index);elementData[index] = element;size = s + 1;}

解释：

这里的 elementData 是 ArrayList 内部用于存储元素的数组，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个空数组。当使用无参构造方法创建 ArrayList 时，实际上只是将 elementData 初始化为一个空数组。当向 ArrayList 中添加第一个元素（仅限添加的第一个元素）时， ArrayList 会自动扩容，将数组容量扩展为默认容量（通常是10）。

3.2.2 带一个参数的构造方法

  • ArrayList(int initialCapacity)
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}

解释：通过这个构造方法，当传入一个大于0的整数作为参数时， ArrayList 会创建一个具有指定容量的数组来存储元素，这样可以在已知元素大概数量的情况下，减少数组扩容的次数，提高性能。如果传入0，则使用一个空数组。如果传入负数，会抛出异常，因为容量不能为负

  • ArrayList(Collection<? extends E> c)
 public ArrayList(Collection<? extends E> c) {Object[] a = c.toArray();if ((size = a.length) != 0) {if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData = EMPTY_ELEMENTDATA;}}

解释：使用集合类来构造ArrayList，将该集合类中的所有元素用来构造ArrayList，和ArrayList中的 addAll（Collection<? extends E> c）的作用类似，其中Collection<? extends E> c 表示可以传入实现了Collection接口并且泛型参数类型是E/E子类的集合类，下面是一个例子：这里不是一个集合类一个元素（与List的嵌套不同）

public static void main(String[] args) {ArrayList<Integer> list0=new ArrayList<>();list0.add(1);list0.add(2);ArrayList<Integer> list1=new ArrayList<>();list1.add(1);list1.add(2);ArrayList<Integer> list=new ArrayList<>(list0);//使用List0这个集合类来构造listlist.add(100);//向list中添加元素list.addAll(list1); //向list中来添加集合类System.out.println(list);System.out.println(list.size());}打印结果：
[1, 2, 100, 1, 2]
5
public static void main(String[] args) {ArrayList<ArrayList<Integer>> lists=new ArrayList<>();ArrayList<Integer> list3=new ArrayList<>();list3.add(1);list3.add(2);list3.add(3);lists.add(list3);System.out.println(lists.size());}打印结果：1

3.3 ArrayList的常见方法

ArrayList的方法很多，以下只列举常见的几种：

注意：

  • LIst<E>subList(int formIndex,int toIndex) 这个方法要重点注意（是个坑），1. 这个方法的返回值实际上是截取list部分的首地址，如果改变subList中的元素，被截取的原list中的元素也会发生改变，2. 截取部分是[  )

3.4 ArrayList 的遍历

3.4.1 直接打印

 public static void main(String[] args) {ArrayList<Integer> list3=new ArrayList<>();list3.add(1);list3.add(2);list3.add(3);System.out.println(list3);}打印结果：[1,2,3]

3.4.2 for循环遍历

public static void main(String[] args) {ArrayList<Integer> list3=new ArrayList<>();for (int i = 0; i <list3.size(); i++) {System.out.print(list3.get(i)+" ");}System.out.println();}打印结果：1 2 3

3.4.3 借助for-each遍历

public static void main(String[] args) {ArrayList<Integer> list3=new ArrayList<>();list3.add(1);list3.add(2);list3.add(3);for(Integer integer: list3){System.out.print(integer+" ");}}打印结果：1 2 3

3.4.4 迭代器遍历

 public static void main(String[] args) {ArrayList<Integer> list3=new ArrayList<>();list3.add(1);list3.add(2);list3.add(3);Iterator<Integer> it=list3.iterator();while(it.hasNext()){System.out.print(it.next()+" ");}System.out.println();ListIterator<Integer> it2=list3.listIterator(list3.size());while(it2.hasPrevious()){  //倒着打印System.out.print(it2.previous()+" ");}System.out.println();ListIterator<Integer> it3=list3.listIterator(1);while(it3.hasNext()){   //从指定位置打印System.out.print(it3.next()+" ");}}打印结果：
1 2 3 
3 2 1 
2 3

注意：

  • ListIterator类 实际上继承了 Iterator类，扩展了Iterator类中的方法，新增hasPrevious（）和Previous（）等方法，且在调用ListIterator（）可传入参数，从特定位置进行打印
  • 原理：Arraylist中重写了literable接口中iterator（）方法（），返回值是Iterator接口的对象（Iterator接口没有继承接口），通过这个对象可以调用各种方法进行遍历
  • ArrayList的扩容机制是扩1.5倍
http://www.xdnf.cn/news/2262.html

相关文章：

  • 系统架构设计中的ATAM方法：理论、实践与深度剖析
  • TRO再添新案 TME再拿下一热门IP，涉及Paddington多个商标
  • 冯·诺依曼与哈佛架构CPU的时序对比
  • Xilinx FPGA支持的FLASH型号汇总
  • Tortoise-ORM级联查询与预加载性能优化
  • 浅谈Java 内存管理：栈与堆，垃圾回收
  • Docker中修改OpenJDK 17 TLS禁用算法
  • Debian12.8如何部署Ragflow
  • 计算机网络 | 应用层（4）--DNS：因特网的目录服务
  • Tauri快速入门1 - 搭设开发环境
  • HTML与安全性：XSS、防御与最佳实践
  • Linux系统编程之内存映射
  • 深入浅出理解并应用自然语言处理（NLP）中的 Transformer 模型
  • 【Pandas】pandas DataFrame rdiv
  • 第6讲：科学配色基础——认识颜色空间（RGB、HSV、HCL）
  • AI图像编辑器 Luminar Neo 便携版 Win1.24.0.14794
  • Tableau 基础表制作
  • Java在云计算、大数据、云原生下的应用和优势 - 面试实战
  • 使用 OpenCV 进行视觉图片调整的几种常见方法
  • 碰一碰发视频源码搭建全解析，支持OEM
  • Ubuntu下安装vsode+qt搭建开发框架(二)
  • STM32 开发 - stm32f10x.h 头文件（内存映射、寄存器结构体与宏、寄存器位定义、实现点灯案例）
  • i18n-ai-translate开源程序，可以使用DeepSeek等模型将您的 i18nJSON翻译成任何语言
  • stm32之EXIT外部中断详解
  • (done) 吴恩达版提示词工程 5. 推理 (情绪分类，控制输出格式，输出 JSON，集成多个任务，文本主题推断和索引，主题内容提醒)
  • 基于Spring AI Alibaba + Spring Boot + Ollama搭建本地AI对话机器人API
  • JAVA服务内存缓慢上涨，年轻代GC正常但Full GC频繁，如何定位？
  • IntelliJ IDEA修改实体类成员变量的名称（引入了该实体类的全部文件也会自动更新变量的名称）
  • 精益数据分析（25/126）：关键指标驱动业务发展
  • GPT系列模型-20250426