List、ArrayList与顺序表1

embedded/2024/11/19 15:35:57/

文章目录

  • 1. 什么是List
  • 2. 常见接口
  • 3. List的使用
  • 4. 线性表
  • 5. 顺序表
  • 5.1 接口的实现

1. 什么是List

在这里插入图片描述
在集合框架中，List是一个接口，继承与Collection接口，也继承于Iterable接口。

Collection接口中主要规范了后序容器中常用的一些方法
在这里插入图片描述
Iterable接口表示实现该接口的类是可以逐个元素进行遍历的
在这里插入图片描述
但是站在数据结构的角度来看，List是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

2. 常见接口

常用方法如下

方法解释
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 的下标
ListsubList( int fromIndex,int toIndex )截取部分List

3. List的使用

注意：List只是个接口，并不能直接用来实例化。

如下图所示，集合框架中，ArrayList 和 LinkedList 都实现了 List 接口，我们可以实例化 ArrayList 和 LinkedList 。（下面就会学习）
在这里插入图片描述

4. 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。常见的线性表：顺序表、链表、栈、队列。

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述

5. 顺序表

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

5.1 接口的实现

java">public interface IList {// 新增元素,默认在数组最后新增void add(int data);// 在 pos 位置新增元素void add(int pos, int data);// 判定是否包含某个元素boolean contains(int toFind);// 查找某个元素对应的位置int indexOf(int toFind);// 获取 pos 位置的元素int get(int pos);// 给 pos 位置的元素设为 value -> 更新void set(int pos, int value);//删除第一次出现的关键字keyvoid remove(int toRemove);// 获取顺序表长度int size();// 清空顺序表void clear();// 打印顺序表，// 注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的void display();boolean isFull();
}

现在让我们根据上述接口来自己实现一个顺序表
1. 打印顺序表 （遍历即可）

java">@Overridepublic void display() {for (int i = 0; i < usedSize; i++) {System.out.print(array[i] + " ");}System.out.println();}

2. 新增元素,默认在数组最后新增

  • 在新增元素之前，我们要判断顺序表是否满了，如果满了将无法新增，我们可以使用扩容的方法使其新增成功。
  • 不要忘记当前长度要加一，usedSize++
  • 将 isFull 方法也写入接口当中
  • 先重写 isFull 方法
java">@Overridepublic boolean isFull() {return usedSize == array.length;}
  • 重写 add 方法
java">//新增元素,默认在数组最后新增@Overridepublic void add(int data) {if(isFull()){array = Arrays.copyOf(array,array.length*2);}this.array[usedSize] = data;usedSize++;}
  1. 在 pos 位置新增元素
  • 首先，应该判断pos 位置是否合法，我们可以使用异常来处理，编写 PosNotLegalException的异常类和checkPosOfAdd 的方法
java">public class PosNotLegalException extends RuntimeException{public PosNotLegalException(){}public PosNotLegalException(String msg){super(msg);}
}

java">private void checkPosOfAdd(int pos) throws PosNotLegalException{if(pos < 0 || pos > usedSize){throw new PosNotLegalException("Add时Pos位置不合法");}}
  • 然后还要判断该顺序表是否满了，满了则扩容
  • 在这里插入图片描述
java">@Overridepublic void add(int pos, int data) {try {checkPosOfAdd(pos);}catch (PosNotLegalException e){e.printStackTrace();}if(isFull()){array = Arrays.copyOf(array,array.length*2);}for (int i = usedSize; i > pos ; i--) {array[i] = array[i - 1];}array[pos] = data;usedSize++;}

4. 判定是否包含某个元素

  • 遍历顺序表，找到返回 true ，没找到返回false
java">@Overridepublic boolean contains(int toFind) {for (int i = 0; i < usedSize; i++) {if(array[i] == toFind ){return true;}}return false;}

5. 查找某个元素对应的位置

  • 遍历顺序表，找到后返回该元素的下标
java">@Overridepublic int indexOf(int toFind) {for (int i = 0; i < usedSize; i++) {if(array[i] == toFind){return i;}}return -1;}

6. 获取 pos 位置的元素

  • 要记得判断 pos 的位置是否合法，写一个方法来判断（get 和 set 方法都能用到）
java">private void checkPosOfGetAndSet(int pos) throws PosNotLegalException{if(pos <0 || pos >= usedSize){throw new PosNotLegalException("get/set时pos不合法");}}

