[Java数据结构] 1.集合框架和顺序表ArrayList前言:本文旨在帮助新手快速入门数据结构及后续复习, 我们不会去过多谈论底层部分, 而是以应用为准则, 尽可能简单并且有层次地切入让从未接触过数据结构的人也可以快速上手。比如在哈希表前的文章并不会介绍hashCode(); 也不会直接查看底层的代码进行讲解.一. 集合框架介绍集合框架是 Java 中用于存储、管理和操作一组对象的标准体系结构。它是一个统一的、模块化的架构为常见的数据结构如列表、集合、队列、映射等 提供了现成的接口和实现类使开发者无需从零开始编写这些数据结构。常用到的会有下图这些接口或类二. List接口和它的常用方法菜鸟教程中是这样定义List接口的:在Java中List接口是一个有序的集合它允许我们按顺序存储和访问元素。它扩展了集合接口。在集合框架图中可以看到,List实现了Iterable接口,这说明它是可以迭代的,可以使用迭代器iterator()方法来实现元素的遍历.从图中还可以看到顺序表Array,链表LinkedList,动态数组Vector和栈Stack都实现了List接口,所以我们有必要了解一些List的常用方法。如下图部分方法介绍如下方法功能int size()获取元素数量boolean isEmpty()判断是否为空boolean contains(Object)判断是否包含某个元素boolean add(E)尾插元素void add(int,E)在指定位置插入元素boolean addAll(Collection? extends E)尾插全部元素boolean addAll(int,Collection? extends E)在指定位置插入全部元素int IndexOf(Object)查找第一个出现的元素,返回下标int lastIndexOf(Object)查找最后一个出现的元素,返回下标void clear()清空元素List sublist(int,int)在指定范围截取List三.顺序表 ArrayList1.顺序表顺序表是在存储上连续(即数据之间是连着的).在物理上也连续(即存储空间的地址是连续的)的线性结构.2.顺序表ArrayList的介绍和使用(1)ArrayList使用语法和构造方法介绍ArrayList数据类型 name new ArrayList();构造方法功能ArrayList()无参数的构造方法ArrayList(Collection? extends E)使用其他Collection构造ArrayList(int)制定初始容量的构造ArrayList支持动态扩容,底层由数组实现当使用不带参数的构造方法时,默认容量为10,容量不足时会1.5倍扩容Arraylist不是线程安全的ArrayList支持克隆、序列化、随机访问(2) 常用方法实际上和上方List常用方法是一样的方法功能int size()获取元素数量boolean isEmpty()判断是否为空boolean contains(Object)判断是否包含某个元素boolean add(E)尾插元素void add(int,E)在指定位置插入元素boolean addAll(Collection? extends E)尾插全部元素boolean addAll(int,Collection? extends E)在指定位置插入全部元素int IndexOf(Object)查找第一个出现的元素,返回下标int lastIndexOf(Object)查找最后一个出现的元素,返回下标void clear()清空元素List sublist(int,int)在指定范围截取List四. ArrayList的简易实现为了方便理解机制,我们可以简易实现一个与ArrayList原理一致的类.public class MyArrayList implements IList{ public int[] elem; public int usedSize 0; //记录元素个数 public static final int DEFAULT_CAPACITY 10; //不传入参数时构造会有默认容量,在ArrayList里是10 public MyArrayList() { elem new int[DEFAULT_CAPACITY]; } //可以传入参数来制定创建顺序表的大小 public MyArrayList(int capacity) { elem new int[capacity]; } //当顺序表满了时将会扩容,默认为2倍扩容(ArrayList是默认1.5倍扩容) private void grow() { elem Arrays.copyOf(elem,2*elem.length); } //可以传值控制扩容倍数 private void grow(int growNum) { elem Arrays.copyOf(elem,growNum*elem.length); } private boolean isFull() { return usedSize elem.length; } //在末尾添加元素 Override public void add(int data) { //执行时会先判断顺序表是否已满,若满了会自动扩容(1.5倍) if(isFull()) { grow(); } //先使用最后的位置,再把计数增加1 elem[usedSize] data; } //在指定位置插入元素 Override public void add(int pos, int data) { //1.会先判断插入位置是否合法 checkPos(pos); //2.若合法,继续判断顺序表是否已满 if(isFull()) { grow(); } //3.插入元素时会先将后续所有元素后移一次; // 时间复杂度为O(n)因此顺序表不适合频繁插入元素 for(int i usedSize - 1; i pos; i--) { elem[i 1] elem[i]; } elem[pos] data; //4.增加计数 usedSize; } //用于判断位置是否合法 private void checkPos(int pos) { if(pos 0 || pos usedSize) { throw new PosOutOfBoundsExcption(所选位置不合法!); } } //查看顺序表是否包含指定值 Override public boolean contains(int toFind) { //遍历去寻找指定值,若包含则返回真,时间复杂度O(n) for (int i 0; i usedSize; i) { if(elem[i] toFind) { return true; } } return false; } //寻找第一个出现的指定值 Override public int indexOf(int toFind) { //遍历去寻找第一个指定值,发现则返回下标,时间复杂度为O(n) for(int i 0; i usedSize; i) { if(elem[i] toFind) { return i; } } return -1; } //获取制定位置的元素,时间复杂度O(1) Override public int get(int pos) { //1.先检查位置是否合法 checkPos(pos); //2.检查顺序表是否为空 if(isEmpty()) { throw new ListEmptyException(该顺序表为空,无法获取元素!); } return elem[pos]; } //修改指定位置元素,时间复杂度O(1) Override public void set(int pos, int value) { //先检查位置是否合法 checkPos(pos); elem[pos] value; } //移除第一个指定元素,时间复杂度O(n) Override public void remove(int toRemove) { //1.先查找需要修改的值并记录其下标,找不到则抛出异常 int index indexOf(toRemove); if(index -1) { System.out.println(没有要删除的数据); return; } //2.将找到的数据进行覆盖,后面的元素依次前移 for (int i index; i usedSize - 1; i) { elem[i] elem[i 1]; } //3.修改计数器-1 usedSize--; } Override public int size() { return usedSize; } Override public void clear() { //直接清除计数器即可 usedSize 0; } Override public boolean isEmpty() { return usedSize 0; } }五.ArrayList的优势和劣势1.优势ArrayList底层由数组实现,在查询数据时十分迅速,时间复杂度为O(1),随机访问性能极其优越2.劣势由上面的代码和分析可以知道,ArrayList在增(除尾插)、删、改操作时,往往要移动很多数据,时间复杂度为O(n);并且增容时默认是1.5倍扩容,或者指定倍数扩容,这导致在数据量较大时扩容会浪费很多空间.3.适用场景综上可知,ArrayList适用于以下场景需要频繁随机访问的数据(查询数据性能高)需要遍历多次的数据(物理存储连续)添加数据以尾插为主的数据(尾插时间复杂度为O(1))元素数量相对稳定,可预估的数据(防止空间浪费)不使用以下场景与上述适用情形相反的情形多线程