Java Collection(1)——List——ArrayList(顺序表)LinkedList(链表)

server/2025/3/13 7:18:43/

一.认识List

1.什么是List？

List是Java标准库中的一个接口，下面是List和其他接口/类的关系图
在这里插入图片描述

2.List常用方法简介

1.boolean add(E e)
在这里插入图片描述
2.void add(int index, E element)
在这里插入图片描述
3.E remove(int index)
在这里插入图片描述
4.boolean remove(Object o)
在这里插入图片描述

5.E get(int index)
在这里插入图片描述
6.E set(int index, E element)
在这里插入图片描述
7.void clear()
在这里插入图片描述
8.boolean contains(Object o)
在这里插入图片描述
9.int indexOf(Object o)
在这里插入图片描述
10.int lastIndexOf(Object o)
在这里插入图片描述
11.List< E > subList(int fromIndex, int toIndex)
在这里插入图片描述
因为List是接口，不能直接实例化对象，所以以上的方法只能通过实现List的类的对象来调用，这里只是了解，后面会模拟实现上面的方法

二.ArrayList(顺序表)

1.什么是ArrayList？

简介：
ArrayList是Java标准库中的一个类，实现了List接口。顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改
特点：

  1.  动态大小：

  2.  快速随机访问：通过下标访问元素，时间复杂度是O(1)

  3.  存储任意类型的数据：支持存储任意类型的数据，包括基本数据类型(自动装箱)

  4.  线程不安全：Vector(使用了synchronized)可以看作是ArrayList的线程安全版本，线程安全问题看我相关的博文

2.模拟实现ArrayList

1.创建ArrayList
实际上就是创建一个数组
在这里插入图片描述
2.添加元素
在这里插入图片描述
3.在pos位置添加元素
在这里插入图片描述
4.判断某元素是否存在
在这里插入图片描述
5.找到目标元素下标
在这里插入图片描述
6.判断输入下标是否合法
在这里插入图片描述
7.获取pos位置的元素
在这里插入图片描述
8.将pos位置元素改为value
在这里插入图片描述
9.删除第一次出现的目标元素
在这里插入图片描述
10.清空顺序表
在这里插入图片描述

3.模拟实现的ArrayList的源码

java">class MyArrayList<T>{private int[] array;private int usedSize;private static final int DefaultSize = 2;//无参构造方法public MyArrayList(){this.array = new int[DefaultSize];}//有参构造方法public MyArrayList(int initCapacity){this.array = new int[initCapacity];}//打印public void show(){for (int i = 0; i < this.usedSize; i++) {System.out.print(this.array[i]+" ");}System.out.println();}//判断是否满了public Boolean isFull(){if (this.array.length == this.usedSize)return true;elsereturn false;}//从最后一个位置添加元素public void add(int data){if (isFull()){this.array = Arrays.copyOf(this.array,this.array.length*2);}this.array[this.usedSize] = data;this.usedSize++;}//在pos位置添加元素public void add(int pos,int data){if (pos < 0 || pos > this.usedSize)throw new exception(pos+"位置不合法");if (isFull()){this.array = Arrays.copyOf(this.array,this.array.length*2);}for (int i = this.usedSize-1; i >= pos ; i--) {this.array[i+1] = this.array[i];}this.array[pos] = data;this.usedSize++;}//判断某元素是否存在public boolean contains(int find){for (int i = 0; i < this.usedSize; i++) {if (this.array[i] == find){return true;}}return false;}//找到目标元素下标public int indexOf(int find){for (int i = 0; i < this.usedSize; i++) {if (this.array[i] == find){return i;}}return -1;}//判断输入下标是否合法public  Boolean check(int pos){if (pos < 0 || pos > this.usedSize - 1){return false;}return true;}//获取pos位置的元素public int get(int pos){if (!check(pos)){throw new exception(pos+"位置不合法");}return this.array[pos];}//将pos位置元素改为valuepublic void set(int pos,int value){if (!check(pos)){throw new exception(pos+"位置不合法");}this.array[pos] = value;}//删除第一次出现的目标元素public void del(int toDel){int dex = indexOf(toDel);if (dex == -1){System.out.println("没有要删除的元素");return;}for (int i = dex; i < this.usedSize-1; i++) {this.array[i] = this.array[i+1];}//引用类型/*this.array[usedSize-1] = null;*/this.usedSize--;}//获取顺序表长度public int size(){return this.usedSize;}//清空顺序表public void clear(){//引用类型/*for (int i = 0; i < this.usedSize; i++) {this.array[i] = null;}*/this.usedSize = 0;}
}

三.LinkedList(链表)

1.什么是线性表？

简介：
线性表是n个具有相同特性的数据元素的有限序列，线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的空间(如下图)
在这里插入图片描述
每个节点有两个域，一个存放数据/值(value)，一个存放下一个节点的地址(address)。通过上一个节点能够找到下一个节点，而且这些节点在物理结构上不一定是连续的，这就叫做线性表/链表。

