一、顺序表ArrayList顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。1. List1.1 List的定义List 是一个接口2. 顺序表的结构1.1 顺序表是一个类实现了 List 接口1.2 java系统中实现了顺序表的构造如若需要使用提供的方法可以直接调用系统的方法。3. 自定义一个顺序表publicclassSeqList{privateint[]data;// 构建一个数组存储元素publicintsize0;// 表示数组的有效长度// 构造方法publicSeqList(){datanewint[1024];}// 在尾部添加元素: 时间复杂度为 O(1)publicvoidadd(intvalue){//1. 判断数组容量是否够if(sizedata.length){realloc();//对数组扩容}data[size]value;size;}publicvoidrealloc(){//1.创建一个新的变量int[]newDatanewint[data.length*2];for(inti0;isize;i){newData[i]data[i];}datanewData;}// 中间位置添加元素: 时间复杂度为 O(N)publicvoidadd(intindex,intvalue){//1. 判断数组容量是否够if(sizedata.length){realloc();}//2. 把要添加的位置元素依次往后挪一格for(intisize-1;iindex;i--){data[i1]data[i];}//3. 直接在该位置上添加新元素data[index]value;size;}// 判断元素是否存在: 时间复杂度为 O(N)publicbooleancontains(intvalue){for(inti0;isize;i){if(data[i]value){returntrue;}}returnfalse;}// 找到元素在顺序表的位置: 时间复杂度为 O(N)publicintindexOf(intvalue){for(inti0;isize;i){if(data[i]value){returni;}}return-1;}// 按照位置删除元素: 时间复杂度为 O(N)publicvoidremove(intindex){//1. 判断 index 是否合法if(index0||indexsize){thrownewRuntimeException(索引越界);}//2. 将该位置之后的元素都往前挪一格for(intiindex;isize-1;i){data[i]data[i1];}size--;}// 按照值删除元素时间复杂度为 O(N)publicvoidremoveByValue(intvalue){//1.遍历数组找到该值的下标位置intindexindexOf(value);//2. 如果不存在直接返回if(index-1){return;}//3. 调用上面的 根据位置删除元素 的方法remove(index);}//get方法: 时间复杂度为 O(1)publicintget(intindex){if(index0||indexsize){thrownewRuntimeException(索引越界);}returndata[index];}// set 方法: 时间复杂度为 O(1)publicintset(intindex,intvalue){returndata[index]value;}4. ArrayList 的使用方式1 ArrayList是以泛型方式实现的使用时必须先实例化ArrayListElistnewArrayList();2ArrayList 实现了 Clonable 接口表明 ArrayList 是可以 clone浅拷贝 的importjava.util.ArrayList;classUser{Stringname;publicUser(Stringname){this.namename;}}publicclassDemo{publicstaticvoidmain(String[]args){ArrayListUserlist1newArrayList();list1.add(newUser(张三));list1.add(newUser(李四));ArrayListUserlist2(ArrayListUser)list1.clone();System.out.println(list1list2);//false 原因是ArrayList 的 clone 是浅拷贝System.out.println(list1.get(0)list2.get(0));//true 原因是: 元素引用时同一个list1.get(0).name改名了;System.out.println(list2.get(0).name);// 改名了}}3ArrayList 底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表5. ArrayList的应用场景5.1 构造一副牌importjava.util.ArrayList;importjava.util.List;importjava.util.Random;classCard{privateStringrank;//点数privateStringsuit;//花色publicStringgetRank(){returnrank;}publicvoidsetRank(Stringrank){this.rankrank;}publicStringgetSuit(){returnsuit;}publicvoidsetSuit(Stringsuit){this.suitsuit;}OverridepublicStringtoString(){returnsuitrank;}}publicclassCardDemo{privatestaticListCardbuyCards(){ListCardcardsnewArrayList();String[]suits{♠️,♥️,♣️,♦️};for(inti0;isuits.length;i){for(intj2;j10;j){CardcardnewCard();card.setSuit(suits[i]);card.setRank(j);cards.add(card);}CardcardJnewCard();cardJ.setSuit(suits[i]);cardJ.setRank(J);CardcardQnewCard();cardQ.setSuit(suits[i]);cardQ.setRank(Q);CardcardKnewCard();cardK.setSuit(suits[i]);cardK.setRank(K);CardcardAnewCard();cardA.setSuit(suits[i]);cardA.setRank(A);cards.add(cardJ);cards.add(cardQ);cards.add(cardK);cards.add(cardA);}returncards;}// 洗牌privatestaticvoidshuffle(ListCardcards){RandomrandomnewRandom();for(inticards.size()-1;i0;i--){intrrandom.nextInt(i);Cardtempcards.get(r);cards.set(r,cards.get(i));cards.set(i,temp);}}publicstaticvoidmain(String[]args){ListCardcardsbuyCards();//System.out.println(cards);shuffle(cards);//System.out.println(cards);// 发牌ListCardplayer1newArrayList();ListCardplayer2newArrayList();ListCardplayer3newArrayList();ListListCardplayersnewArrayList();players.add(player1);players.add(player2);players.add(player3);for(inti0;i5;i){for(intj0;jplayers.size();j){Cardcardcards.remove(0);players.get(j).add(card);}}for(inti0;iplayers.size();i){System.out.println(玩家(i1):players.get(i));}}}5.2 杨辉三角importjava.util.ArrayList;importjava.util.List;publicclassyangHUi{publicListListIntegergenerate(intnumRows){ListListIntegerretnewArrayList();for(introwIndex0;rowIndexnumRows;rowIndex){ListIntegerrownewArrayList();for(intcolIndex0;colIndexrowIndex1;colIndex){if(colIndex0||colIndexrowIndex){row.add(1);}else{ListIntegerprevRowret.get(rowIndex-1);intvalue1prevRow.get(colIndex-1);intvalue2prevRow.get(colIndex);row.add(value1value2);}}ret.add(row);}returnret;}publicstaticvoidmain(String[]args){yangHUi ynewyangHUi();ListListIntegerrety.generate(5);System.out.println(ret);}