java">@Overridepublic int get(int pos) {try{checkPosOfGetAndSet(pos);}catch (PosNotLegalException e){e.printStackTrace();}return array[pos];}

7. 给 pos 位置的元素设为 value

  • 还是要先判断 pos 位置是否合法
java">@Overridepublic void set(int pos, int value) {try{checkPosOfGetAndSet(pos);}catch (PosNotLegalException e){e.printStackTrace();}array[pos] = value;}

8. 删除第一次出现的关键字key

  • 首先需要找到你想要删除的关键字的下标pos，才能删除，刚好用到我们上面写到的 indexOf 方法
  • 不要忘记判断 pos 是否合法
  • 删除元素
  • 当前长度减一，即 usedSize - 1
    在这里插入图片描述
java">@Overridepublic void remove(int toRemove) {int pos = indexOf(toRemove);if (pos == -1){System.out.println("没有你要删除的数字");return;}for (int i = pos; i < usedSize - 1; i++) {array[i] = array[i + 1];}usedSize--;}

9. 获取顺序表长度

  • 当前 usedSize 的值就是顺序表的长度。
java">public int size() {return usedSize;}

10. 清空顺序表

  • 直接将 usedSize 置为 0 即可，如果该顺序表当中存储的引用类型，那么需要遍历顺序表，将每个下标都指向null
java"> @Overridepublic void clear() {//如果为引用类型/*for (int i = 0; i < usedSize; i++) {array[i] == null;}*/usedSize = 0;}

全部代码如下