2.链表的分类

从方向上来讲有三种类型

  1.  单向链表(如上图)：每个节点只有一个指向下一个节点的指针，最后一个节点的指针指向null。单向链表只能从头到尾进行遍历

  2.  双向链表：每个节点有两个指针，一个指向前一个节点，一个指向下一个节点。双向链表可以从任意一个节点开始，向前或向后进行遍历

  3.  循环链表：链表的最后一个节点指向头节点，形成一个环。循环链表可以是单向的，也可以是双向的

从头节点的区别来讲有两个类型

  1.  带头链表：带头链表是指在链表的第一个节点之前增加一个特殊的节点，称为头结点。这个头结点通常不存储实际的数据，仅作为链表的起始点

  2.  不带头链表(如上图)：链表中所有节点的结构是一致的，第一个节点是不确定的(后面讲到头插法就明白了)

通过以上排列组合，一共可以得到六种类型的链表

  1.  单向带头链表

  2.  单向不带头链表

  3.  双向带头链表

  4.  双向不带头链表

  5.  循环带头链表

  6.  循环不带头链表

本文主要介绍单向不带头链表，只要搞清楚这一个类型的原理，其他类型都是同理

3.单向不带头链表模拟实现

1.创建链表
在这里插入图片描述
2.求链表长度
在这里插入图片描述
3.头插法
在这里插入图片描述

4.尾插法
在这里插入图片描述
头插法不需要判断当前链表是否为空，但是尾插法需要
因为不论链表是否为空，头插法不会触发空指针异常；但当链表为空时，尾插法如果不进行判断，就会触发空指针异常
5.在pos位置添加元素
在这里插入图片描述
6.删除出现的第一个key目标
在这里插入图片描述
7.删除出现的所有key目标
在这里插入图片描述
8.清空链表
在这里插入图片描述

4.模拟实现的单向链表源码

java">public class MySingleList {//内部类static class ListNode{public int val;public ListNode next;public ListNode(int val){this.val = val;}}//private ListNode head;//创建链表public void createList(){ListNode node1 = new ListNode(1);ListNode node2 = new ListNode(2);ListNode node3 = new ListNode(3);ListNode node4 = new ListNode(4);ListNode node5 = new ListNode(5);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}//打印链表public void disPlay(){ListNode cur = head;if (head == null){System.out.println("链表为空");return;}while (cur != null){System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}//求链表长度public int getSize(){int count = 0;ListNode cur = head;while (cur != null){cur = cur.next;count++;}return count;}//查找keypublic Boolean contains(int key){ListNode cur = head;while (cur != null){if (cur.val == key){return true;}cur = cur.next;}return false;}//头插法public void addFirst(int data){ListNode node = new ListNode(data);node.next = head;head = node;}//尾插法public void addLast(int data){ListNode node = new ListNode(data);ListNode cur = head;if (cur == null){head = node;return;}while (cur.next != null){cur = cur.next;}cur.next = node;}//在pos位置添加元素,第一个节点下标为0,假如输入pos=2,那么该节点插入后就是链表的第2个节点public void addPos(int pos,int data){if (pos < 0 || pos > getSize()){System.out.println("插入位置不合法");return;}//pos == 0,直接使用头插法if(pos == 0){addFirst(data);return;}//pos == getSize(),使用尾插法if (pos == getSize()){addLast(data);return;}ListNode cur = toFindAddPosSubOne(pos);ListNode node = new ListNode(data);if (cur != null) {node.next = cur.next;cur.next = node;}}//第一个节点下标为0,找到pos下标的前一个节点,并且返回该节点的地址private ListNode toFindAddPosSubOne(int pos){if (pos < 0 || pos > getSize()){System.out.println("输入的位置不合法");return null;}ListNode cur = head;while ( pos - 1 != 0){cur = cur.next;pos--;}return cur;}//删除出现的第一个key目标public void delFirstKey(int key){if(head == null){System.out.println("链表为空");return;}if (head.val == key){head = head.next;}ListNode cur = toFindDel(key);if (cur == null){System.out.println("没有你要删除的数字");return;}cur.next = cur.next.next;}//找到要删除节点的前一个节点private ListNode toFindDel(int key){ListNode cur = head;while (cur != null){if (cur.next.val == key){return cur;}cur = cur.next;}return null;}//删除出现的所有key目标public void delAllKey(int key){if(head == null){System.out.println("链表为空");return;}while (head.val == key){head = head.next;}ListNode cur = head;ListNode del = cur.next;int count = 0;while (del != null){if (del.val != key){del = del.next;cur = cur.next;}else {cur.next = del.next;del = del.next;count++;}}if (count == 0){System.out.println("没有你要删除的数字");}}//清空链表public void clear(){head = null;}
}

四.顺序表VS链表

存储方式

  1.  顺序表：使用连续的内存空间存储元素

  2.  链表：使用非连续的内存空间存储元素

