php网站前后台源代码,音乐门户网站模板,中国国家人才培训网官网,产品外观设计报价一、顺序表概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构#xff0c;一般情况下采用数组存储。在数组上完成数据的增删查改。
二、主要功能接口实现
Java顺序表底层就是一个动态数组。其主要功能接口如下#xff1a;
// 1.打印顺序表#xff0…一、顺序表概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
二、主要功能接口实现
Java顺序表底层就是一个动态数组。其主要功能接口如下
// 1.打印顺序表注意该方法并不是顺序表中的方法为了方便看测试结果给出的
public void display() { }
// 2.新增元素,默认在数组最后新增
public void add(int data) { }
// 3.判断当前的顺序表是不是满的
public boolean isFull() { }
// 4.在 pos 位置新增元素
public void add(int pos, int data) { }
// 5.判定是否包含某个元素
public boolean contains(int toFind) { return true; }
// 6.查找某个元素对应的位置
public int indexOf(int toFind) { return -1; }
// 7.获取 pos 位置的元素
public int get(int pos) { return -1; }
// 8.给 pos 位置的元素设为 value
public void set(int pos, int value) { }
// 9.删除第一次出现的关键字 key
public void remove(int toRemove) { }
// 10.获取顺序表长度
public int size() { return 0; }
// 11.清空顺序表
public void clear() { }下面我们对应上面的功能接口自己实现一下顺序表由于这部分比较简单这里就直接给出代码大家可结合注释参考。另外此处侧重于流程实现使用了更好理解的int类型并未使用泛型
import java.util.Arrays;
public class MyArraylist {public int[] elem;// 已使用容量初始为0public int usedSize;// 默认容量private static final int DEFAULT_SIZE 5;// 这里采用无参的构造方法public MyArraylist() {this.elem new int[DEFAULT_SIZE];}/*** 1.打印顺序表 * 注意该方法并不是顺序表中的方法为了方便看测试结果给出的* 根据usedSize判断即可*/public void display() {for (int i 0; i this.usedSize; i) {System.out.print(this.elem[i] );}}/*** 2.新增元素,默认尾插*/ public void add(int data) {if (isFull()) {resize();}this.elem[this.usedSize] data;this.usedSize;}// 扩容private void resize() {this.elem Arrays.copyOf(this.elem, 2 * this.elem.length);}// 检查坐标合法性private void checkPosInAdd(int pos) {if (pos 0 || pos this.usedSize) {// 这里自定义异常类throw new IndexException(位置不合法请检查位置的合法性);}}/*** 3.判断当前的顺序表是不是满的*/public boolean isFull() {return this.usedSize this.elem.length;}/*** 4.在 pos 位置新增元素*/public void add(int pos, int data) {if (isFull()) {resize();}checkPosInAdd(pos);for (int i this.usedSize; i pos; i--) {this.elem[i] this.elem[i - 1];}this.elem[pos] data;this.usedSize;}/*** 5.判定是否包含某个元素*/public boolean contains(int toFind) {for (int i 0; i this.usedSize; i) {if (this.elem[i] toFind) {return true;}}return false;}/*** 6.查找某个元素对应的位置*/public int indexOf(int toFind) {for (int i 0; i this.usedSize; i) {if (this.elem[i] toFind) {return i;}}return -1;}/*** 7.获取 pos 位置的元素*/public int get(int pos) {checkPosInAdd(pos);return this.elem[pos];}// 判空private boolean isEmpty() {if (this.usedSize 0) {return true;}return false;}/*** 8.将 pos 位置的元素设为修改为 value*/public void set(int pos, int value) {checkPosInAdd(pos);this.elem[pos] value;}/*** 9.删除第一次出现的关键字key*/public boolean remove(int key) {int index indexOf(key);if (index -1) {System.out.println(不存在关键字 key);return false;}for (int j index; j this.usedSize - 1; j) {this.elem[j] this.elem[j 1];}this.usedSize--;//注意是在这条语句之后//elem[usedSize] null;// 如果里面是引用类型 那么此时就需要手动置空elem[usedSize] 0;return true;}/*** 10.获取顺序表长度*/ public int size() {return this.usedSize;}/*** 11.清空顺序表*/ public void clear() {this.usedSize 0;}
}上述过程中自定义的异常类
public class IndexException extends RuntimeException {// 帮助父类构造IndexException() {super();}IndexException(String msg) {super(msg);}
}三、Java集合框架中的 ArrayList
在 java.util 包下为我们提供了一个ArrayList类ArrayList底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表且这里的 ArrayList 是以泛型方式实现的使用时必须要先实例化。此外在Java中还对ArrayList有以下这些说明现阶段不做解释大家可以暂时了解即可 ArrayList实现了RandomAccess接口表明ArrayList支持随机访问ArrayList实现了Cloneable接口表明ArrayList是可以clone的ArrayList实现了Serializable接口表明ArrayList是支持序列化的和Vector不同ArrayList不是线程安全的在单线程下可以使用在多线程中可以选择Vector或者 CopyOnWriteArrayList 1、ArrayList的构造方法
方法解释ArrayList()无参构造ArrayList(Collection? extends E c)利用其他 Collection 构建 ArrayListArrayList(int initialCapacity)指定顺序表初始容量
解释 对于无参构造方法ArrayList()在实例化ArrayList对象时不会分配内存在add()方法中才进行内存分配。对于ArrayList(Collection? extends E c)表示可以将实现了Collection接口、并且是E类型或E类型的子类的集合作为参数构造ArrayList。相比之下ArrayList(int initialCapacity)就比较好理解了这个构造方法是在实例化ArrayList对象时分配指定initialCapacity大小的容量。 2、ArrayList常用方法
与此同时ArrayList下为我们提供了大量的方法其中常见操作方法如下
方法解释boolean add(E e)尾插 evoid add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection? extends E c)尾插 c 中的元素E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一个 oE get(int index)获取下标 index 位置元素E set(int index, E element)将下标 index 位置元素设置为 elementvoid clear()清空boolean isEmpty()如果此列表不包含元素则返回 trueint size()返回此列表中的元素数boolean contains(Object o)判断 o 是否在线性表中int indexOf(Object o)返回第一个 o 所在下标int lastIndexOf(Object o)返回最后一个 o 的下标List subList(int fromIndex, int toIndex)截取部分 list
3、ArrayList 的继承关系
在《Java集合框架中》我们介绍了Java集合中的继承关系你是否还有印象ArrayList实现了List接口 对于List接口来说里面涵盖了ArrayList中的方法也就是说我们可以使用 List 接口对 ArrayList 实例进行操作因此我们可以写出类似这种调用方式ListInteger list new Arraylist(); 将ArrayList实例交给List接口然后直接使用list进行相关操作。
public class OperateTest {public static void main(String[] args) {ListInteger list new ArrayList();list.add(111);list.add(222);list.add(333);list.add(444);list.add(555);System.out.println(list);// 设定list2-[1,2,3] 便于测试addAll()ListInteger list2 new ArrayList();list2.add(1);list2.add(2);list2.add(3);// 末尾插入list2list.addAll(list2);System.out.println(list);// 获取list中有效元素个数System.out.println(list.size());// 获取和设置index位置上的元素注意index必须介于[0, size)间System.out.println(list.get(0));list.set(0, 999);System.out.println(list.get(0));// 在list的index位置插入指定元素index及后续的元素统一往后搬移一个位置list.add(1, 888);System.out.println(list);// 删除指定元素找到了就删除该元素之后的元素统一往前搬移一个位置// (这里如果直接写444会默认下标需要使用引用类型)list.remove(new Integer(444));System.out.println(list);// 删除list中index位置上的元素注意index不要超过list中有效元素个数,否则会抛出下标越界异常list.remove(list.size()-1);System.out.println(list);// 检测list中是否包含指定元素包含返回true否则返回falseif(!list.contains(123456)){list.add(123456);System.out.println(list);}// 查找指定元素第一次出现的位置indexOf从前往后找lastIndexOf从后往前找System.out.println(list.indexOf(333));System.out.println(list.lastIndexOf(333));// 使用list中[0, 4)之间的元素构成一个新的SubList返回,// 但是和ArrayList共用一个elementData数组(对任一部分修改会影响整个部分)ListInteger ret list.subList(0, 2);System.out.println(ret);// 清空list.clear();System.out.println(list.size());}
}4、ArrayList的遍历
1 方式一 使用for循环下标遍历
for (int i 0; i list.size(); i) {System.out.println(list.get(i));
}2 方式二 由于List、Arraylist集合实现了iterable接口可以使用增强的for循环-foreach
for (Integer x:list) {System.out.println(x);
}3 方式三 对于Java而言只要实现了Iterable接口的集合就可以使用迭代器 iterator
IteratorInteger it list.listIterator();
while(it.hasNext()){System.out.println(it.next());
}总结
本篇文章主要介绍了 Java 集合中的线性结构 ArrayList 这是一个相对比较简单且容易理解和实现的数据结构。这里就简单总结一下顺序表 ArrayList的优缺点
顺序表缺点 ArrayList底层使用连续的空间任意位置插入或删除元素时需要将该位置后序元素整体往前或者往后搬移故时间复杂度为O(N)增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。增容一般是呈倍数增长。假如以2倍扩容势必会有一定的空间浪费例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 顺序表优点 当给定下标的时候查找速度非常快复杂度为O(1)