java">package project1;public interface IList {// 新增元素,默认在数组最后新增void add(int data);// 在 pos 位置新增元素void add(int pos, int data);// 判定是否包含某个元素boolean contains(int toFind);// 查找某个元素对应的位置int indexOf(int toFind);// 获取 pos 位置的元素int get(int pos);// 给 pos 位置的元素设为 valuevoid set(int pos, int value);//删除第一次出现的关键字keyvoid remove(int toRemove);// 获取顺序表长度int size();// 清空顺序表void clear();// 打印顺序表，void display();boolean isFull();
}package project1;public class PosNotLegalException extends RuntimeException{public PosNotLegalException(){}public PosNotLegalException(String msg){super(msg);}
}package project1;import java.util.Arrays;public class MyArrayList implements IList{private int[] array;private int usedSize;public MyArrayList(){this.array = new int[10];}//新增元素,默认在数组最后新增@Overridepublic void add(int data) {if(isFull()){array = Arrays.copyOf(array,array.length*2);}this.array[usedSize] = data;usedSize++;}private void checkPosOfAdd(int pos) throws PosNotLegalException{if(pos < 0 || pos > usedSize){throw new PosNotLegalException("Add时Pos位置不合法");}}@Overridepublic void add(int pos, int data) {try {checkPosOfAdd(pos);}catch (PosNotLegalException e){e.printStackTrace();}if(isFull()){array = Arrays.copyOf(array,array.length*2);}for (int i = usedSize; i > pos ; i--) {array[i] = array[i - 1];}array[pos] = data;usedSize++;}@Overridepublic boolean contains(int toFind) {for (int i = 0; i < usedSize; i++) {if(array[i] == toFind ){return true;}}return false;}@Overridepublic int indexOf(int toFind) {for (int i = 0; i < usedSize; i++) {if(array[i] == toFind){return i;}}return -1;}private void checkPosOfGetAndSet(int pos) throws PosNotLegalException{if(pos <0 || pos >= usedSize){throw new PosNotLegalException("get/set时pos不合法");}}@Overridepublic int get(int pos) {try{checkPosOfGetAndSet(pos);}catch (PosNotLegalException e){e.printStackTrace();}return array[pos];}@Overridepublic void set(int pos, int value) {try{checkPosOfGetAndSet(pos);}catch (PosNotLegalException e){e.printStackTrace();}array[pos] = value;}@Overridepublic void remove(int toRemove) {int pos = indexOf(toRemove);if (pos == -1){System.out.println("没有你要删除的数字");return;}for (int i = pos; i < usedSize - 1; i++) {array[i] = array[i + 1];}usedSize--;}@Overridepublic int size() {return usedSize;}@Overridepublic void clear() {//如果为引用类型/*for (int i = 0; i < usedSize; i++) {array[i] == null;}*/usedSize = 0;}@Overridepublic void display() {for (int i = 0; i < usedSize; i++) {System.out.print(array[i] + " ");}System.out.println();}@Overridepublic boolean isFull() {return usedSize == array.length;}
}package project1;import java.util.List;public class Test {public static void main(String[] args) {IList iList = new MyArrayList();iList.add(1);iList.add(2);iList.add(3);iList.add(4);iList.add(5);iList.add(2,6);boolean flag1 = iList.contains(6);System.out.println(flag1);iList.remove(6);boolean flag2 = iList.contains(6);System.out.println(flag2);//iList.clear();iList.display();}
}

ArrayList 自己也有这些方法，下一篇学习 ArrayList 自己的方法。

写了这么多，我真牛，要好好奖励奖励自己了
在这里插入图片描述


http://www.ppmy.cn/embedded/138798.html

相关文章

css初始化（二十三课）

css初始化（二十三课）

一、把所有标签的内外边距清零 * {padding: 0;margin: 0;} 二、把斜体的文字不倾斜 i,em {font-style: normal;} 三、去掉li标签前面的小圆点 li {list-style: none;} 四、照顾低版本浏览器&#xff0c;实现兼容性 img {border: 0;vertical-align: middle;} 五、鼠标经过按…
阅读更多...
redis的击穿和雪崩

redis的击穿和雪崩

Redis 是一个高性能的键值存储数据库&#xff0c;广泛用于缓存、会话管理等场景。然而&#xff0c;Redis 在高并发场景下可能会遇到一些问题&#xff0c;比如“击穿”和“雪崩”。下面详细解释这两个概念&#xff1a; 击穿&#xff08;Hotspot&#xff09; 击穿是指某个热点数…
阅读更多...
两大新兴开发语言大比拼：Move PK Rust

两大新兴开发语言大比拼：Move PK Rust

了解 Move 和 Rust 的差异有助于开发者根据项目的具体需求选择最合适的语言。选择不恰当的语言可能会导致项目后期出现技术债务。不同语言有其独特的优势。了解 Move 和 Rust 的差异可以帮助开发者拓展技术视野&#xff0c;发现不同语言在不同领域的应用潜力。 咱们直奔主题&a…
阅读更多...
Docker Compose部署Kafka（非Zookeeper​）

Docker Compose部署Kafka（非Zookeeper​）

整个工具的代码都在Gitee或者Github地址内 gitee&#xff1a;solomon-parent: 这个项目主要是总结了工作上遇到的问题以及学习一些框架用于整合例如:rabbitMq、reids、Mqtt、S3协议的文件服务器、mongodb github&#xff1a;GitHub - ZeroNing/solomon-parent: 这个项目主要是…
阅读更多...
Shell脚本2 -- 永久环境变量与字符串操作

Shell脚本2 -- 永久环境变量与字符串操作

声明&#xff1a; 本文的学习内容来源于B站up主“泷羽sec”视频【shell编程&#xff08;2&#xff09;永久环境变量和字符串显位】的公开分享&#xff0c;所有内容仅限于网络安全技术的交流学习&#xff0c;不涉及任何侵犯版权或其他侵权意图。如有任何侵权问题&#xff0c;请联…
阅读更多...
安全见闻6-9

安全见闻6-9

在实际应用中&#xff0c;应结合多种方法进行综合分析&#xff0c;以确保网络系统的安全稳定运行。同时&#xff0c;随着技术不断发展&#xff0c;二进制安全领域也在不断演进&#xff0c;需要持续学习和研究新的技术和方法&#xff0c;以应对不断变化的安全挑战。 安全见闻6 …
阅读更多...
蓝桥杯每日真题 - 第17天

蓝桥杯每日真题 - 第17天

题目&#xff1a;&#xff08;最大数字&#xff09; 题目描述&#xff08;13届 C&C B组D题&#xff09; 题目分析&#xff1a; 操作规则&#xff1a; 1号操作&#xff1a;将数字加1&#xff08;如果该数字为9&#xff0c;变为0&#xff09;。 2号操作&#xff1a;将数字…
阅读更多...
C语言项⽬实践-贪吃蛇

C语言项⽬实践-贪吃蛇

目录 1.项目要点 2.窗口设置 2.1mode命令 2.2title命令 2.3system函数 2.Win32 API 2.1 COORD 2.2 GetStdHandle 2.3 CONSOLE_CURSOR_INFO 2.4 GetConsoleCursorInfo 2.5 SetConsoleCursorInfo 2.5 SetConsoleCursorPosition 2.7 GetAsyncKeyState 3.贪吃蛇游戏设…
阅读更多...
最新文章

Copyright @ 2022~2023