邯郸有学做搭建网站的吗,asp网站作业下载,百度网页版链接,怀化组织部网站目录 前言
顺序表
编辑
顺序表和数组
ArrayList简介
说明
ArrayList使用编辑
ArrayList常见操作 ArrayList实现二维数组
ArrayList的遍历 ArrayList的扩容机制 总结 前言
一个高端的程序员,往往都是数据结构学的很好,判断一个程序的优劣也是看数据结构学的好与坏.…目录 前言
顺序表
编辑
顺序表和数组
ArrayList简介
说明
ArrayList使用编辑
ArrayList常见操作 ArrayList实现二维数组
ArrayList的遍历 ArrayList的扩容机制 总结 前言
一个高端的程序员,往往都是数据结构学的很好,判断一个程序的优劣也是看数据结构学的好与坏.
顺序表,数据结构中最简单的部分之一,让我们一起学习吧~~~
顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表和数组
顺序表的底层就是用数组来实现的.我们会有这样的疑问,顺序表和数组很像,而且它还是用数组实现的,那么顺序表存在的意义又是什么呢?
我们可以这样理解: 我们运用数组创造出了一个常用的数据结构,然后以后每次使用的时候,我们不必再用数组实现,而是直接调用它(就像库函数一样)
更简单的理解: 数组就像是单个电脑主机 而顺序表就像是外设齐全的电脑(键盘,鼠标,显示屏等等)
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底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表
ArrayList使用
public static void main(String[] args) {// ArrayList创建推荐写法// 构造一个空的列表ListInteger list1 new ArrayList();// 构造一个具有10个容量的列表ListInteger list2 new ArrayList(10);list2.add(1);list2.add(2);list2.add(3);// list2.add(hello); // 编译失败ListInteger已经限定了list2中只能存储整形元素// list3构造好之后与list中的元素一致ArrayListInteger list3 new ArrayList(list2);// 避免省略类型否则任意类型的元素都可以存放使用时将是一场灾难List list4 new ArrayList();list4.add(111);list4.add(100);
}
ArrayList常见操作 ArrayList实现二维数组
ArrayListArrayListInteger test new ArrayList();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遍历for (int i 0; i list.size(); i) {System.out.print(list.get(i) );} System.out.println();// 借助foreach遍历for (Integer integer : list) {System.out.print(integer );} System.out.println();//list的迭代器IteratorInteger it list.listIterator();while(it.hasNext()){System.out.print(it.next() );} System.out.println();
} ArrayList的扩容机制
顺序表是用数组来实现的,那么我们会好奇:
如果不给容量参数的话,会不会报错? 答:不会,会有默认的容量 如果容量满了,我们再添加元素,程序会扩容还是会报错 答:ArrayList是一个动态类型的顺序表,即在插入元素的过程中会自动扩容 下面ArrayList源码扩容的方法(只看有注释的部分即可,其他可以了解)
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 codeif (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)预估按照1.5倍大小扩容 (2)如果用户所需大小超过预估1.5倍大小则按照用户所需大小扩容 (3)真正扩容之前检测是否能扩容成功防止太大导致扩容失败 3. 使用copyOf进行扩容
