数据结构之第四章、ArrayList和顺序表

 一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

---

二、顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

2.1接口的实现

public class SeqList {private int[] array;private int size;private static final DEFAULT_CAPACITY;// 将顺序表的底层容量设置为DEFAULT_CAPACITYSeqList(){ }//判断是否达到容量public boolean isFull();//扩容机制public void resize();// 新增元素,默认在数组最后新增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) { }//判断顺序表是否为空public boolean isEmpty();//删除第一次出现的关键字keypublic void remove(int toRemove) { }// 获取顺序表长度public int size() { return 0; }// 清空顺序表public void clear() { }// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display() { }
}
//---------------------------------------------------------------------------------------//自定义异常public class PosOutOfException extends RuntimeException；

2.2方法的实现 

public class SeqList {//定义数组private int[] array;//有效数据private int usedsize;private static final int DEFAULT_CAPACITY=5;// 默认构造方法// 将顺序表的底层容量设置为DEFAULT_CAPACITYSeqList(){this.array=new int[DEFAULT_CAPACITY];}// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display() {for (int i = 0; i < usedsize; i++) {System.out.print(array[i]);}System.out.println();}//判断是否达到容量public boolean isFull(){if(usedsize==DEFAULT_CAPACITY){return false;}return true;}//扩容机制public void resize(){array=Arrays.copyOf(array,2* array.length);}// 新增元素,默认在数组最后新增public void add(int data) {if(isFull()){resize();}this.array[usedsize]=data;usedsize++;}// 在 pos 位置新增元素public void add(int pos, int data) {if(!Pos(pos)){throw new posOutOfException();}if(isFull()){resize();}//挪动数据for (int i = this.usedsize-1; i >=pos; i--) {this.array[i+1]=this.array[i];}this.array[pos]=data;this.usedsize++;}// 判定是否包含某个元素public boolean contains(int toFind) {for (int i = 0; i < this.usedsize; i++) {if(this.array[i]==toFind){return true;}}return false;}// 查找某个元素对应的位置public int indexOf(int toFind) {for (int i = 0; i < this.usedsize; i++) {if(this.array[i]==toFind){return i;}}return -1;}//判断pos位置元素是否符合要求public boolean Pos(int pos){if(pos>=this.usedsize||pos<0){return false;}return true;}// 获取 pos 位置的元素public int get(int pos) {if(Pos(pos)==true){return array[pos];}throw new posOutOfException();}// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) {if(!Pos(pos)){throw new posOutOfException("set数据时，位置不合法！");}this.array[pos]=value;}//删除第一次出现的关键字keypublic void remove(int toRemove) {if(isEmpty()){return ;}int index=indexOf(toRemove);if(indexOf(toRemove)==-1){return ;}else{for (int i = index; i < this.usedsize-1; i++) {this.array[i] = this.array[i+1];}}this.usedsize--;}//判断顺序表是否为空public boolean isEmpty(){return this.usedsize==0;}// 获取顺序表长度public int size() {return this.usedsize;}// 清空顺序表public void clear() {for (int i = 0; i < this.usedsize; i++) {array[i]=0;}//引用类型：array[i]=null;this.usedsize=0;}
}

---

三、ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：

【说明】

• ArrayList是以泛型方式实现的，使用时必须要先实例化
• ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
• ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
• ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
• 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
• ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

---

四、ArrayList使用

4.1ArrayList的构造

4.1.1ArrayList的无参构造 

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>();list.add(10);}

查看底层源码看ArrayList的底层代码实现： 

 再看add方法：

 

 综上分析：

1. 当调用不带参数的构造方法的时候，默认数组长度为0。
2. 当第一次add的时候，才会分配内存，且分配内存的容量为10。

4.1.2指定顺序表初始容量的构造方法 

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>(10);list.add(10);}

查看相应源码： 

4.1.3借助Collection构造 

