一、顺序表（ArrayList）
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。
1. List
1.1 List的定义
List 是一个接口
2. 顺序表的结构
1.1 顺序表是一个类，实现了 List 接口
1.2 java系统中实现了顺序表的构造，如若需要使用提供的方法，可以直接调用系统的方法。
3. 自定义一个顺序表
publicclassSeqList{privateint[]data;// 构建一个数组，存储元素publicintsize=0;// 表示数组的有效长度// 构造方法publicSeqList(){data=newint[1024];}// 在尾部添加元素: 时间复杂度为 O(1)publicvoidadd(intvalue){//1. 判断数组容量是否够if(size>=data.length){realloc();//对数组扩容}data[size]=value;size++;}publicvoidrealloc(){//1.创建一个新的变量int[]newData=newint[data.length*2];for(inti=0;i<size;i++){newData[i]=data[i];}data=newData;}// 中间位置添加元素: 时间复杂度为 O(N)publicvoidadd(intindex,intvalue){//1. 判断数组容量是否够if(size>=data.length){realloc();}//2. 把要添加的位置元素依次往后挪一格for(inti=size-1;i>=index;i--){data[i+1]=data[i];}//3. 直接在该位置上添加新元素data[index]=value;size++;}// 判断元素是否存在: 时间复杂度为 O(N)publicbooleancontains(intvalue){for(inti=0;i<size;i++){if(data[i]==value){returntrue;}}returnfalse;}// 找到元素在顺序表的位置: 时间复杂度为 O(N)publicintindexOf(intvalue){for(inti=0;i<size;i++){if(data[i]==value){returni;}}return-1;}// 按照位置删除元素: 时间复杂度为 O(N)publicvoidremove(intindex){//1. 判断 index 是否合法if(index<0||index>=size){thrownewRuntimeException("索引越界");}//2. 将该位置之后的元素都往前挪一格for(inti=index;i<size-1;i++){data[i]=data[i+1];}size--;}// 按照值删除元素：时间复杂度为 O(N)publicvoidremoveByValue(intvalue){//1.遍历数组，找到该值的下标位置intindex=indexOf(value);//2. 如果不存在，直接返回if(index==-1){return;}//3. 调用上面的 根据位置删除元素 的方法remove(index);}//get方法: 时间复杂度为 O(1)publicintget(intindex){if(index<0||index>=size){thrownewRuntimeException("索引越界");}returndata[index];}// set 方法: 时间复杂度为 O(1)publicintset(intindex,intvalue){returndata[index]=value;}4. ArrayList 的使用方式
（1） ArrayList是以泛型方式实现的，使用时必须先实例化
ArrayList<E>list=newArrayList<>();（2）ArrayList 实现了 Clonable 接口，表明 ArrayList 是可以 clone（浅拷贝） 的
importjava.util.ArrayList;classUser{Stringname;publicUser(Stringname){this.name=name;}}publicclassDemo{publicstaticvoidmain(String[]args){ArrayList<User>list1=newArrayList<>();list1.add(newUser("张三"));list1.add(newUser("李四"));ArrayList<User>list2=(ArrayList<User>)list1.clone();System.out.println(list1==list2);//false 原因是：ArrayList 的 clone 是浅拷贝System.out.println(list1.get(0)==list2.get(0));//true 原因是: 元素引用时同一个list1.get(0).name="改名了";System.out.println(list2.get(0).name);// 改名了}}（3）ArrayList 底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
5. ArrayList的应用场景
5.1 构造一副牌
importjava.util.ArrayList;importjava.util.List;importjava.util.Random;classCard{privateStringrank;//点数privateStringsuit;//花色publicStringgetRank(){returnrank;}publicvoidsetRank(Stringrank){this.rank=rank;}publicStringgetSuit(){returnsuit;}publicvoidsetSuit(Stringsuit){this.suit=suit;}@OverridepublicStringtoString(){returnsuit+rank;}}publicclassCardDemo{privatestaticList<Card>buyCards(){List<Card>cards=newArrayList<>();String[]suits={"♠️","♥️","♣️","♦️"};for(inti=0;i<suits.length;i++){for(intj=2;j<=10;j++){Cardcard=newCard();card.setSuit(suits[i]);card.setRank(j+"");cards.add(card);}CardcardJ=newCard();cardJ.setSuit(suits[i]);cardJ.setRank("J");CardcardQ=newCard();cardQ.setSuit(suits[i]);cardQ.setRank("Q");CardcardK=newCard();cardK.setSuit(suits[i]);cardK.setRank("K");CardcardA=newCard();cardA.setSuit(suits[i]);cardA.setRank("A");cards.add(cardJ);cards.add(cardQ);cards.add(cardK);cards.add(cardA);}returncards;}// 洗牌privatestaticvoidshuffle(List<Card>cards){Randomrandom=newRandom();for(inti=cards.size()-1;i>0;i--){intr=random.nextInt(i);Cardtemp=cards.get(r);cards.set(r,cards.get(i));cards.set(i,temp);}}publicstaticvoidmain(String[]args){List<Card>cards=buyCards();//System.out.println(cards);shuffle(cards);//System.out.println(cards);// 发牌List<Card>player1=newArrayList<>();List<Card>player2=newArrayList<>();List<Card>player3=newArrayList<>();List<List<Card>>players=newArrayList<>();players.add(player1);players.add(player2);players.add(player3);for(inti=0;i<5;i++){for(intj=0;j<players.size();j++){Cardcard=cards.remove(0);players.get(j).add(card);}}for(inti=0;i<players.size();i++){System.out.println("玩家"+(i+1)+""+":"+players.get(i));}}}5.2 杨辉三角
importjava.util.ArrayList;importjava.util.List;publicclassyangHUi{publicList<List<Integer>>generate(intnumRows){List<List<Integer>>ret=newArrayList<>();for(introwIndex=0;rowIndex<numRows;rowIndex++){List<Integer>row=newArrayList<>();for(intcolIndex=0;colIndex<rowIndex+1;colIndex++){if(colIndex==0||colIndex==rowIndex){row.add(1);}else{List<Integer>prevRow=ret.get(rowIndex-1);intvalue1=prevRow.get(colIndex-1);intvalue2=prevRow.get(colIndex);row.add(value1+value2);}}ret.add(row);}returnret;}publicstaticvoidmain(String[]args){yangHUi y=newyangHUi();List<List<Integer>>ret=y.generate(5);System.out.println(ret);}
