顺序表
含义：物理上连续，逻辑上也连续的线性结构。
应用于对数组的数据进行增删查改。
ArrayList说明
ArrayList是一个普通的类，实现了List接口
【说明】
- ArrayList是以泛型方式实现的，使用时必须要先实例化
- ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
- ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
- ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
- 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
- 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) 删除遇到的第一个 o
- E get(int index) 获取下标 index 位置元素
- E set(int index, E element) 将下标 index 位置元素设置为 element
- void clear() 清空
- boolean contains(Object o) 判断 o 是否在线性表中
- int indexOf(Object o) 返回第一个 o 所在下标
- int lastIndexOf(Object o) 返回最后一个 o 的下标
- List subList(int fromIndex, int toIndex) 截取部分 list
顺序表的优缺点
缺点：
1.插入数据必须要移动其他数据，最坏情况下，是插入到0位置，时间复杂度为O（N）。
2.删除数据也需要移动数据，就坏情况下，是删除0位置，时间复杂度为O（N）。
优点：
在给定下标查找时，时间复杂度为O（1）。
所以什么时候适合用顺序表？
就是给定下表查找时的场景。
ArrayList的扩容机制
ArrayList是一个动态类型的顺序表，在插入元素的过程中会自动扩容。
- 按照1.5倍扩容
- 第一次Add时，会分配大小为10的内存
1.练习 ：杨辉三角
代码如下
class Solution { public List<List<Integer>> generate(int numRows) { //二维数组 List<List<Integer>> ret= new ArrayList<>(); //第一行 ArrayList<Integer> list = new ArrayList<>(); //第一行的第一个元素 list.add(1); //把第一行的元素放到二维数组里 ret.add(list); //第二行的每个元素由前一行所得 for (int i = 1; i <numRows ; i++) { //实例化当前行 List<Integer> curRow = new ArrayList<Integer>(); //当前行第一个元素是1 curRow.add(1); //获取一维数组中上一行的元素。get方法是获取pos位置的元素 List<Integer> prevRow = ret.get(i - 1); //当前行的中间元素 for (int j = 1; j < i; j++) { int val = prevRow.get(j) + prevRow.get(j - 1); curRow.add(val); } //当前行的最后一个数据 curRow.add(1); //把当前行数组放到二维数组里 ret.add(curRow); } return ret; } }
2.顺序表的实现
//定义一个接口 public interface IList { //新增元素，默认在数组最后新增 public void add(int data) ; // 在 pos 位置新增元素 public void add(int pos, int data) ; // 判定是否包含某个元素 public boolean contains(int toFind); // 查找某个元素对应的位置 public int indexOf(int toFind) ; // 获取 pos 位置的元素 public int get(int pos) ; // 给 pos 位置的元素设为 value //(修改pos位置上的值) public void set(int pos, int value); //删除第一次出现的关键字key public void remove(int toRemove) ; // 获取顺序表长度 public int size() ; // 清空顺序表 public void clear() ; // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的 public void display() ; public boolean isEmpty(); } //类实现接口 public class MyArrayList implements IList { //定义一个数组 public int[] elem; private int usedSize; public static final int DEFAUL_SIZE = 5; public MyArrayList() { //初始化数组 this.elem = new int[DEFAUL_SIZE]; } public MyArrayList(int capacity){ this.elem = new int[capacity]; } //遍历顺序表方法 public void display(){ for (int i = 0; i < this.usedSize; i++) { System.out.print(this.elem[i]+" "); } System.out.println(); } //判断数组满了没有 public boolean isFull(){ if (usedSize == elem.length){ return true; } return false; } @Override public void add(int data) { //判断满没满才能放 cheakCapacity(); this.elem[this.usedSize] = data; this.usedSize++; } //扩容方法 //private封装，只为当前类使用 private void cheakCapacity(){ if (isFull()){ //满了扩容 elem = Arrays.copyOf(elem,elem.length*2); } } /* 检查pos的合法性 */ private void cheakPosOnGetAndSet(int pos) throws PosIllegality { if (pos < 0 || pos >usedSize){ System.out.println("pos位置不合法!"); //抛异常，以便能找到哪一行错误 throw new PosIllegality("插入元素下标异常：" + pos); } } //指定位置放元素 @Override public void add(int pos, int data) { try{ cheakPosOnGetAndSet(pos); }catch(PosIllegality e){ e.printStackTrace(); return ; } cheakCapacity(); for (int i = usedSize-1; i >= pos ; i--) { elem[i+1] = elem[i]; } elem[pos] = data; usedSize ++; } //是否包含某个元素 @Override public boolean contains(int toFind) { if(isEmpty()) { return false; } for (int i = 0; i < usedSize; i++) { //如果是查找引用数据类型，一定记住要重写方法 if (elem[i] == toFind){ return true; } } return false; } @Override public int indexOf(int toFind) { if(isEmpty()) { return -1; } for (int i = 0; i < usedSize; i++) { //如果是查找引用数据类型，一定记住要重写方法 if (elem[i] == toFind){ return i; } } return -1; } @Override public int get(int pos) throws MyArrayEmpty{ cheakPosOnGetAndSet(pos); if (isEmpty()){ throw new MyArrayEmpty("获取顺序表下标位置时"+ "顺序表为空！"); } return elem[pos]; } @Override public void set(int pos, int value) { //先检查pos的合法性， cheakPosOnGetAndSet(pos); //修改pos上的值 elem[pos] = value ; } @Override public void remove(int toRemove) { int index = indexOf(toRemove); if (index == -1){ System.out.println("没有这个数字！"); return; } for (int i = index; i < usedSize-1; i++) { elem[i] = elem[i+1]; } usedSize--; } @Override public int size() { return this.usedSize; } @Override public void clear() { this.usedSize = 0; //如果是引用数据类型,可以用for循环一个一个置为null } public boolean isEmpty(){ return usedSize == 0; } } public class MyArrayEmpty extends RuntimeException { public MyArrayEmpty(String msg){ super(msg); } } public class PosIllegality extends RuntimeException { //构造方法 public PosIllegality(String msg){ super(msg); } } public class Test{ public static void main1(String[] args) { MyArrayList myArrayList = new MyArrayList(); myArrayList.add(1);//下标0 myArrayList.add(2);//下标1 myArrayList.add(199);//下标2 myArrayList.display(); //删除元素2 myArrayList.remove(2); myArrayList.display(); }
3.简单的洗牌算法
package card; import java.util.ArrayList; import java.util.List; import java.util.Random; /** 52张牌 1-k J Q K 11 12 13 */ public class CardDemo { //定义花色 private final String[] suits = {"♥","♠","♦","♣"}; //买的牌 public List<Card> buyCard(){ //产生52张牌 List<Card> cardList = new ArrayList<>(); for (int i = 0; i < 4; i++) { for (int j = 0; j < 13; j++) { Card card = new Card(suits[i],j); cardList.add(card); } } return cardList; } //洗牌 public void shuffle(List<Card> cardList){ //生成随机数 Random random = new Random(); for (int i =cardList.size()-1; i >0; i--) { int index = random.nextInt(i); //交换 swap(cardList,i,index); } } private void swap(List<Card> cardList,int a,int b) { //把a和b交换 Card tmp = cardList.get(a); cardList.set(a, cardList.get(b)); cardList.set(b, tmp); } public void getCard(List<Card> cardList){ List<Card> hand1 = new ArrayList<>(); List<Card> hand2 = new ArrayList<>(); List<Card> hand3 = new ArrayList<>(); List<List<Card>> hands = new ArrayList<>(); hands.add(hand1); hands.add(hand2); hands.add(hand3); //每个人轮流抓5张牌 for (int i = 0; i <5 ; i++) { for (int j = 0; j < 3; j++) { Card card = cardList.remove(0); hands.get(j).add(card); } } System.out.println("第1个揭牌如下："); System.out.println(hand1); System.out.println("第2个揭牌如下："); System.out.println(hand2); System.out.println("第3个揭牌如下："); System.out.println(hand3); System.out.println("剩下的牌："); System.out.println(cardList); } } package card; import java.sql.SQLOutput; import java.util.List; public class Test { public static void main(String[] args) { CardDemo cardDemo = new CardDemo(); List<Card> cardList = cardDemo.buyCard(); System.out.println("买的牌如下："); System.out.println(cardList); System.out.println("洗牌："); cardDemo.shuffle(cardList); System.out.println(cardList); System.out.println("揭牌："); cardDemo.getCard(cardList); } }
