懒人图库网站源码,智能网站建设制作,苏州有什么好玩的地方适合小朋友,网站建设图库1.线性表 线性表#xff08; linear list#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构#xff0c;常见的线性表#xff1a;顺序表、链表、栈、队列... 线性表在逻辑上是线性结构#xff0c;也就说是连续的一条直线。但是在…1.线性表 线性表 linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列... 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。 2. ArrayList 简介 在集合框架中 ArrayList 是一个普通的类实现了 List 接口具体框架图如下 说明 1. ArrayList 是以泛型方式实现的使用时必须要先实例化 2. ArrayList 实现了 RandomAccess 接口表明 ArrayList 支持随机访问 3. ArrayList 实现了 Cloneable 接口表明 ArrayList 是可以 clone 的 4. ArrayList 实现了 Serializable 接口表明 ArrayList 是支持序列化的 5. 和 Vector 不同 ArrayList 不是线程安全的在单线程下可以使用在多线程中可以选择 Vector 或者 CopyOnWriteArrayList 6. ArrayList 底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表 3. ArrayList 的使用 顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 3.1 ArrayList 的构造方法 方法说明 ArrayList() 无参构造 ArrayList (Collection? extends E c) 利用其他 Collection 构建 ArrayList ArrayList (int initialCapacity) 指定顺序表初始容量 代码示例 public static void main(String[] args) {// ArrayList创建推荐写法// 构造一个空的列表ListInteger list new ArrayList();ArrayListInteger a1 new ArrayList();a1.add(1);a1.add(2);a1.add(3);System.out.println(a1);System.out.println();// 构造一个具有10个容量的列表ArrayListInteger a2 new ArrayList(10);a2.add(11);a2.add(22);a2.add(33);System.out.println(a2);System.out.println();// a3构造好之后与a2中的元素一致ArrayListInteger a3 new ArrayList(a2);System.out.println(a3);} 运行结果 注意: 1.List 是一个接口通过list访问的是接口中的方法是常用的构造方法 2.ArrayList的底层逻辑就是一个数组 3. 第一种构造方法虽然没有定义表的容量只是定义了一个数组引用但是Add()方法会对没有容量的表进行定容 4. 第二种构造方法定义了表的容量 5.第三种构造方法是实现了 Collection 接口的并且参数的类型时当前 a3 指定的泛型类型本身 3.2 ArrayList常见操作 ArrayList虽然提供的方法比较多但是常用方法如下所示需要用到其他方法时兄弟们可以自行查看ArrayList的帮助文档。 方法说明 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)删除遇到的第一个 oE get(int index)获取下标 index 位置元素E set(int index, E element)将下标 index 位置元素设置为 elementvoid clear()清空boolean contains(Object o)判断 o 是否在线性表中int indexOf(Object o)返回第一个 o 所在下标int lastIndexOf(Object o)返回最后一个 o 的下标ListE subList(int fromIndex, int toIndex)截取部分 list 代码示例 public static void main(String[] args) {ListString list new ArrayList();list.add(JavaSE);list.add(JavaWeb);list.add(JavaEE);list.add(JVM);list.add(测试课程);System.out.println(list);System.out.println();
// 获取list中有效元素个数System.out.println(size: list.size());System.out.println();
// 获取和设置index位置上的元素注意index必须介于[0, size)间System.out.println(list.get(1));list.set(1, JavaWEB);System.out.println(set and get: list.get(1));System.out.println();
// 在list的index位置插入指定元素index及后续的元素统一往后搬移一个位置list.add(1, Java数据结构);System.out.println(add(index,element)list);System.out.println();
// 删除指定元素找到了就删除该元素之后的元素统一往前搬移一个位置list.remove(JVM);System.out.println(removelist);System.out.println();
// 删除list中index位置上的元素注意index不要超过list中有效元素个数,否则会抛出下标越界异常list.remove(list.size()-1);System.out.println(remove(index)list);// 检测list中是否包含指定元素包含返回true否则返回falseif(list.contains(测试课程)){list.add(测试课程);System.out.println(contains);System.out.println();}
// 查找指定元素第一次出现的位置indexOf从前往后找lastIndexOf从后往前找list.add(JavaSE);System.out.println(list.indexOf:list.indexOf(JavaSE));System.out.println(list.lastIndexOf:list.lastIndexOf(JavaSE));System.out.println();
// 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组ListString ret list.subList(0, 4);System.out.println(subList:ret);System.out.println();list.clear();System.out.println(clear:list.size());} 运行结果如下 3.3 ArrayList的遍历 ArrayList 可以使用三种方式遍历 for 循环 下标、 foreach 、使用迭代器 代码如下 public static void main(String[] args) {ListInteger list new ArrayList();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);// 使用下标for遍历System.out.println(fori);for (int i 0; i list.size(); i) {System.out.print(list.get(i) );}System.out.println();// 借助foreach遍历System.out.println(foreach);for (Integer integer : list) {System.out.print(integer );}System.out.println();System.out.println(Iterator);IteratorInteger it list.listIterator();while(it.hasNext()){System.out.print(it.next() );}}运行结果如下 注意 1. ArrayList最常使用的遍历方式是for循环下标 以及 foreach 2. 迭代器是设计模式的一种 3.4 ArrayList的扩容机制 ArrayList 是一个动态类型的顺序表即在插入元素的过程中会自动扩容。以下是 ArrayList 源码中扩容方式以JDK8为例 Object[] elementData; // 存放元素的空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; // 默认空间
private static final int DEFAULT_CAPACITY 10; // 默认容量大小
public boolean add(E e) {
ensureCapacityInternal(size 1); // Increments modCount!!
elementData[size] e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount;
// overflow-conscious code
if (minCapacity - elementData.length 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// 获取旧空间大小
int oldCapacity elementData.length;
// 预计按照1.5倍方式扩容
int newCapacity oldCapacity (oldCapacity 1);
// 如果用户需要扩容大小 超过 原空间1.5倍按照用户所需大小扩容
if (newCapacity - minCapacity 0)
newCapacity minCapacity;
// 如果需要扩容大小超过MAX_ARRAY_SIZE重新计算容量大小
if (newCapacity - MAX_ARRAY_SIZE 0)
newCapacity hugeCapacity(minCapacity);
// 调用copyOf扩容
elementData Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 如果minCapacity小于0抛出OutOfMemoryError异常
if (minCapacity 0)
throw new OutOfMemoryError();
return (minCapacity MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
} 总结1. 检测是否真正需要扩容如果是调用grow准备扩容 2. 预估需要库容的大小 初步预估按照1.5倍大小扩容 如果用户所需大小超过预估1.5倍大小则按照用户所需大小扩容 真正扩容之前检测是否能扩容成功防止太大导致扩容失败 3. 使用 copyOf 进行扩容 4. ArrayList的模拟实现以整型为例 4.1 定义接口 定义ArrayList的基本功能 // 新增元素,默认在数组最后新增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(); 4.2 实现功能 public int[] elem;public int usedSize;public MyArrayList() {this.elem new int[10];}Overridepublic void add(int data) {//如果满了 能放吗if(isFull()) {//扩容elem Arrays.copyOf(elem,2*elem.length);}this.elem[usedSize] data;this.usedSize;}Overridepublic boolean isFull() {return usedSize elem.length;}Overridepublic void add(int pos, int data) {try {checkPosOfAdd(pos);}catch (PosNotLegalException e) {e.printStackTrace();}if(isFull()) {elem Arrays.copyOf(elem,2*elem.length);}//移动元素for (int i usedSize-1; i pos; i--) {elem[i1] elem[i];}//插入元素elem[pos] data;usedSize;}/*该方法来 判断 添加元素时 pos是否合法*/private void checkPosOfAdd(int pos) throws PosNotLegalException{if(pos 0 || pos usedSize) {throw new PosNotLegalException(pos位置不合法!);}}Overridepublic boolean contains(int toFind) {//只需要寻找usedSize次for (int i 0; i usedSize; i) {if(elem[i] toFind) {return true;}}return false;}Overridepublic int indexOf(int toFind) {for (int i 0; i usedSize; i) {if(elem[i] toFind) {return i;}}return -1;}Overridepublic int get(int pos) {try {checkPosOfGetAndSet(pos);}catch (PosNotLegalException e) {e.printStackTrace();}return elem[pos];}private void checkPosOfGetAndSet(int pos) throws PosNotLegalException{if(pos 0 || pos usedSize) {throw new PosNotLegalException(get/set获取元素的时候 pos位置不合法);}}Overridepublic void set(int pos, int value) {try {checkPosOfGetAndSet(pos);}catch (PosNotLegalException e) {e.printStackTrace();}elem[pos] value;}Overridepublic void remove(int toRemove) {//1、要查找是否存在要删除的关键字 toRemoveint pos indexOf(toRemove);if(pos -1) {System.out.println(没有要删除的数字);return;}for (int i pos; i usedSize-1; i) {elem[i] elem[i1];}usedSize--;}Overridepublic int size() {return usedSize;}Overridepublic void clear() {
//类型为包装类时使用/*for (int i 0; i usedSize; i) {elem[i] null;}*/usedSize 0;}Overridepublic void display() {for (int i 0; i usedSize; i) {System.out.print(elem[i] );}System.out.println();}//自定义异常类
public class PosNotLegalException extends RuntimeException {public PosNotLegalException() {}public PosNotLegalException(String msg) {super(msg);}
} 注意 1. 数组长度不代表有效数值个数使用userdSize来记录有效数值个数 2. 对表进行增删查改时先确认表是否为空或者满了再进行操作 3.对表进行指定位置的删查改时要确认该位置是否合法 4.进行clear时整型逐一置为0其他包装类逐一置为null 5.可根据自己需求自定义异常类进行抛出 4.3 代码测试 MyArrayList myArrayList new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(3);myArrayList.display();System.out.println();myArrayList.add(1,4);myArrayList.display();System.out.println();System.out.println(contains(3)myArrayList.contains(3));System.out.println();System.out.println(indexOf(2):myArrayList.indexOf(2));System.out.println();System.out.println(get(1):myArrayList.get(1));System.out.println();myArrayList.set(0,5);myArrayList.display();System.out.println();myArrayList.remove(2);myArrayList.display();System.out.println();System.out.println(size:myArrayList.size());System.out.println();myArrayList.clear();System.out.println(clear:myArrayList.size()); 运行结果如下 5. ArrayList的优缺点 5.1 优点 随机访问高效由于ArrayList内部是一个数组所以通过索引直接访问元素非常快时间复杂度为O(1)。增删元素方便可以在任意位置插入和删除元素不过插入和删除操作的时间复杂度分别为O(n)因为需要移动其他元素。大小可变ArrayList可以自动调整容量无需预先指定固定大小。 5.2 缺点 空间效率每次元素增加时如果当前容量不足以容纳新元素ArrayList会创建一个新的更大的数组并将所有元素复制过去这可能导致内存浪费。插入和删除效率较低对于频繁的插入和删除操作尤其是在列表的头部或尾部ArrayList的性能不如LinkedList。不适合大量读取而少修改的情况当数据主要是用于查找而非频繁修改时像HashMap这样的数据结构可能更合适。 本文是作者学习后的总结如果有什么不恰当的地方欢迎大佬指正