访问方式

  1.  顺序表：支持随机访问，通过下标/索引在O(1)时间内访问

  2.  链表：不支持随机访问，通过遍历链表访问元素(O(n)时间复杂度)

删除和插入

  1.  顺序表：需要移动大量元素，例如：删除下标为2的元素，后面的元素都需要向前覆盖

  2.  链表：头插法/尾插法，删除头/尾节点时间复杂度是O(1),虽然其他位置的插入和删除时间复杂度也是O(n)，但不需要大量地移动元素

容量

  1.  顺序表：自动扩容

  2.  链表：没有容量这个概念

适用场景

  1.  顺序表：元素高效存储+频繁访问

  2.  链表：任意位置插入和删除频繁

http://www.ppmy.cn/server/174576.html

相关文章

C#中常量详解

C#中常量详解

一、定义与特点‌ 1‌.核心定义‌ 常量是使用 const 关键字声明的不可变值&#xff0c;其值在‌编译时确定‌且在程序生命周期内不可修改‌。与变量不同&#xff0c;常量必须在声明时初始化&#xff0c;且后续无法重新赋值‌。 2‌.主要用途‌ 表示程序中固定不变的值&…
阅读更多...
0312-PromptMRG：诊断驱动的医疗报告生成提示

0312-PromptMRG：诊断驱动的医疗报告生成提示

1&#xff0c;摘要&#xff1a; 提出了诊断驱动的医疗报告生成提示(PromptMRG)&#xff0c;这是一个新的框架&#xff0c;旨在通过诊断感知提示的指导提高MRG的诊断准确性。具体来说&#xff0c;PromptMRG是基于编码器-解码器架构&#xff0c;并带有一个额外的疾病分类分支。在…
阅读更多...
安卓应用架构模式 MVC MVP MVVM有什么区别？

安卓应用架构模式 MVC MVP MVVM有什么区别？

在 Android 开发中&#xff0c;MVC、MVP 和 MVVM 是三种常见的架构模式&#xff0c;它们的目标都是通过分层解耦代码&#xff0c;提升可维护性和可测试性。以下是它们的核心区别和实际应用对比&#xff1a; 1. 核心职责划分 架构模式分层结构各层职责MVCModel-View-Controlle…
阅读更多...
SVN 拉取，文件冲突 解决办法

SVN 拉取，文件冲突 解决办法

情景 svn 在拉取代码时 提示 已跳过&#xff0c;其余有冲突 &#xff0c;警告至少还有一个的文件处于冲突状态 导致文件拉取失败 一、原因 版本库和本地工作副本之间存在文件冲突&#xff0c;导致文件无法正常拉取。 二、 Terminal 窗口解决办法 1.查看冲突文件 在 Termin…
阅读更多...
关于AI数据分析可行性的初步评估

关于AI数据分析可行性的初步评估

一、结论&#xff1a;可在部分环节嵌入&#xff0c;无法直接处理大量数据 1.非本地部署的AI应用处理非机密文件没问题&#xff0c;内部文件要注意数据安全风险。 2.AI&#xff08;指高规格大模型&#xff09;十分适合探索性研究分析&#xff0c;对复杂报告无法全流程执行&…
阅读更多...
已安装 MFC 仍提示“此项目需要 MFC 库”的解决方法 (MSB8041)

已安装 MFC 仍提示“此项目需要 MFC 库”的解决方法 (MSB8041)

编译报错信息表明项目需要 MFC 库&#xff0c;但 Visual Studio 无法找到。尽管你已确认安装了 MFC&#xff0c;问题仍然存在&#xff0c;这通常是由于环境中存在多个 MSVC 版本造成的冲突。 问题描述&#xff1a; 编译时出现错误&#xff1a;error MSB8041: 此项目需要 MFC …
阅读更多...
【WRF模拟】如何查看 WPS 的输入静态地理数据（二进制格式）？

【WRF模拟】如何查看 WPS 的输入静态地理数据（二进制格式）？

查看 WPS 的输入静态地理数据方法总结 方法 1：使用 gdal_translate 将二进制数据转换为 GeoTIFFgdal_translate 工具概述使用 gdal_translate 将二进制数据转换为 GeoTIFF方法 2：使用 ncdump 查看 geo_em.dXX.nc方法 3：使用 Python xarray + matplotlib 可视化 geo_em.dXX.n…
阅读更多...
halcon机器人视觉(四)calibrate_hand_eye_stationary_3d_sensor

halcon机器人视觉(四)calibrate_hand_eye_stationary_3d_sensor

目录 一、准备数据和模型二、按照表面匹配的的结果进行手眼标定三、根据标定结果计算CalObjInCamPose 一、准备数据和模型 1、读3D模型&#xff1a;read_object_model_3d 2、创建表面匹配模板&#xff1a;create_surface_model 3、创建一个HALCON校准数据模型&#xff1a;crea…
阅读更多...
最新文章

Copyright @ 2022~2023