网站建设 事项,任丘网站开发建设怎么选,易思espcms企业网站管理系统,网站关键词快排名文章目录 什么是List常见接口介绍线性表顺序表顺序表接口的实现add在末尾新增元素在 pos 位置新增元素判定是否包含某个元素查找某个元素对应的位置获取 pos 位置的元素给 pos 位置的元素设为 value删除第一次出现的关键字key获取顺序表的长度清空顺序表 顺序表的优缺点优点缺点 总结 什么是List
在集合框架中List是一个接口继承自Collection。 Collection也是一个接口该接口中规范了后序容器中常用的一些方法具体如下所示 Iterable也是一个接口表示实现该接口的类是可以逐个元素进行遍历的具体如下 List 的官方文档
站在数据结构的角度来看List就是一个线性表即n个具有相同类型元素的有限序列在该序列上可以执行增删改查以及变量等操作。
常见接口介绍
List中提供了好的方法具体如下 虽然方法比较多但是常用方法如下 注意List是个接口并不能直接用来实例化
线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列…
线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储
顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。
在数组上完成数据的增删查改。
顺序表接口的实现
我们现在有这样一个SepList接口为
public interface SepList {// 新增元素,默认在数组最后新增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 key);// 获取顺序表长度int size();// 清空顺序表void clear();
}这里博主将在一个MyArrayList类里面实现这些接口
public class MyArrayList implements SepList {private int[] elem;//数组private int usedSize;//记录有效的数据的个数private static final int DEFAULT_SIZE 10;//最初的数据容量public MyArrayList() {this.elem new int[DEFAULT_SIZE];}// 新增元素,默认在数组最后新增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 key) { }// 获取顺序表长度public int size() { return 0; }// 清空顺序表public void clear() { }
}add在末尾新增元素
在增加一个元素前我们需要对该顺序表进行判断判断是否已满若满则需要进行扩容
每增加一个元素我们我们记录有效个数的usedSize加1
// 新增元素,默认在数组最后新增public void add(int data) {//判断数组是否已经被装满if(usedSize this.elem.length) {//被装满后需要进行扩容this.elem Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[this.usedSize] data;usedSize;}在 pos 位置新增元素
在增加一个元素前我们需要对该顺序表进行判断判断是否已满若满则需要进行扩容
我们还需要多pos进行一个判断判断它是否合法如果不合法我们抛出异常进行提醒
在pos位置增加元素需要将pos位置及以后的元素进行后移一位然后再在pos位置新增元素
每增加一个元素我们我们记录有效个数的usedSize加1
//自定义异常
class PosWrongfulException extends RuntimeException {public PosWrongfulException(String message) {super(message);}
}// 在 pos 位置新增元素public void add(int pos, int data) throws PosWrongfulException {//判断数组是否已经被转满if(usedSize this.elem.length) {//被装满后需要进行扩容this.elem Arrays.copyOf(this.elem,2*this.elem.length);}if(pos 0 || pos this.usedSize) {System.out.println(pos位置不合法);throw new PosWrongfulException(pos位置不合法);}for(int i this.usedSize;i pos;i--) {//pos位置以及pos位置以后的数据整体进行后移this.elem[i] this.elem[i-1];}this.elem[pos] data;usedSize;}判定是否包含某个元素
遍历即可
// 判定是否包含某个元素public boolean contains(int toFind) {for(int i 0;i this.usedSize;i) {if(this.elem[i] toFind) {return true;}}return false;}查找某个元素对应的位置
对数组进行遍历有的话返回相应的数组下标就好没有返回-1
// 查找某个元素对应的位置public int indexOf(int toFind) {for(int i 0;i this.usedSize;i) {if(this.elem[i] toFind) {return i;}}return -1;}获取 pos 位置的元素
获取前我们得进行判断该顺序表类元素不能为空
我们还得对pos进行是否合法得判断
//自定义的异常
class PosWrongfulException extends RuntimeException {public PosWrongfulException(String message) {super(message);}
}
class EmptyException extends RuntimeException {public EmptyException(String message) {super(message);}
}// 获取 pos 位置的元素public int get(int pos)throws PosWrongfulException {if(this.usedSize 0){throw new EmptyException(当前顺序表为空);}if(pos 0 || pos this.usedSize) {System.out.println(pos位置不合法);throw new PosWrongfulException(pos位置不合法);}return this.elem[pos];}给 pos 位置的元素设为 value
我们依旧需要判断pos的合法性前面已经自定义了该异常这里就不再进行定义了
然后将pos位置的元素改为value就好
// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) {if(pos 0 || pos this.usedSize) {System.out.println(pos位置不合法);throw new PosWrongfulException(pos位置不合法);}this.elem[pos] value;}删除第一次出现的关键字key
我们依旧需要判断数组是否为空
遍历数组若没有我们要删除的元素我们便进行提示后退出
若有则只需要用后面的数据对前面进行覆盖就好 //删除第一次出现的关键字keypublic void remove(int key) {if(this.usedSize 0) {throw new EmptyException(顺序表为空);}int index this.indexOf(key);if(index -1) {System.out.println(没有这个数字);return;}//进行覆盖for (int i index; i size()-1; i) {this.elem[i] this.elem[i1];}//如果不是基本类型将usedSize下标置为空//this.elem[this.usedSize] null;this.usedSize--;}获取顺序表的长度
这个就非常简单了只需要返回usedSize就好 // 获取顺序表长度public int size() { return this.usedSize;}清空顺序表
对于当前基本类型的数据来说只需要将usedSize置为0就好 public void clear() {this.usedSize0;}顺序表的优缺点
线性表的顺序存储结构在存、读数据时不管是哪个位置时间复杂度都是O(1)而插入或删除时时间复杂度都是O(n)。这就说明它比较适合元素个数不太变化而更多是存取数据的应用。当然它的优缺点还不只这些……
优点
无需为表示表中元素之间的逻辑关系而增加额外的存储空间可以快速地存取表中任一位置的元素
缺点
插入删除操作需要移动大量元素当线性表长度变化较大时难以确定存储空间的容量造成存储空间的碎片
总结
关于《【数据结构】 List与顺序表及接口的实现》就讲解到这儿感谢大家的支持欢迎各位留言交流以及批评指正如果文章对您有帮助或者觉得作者写的还不错可以点一下关注点赞收藏支持一下