class People{}
class Student extends People{}
class Animal{}
public class Demo1 {public static void main(String[] args) {ArrayList<Student> list=new ArrayList<>();ArrayList<People> list2=new ArrayList<>(list);//list是People的子类ArrayList<Animal> list3=new ArrayList<>();ArrayList<People> list4=new ArrayList<>(list3);}
}

构造方法小结： 

public static void main(String[] args) {// ArrayList创建，推荐写法// 构造一个空的列表List<Integer> list1 = new ArrayList<>();// 构造一个具有10个容量的列表List<Integer> list2 = new ArrayList<>(10);list2.add(1);list2.add(2);list2.add(3);// list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素// list3构造好之后，与list中的元素一致ArrayList<Integer> list3 = new ArrayList<>(list2);// 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难List list4 = new ArrayList();list4.add("111");list4.add(100);}

4.2ArrayList常见操作

常见方法如下：

4.2.1 add(E e)方法

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>();list.add(10);list.add(150);ArrayList<String> list2=new ArrayList<>();list2.add("Hello ");list2.add("World!");}

 4.2.2 add(int index,E element)方法

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>();list.add(10);list.add(150);list.add(1,20);ArrayList<String> list2=new ArrayList<>();list2.add("Hello ");list2.add("World!");list2.add(0,"Java:");System.out.println("=========");}

 4.2.3 addAll(Collection<? extends E> c)方法

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>();list.add(10);list.add(150);list.add(1,20);ArrayList<String> list2=new ArrayList<>();list2.add("Hello ");list2.add("World!");list2.add(0,"Java:");ArrayList<String> list3=new ArrayList<>();list3.addAll(list2);System.out.println("=========");}

 4.2.4 remove(int index)方法

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>();list.add(10);list.add(150);list.add(1,20);ArrayList<String> list2=new ArrayList<>();list2.add("Hello ");list2.add("World!");list2.add(0,"Java:");list.remove(2);list2.remove(0);System.out.println("========");}

 4.2.5 get(int index)方法

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>();list.add(10);list.add(150);list.add(1,20);ArrayList<String> list2=new ArrayList<>();list2.add("Hello ");list2.add("World!");list2.add(0,"Java:");System.out.println(list.get(1));System.out.println(list2.get(0));//20//Java:System.out.println("========");}

4.2.6 set(int index,E element)方法

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>();list.add(10);list.add(150);list.add(1,20);ArrayList<String> list2=new ArrayList<>();list2.add("Hello ");list2.add("World!");list2.add(0,"Java:");list.set(1,30);list2.set(0," ");System.out.println("========");}

 4.2.7 List<E> subList(int fromIndex, int toIndex)方法注意事项

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>();list.add(10);list.add(150);list.add(1,20);List<Integer> list2=list.subList(0,2);list2.set(0,100);System.out.println("========");}

 这里的截取并不是返回一个新的顺序表，而是指向截取的范围的引用。此时发生的并不是一个拷贝。功能总结练习：

public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("JavaSE");list.add("JavaWeb");list.add("JavaEE");list.add("JVM");list.add("测试课程");System.out.println(list);
// 获取list中有效元素个数System.out.println(list.size());
// 获取和设置index位置上的元素，注意index必须介于[0, size)间System.out.println(list.get(1));list.set(1, "JavaWEB");System.out.println(list.get(1));
// 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置list.add(1, "Java数据结构");System.out.println(list);
// 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置list.remove("JVM");System.out.println(list);
// 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常list.remove(list.size()-1);System.out.println(list);
// 检测list中是否包含指定元素，包含返回true，否则返回falseif(list.contains("测试课程")){list.add("测试课程");} // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找list.add("JavaSE");System.out.println(list.indexOf("JavaSE"));System.out.println(list.lastIndexOf("JavaSE"));
// 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组List<String> ret = list.subList(0, 4);System.out.println(ret);list.clear();System.out.println(list.size());}

4.2.8ArrayList的输出方式

通过ARrayList源码逐步查看：

 4.3ArrayList的遍历操作

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

4.3.1通过for循环遍历

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>();list.add(10);list.add(150);list.add(1,20);System.out.println("========");for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));}//10//20//150}

4.3.2通过for-each遍历

左边：右边：---->

右边是要进行遍历的集合

左边是集合当中元素的类型所定义的变量

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>();list.add(10);list.add(150);list.add(1,20);System.out.println("========");for (Integer i:list) {System.out.println(i);}//10//20//150}

4.3.3通过迭代器遍历

public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>();list.add(10);list.add(150);list.add(1,20);System.out.println("========");Iterator<Integer> it=list.iterator();//it相当于指针，走一步输出一个走一步输出一个//这就是迭代器while(it.hasNext()){//如果有下一个就输出下一个System.out.println(it.next());}//10//20//150}

注意：
1. ArrayList最常使用的遍历方式是：for循环+下标 以及 foreach
2. 迭代器是设计模式的一种，后序容器接触多了再给大家铺垫

3.

4.4ArrayList的扩容机制 

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.5倍大小扩容。如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容，真正扩容之前检测是否能扩容成功，防止太大导致扩容失败。
3. 使用copyOf进行扩容

---

五、ArrayList的具体使用

5.1实现洗牌算法

public class Card {//创建牌private int rank;//牌面值private String suit;//花色//构造方法+set和getpublic Card() {}public Card(int rank, String suit) {this.rank = rank;this.suit = suit;}public int getRank() {return rank;}public void setRank(int rank) {this.rank = rank;}public String getSuit() {return suit;}public void setSuit(String suit) {this.suit = suit;}//重写toString方法public String toString(){return suit+" "+rank;}
}
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class Cards {//四种花色的字符串数组private static final String[] SUITS={"♥","♠","♣","♦"};public static List<Card> buyCard(){//创建52张牌，每个花色13张牌List<Card> list=new ArrayList<>();for (int i=0;i<SUITS.length;i++){for (int j = 1; j <=13 ; j++) {Card card=new Card(j,SUITS[i]);list.add(card);}}return list;}//实现牌组的交换public static void shuffle(List<Card> list){Random output=new Random();for (int i = list.size()-1; i >0 ; i--) {int j=output.nextInt(i);//实现牌组的交换Card tmp=list.get(i);list.set(i,list.get(j));list.set(j,tmp);}}public static void main(String[] args) {//置牌List<Card> list=buyCard();System.out.println(list);System.out.println("洗牌：");shuffle(list);System.out.println(list);System.out.println("发牌：");List<Card> list1=new ArrayList<Card>();List<Card> list2=new ArrayList<>();List<Card> list3=new ArrayList<>();//ArrayList构造方法List<List<Card>> hand=new ArrayList<>();hand.add(list1);hand.add(list2);hand.add(list3);for (int i = 0; i < 14; i++) {for (int j = 0; j < hand.size(); j++) {//摸牌动作Card tmp=list.remove(0);hand.get(j).add(tmp);}}System.out.println("第一个人的牌数：");System.out.println(list1);System.out.println("第二个人的牌数：");System.out.println(list2);System.out.println("第三个人的牌数：");System.out.println(list3);}
}

---

六、ArrayList的问题及思考

6.1顺序表的优点

1. 根据指定下标（索引）去查找元素，效率非常高！时间复杂度为O(1)。
2. 更新元素也很快：更新指定下标的元素。时间复杂度为O(1)。

6.2顺序表的缺点

1. 每次插入数据，都需要移动元素。极端情况下，如果插入到0下标，那么移动的元素复杂度O(N)。
2. 每次删除数据的时候，都需要移动元素。极端情况下，删除0下标的元素的时间复杂度为O(N)。
3. 当容量满后进行1.5倍扩容。然后只放了一个元素，此时可能会浪费空间。

6.3总结

顺序表适用于经常进行查找元素或者更新元素的场景下，此时推荐使用顺序表。