Arraylist与顺序表

1.List的介绍在集合框架中List是一个集合继承于ConnectionConnection中所包含的方法有Connection继承于Interable接口List 的官方文档站在数据结构的角度来看List就是一个线性表即n个具有相同类型元素的有限序列在该序列上可以执行增删改查以及变量等操作。2.常见的方法List中的方法含有很多其中的方法很多但是常用的方法如下3.List的使用注意List是个接口不能被直接的实例化即以下的操作是不对的List接口实例化的必须是类所以我们可以使用List接口去实例化调用List接口的类例如ArrayListLinkedList。二.线性表线性表linear list是 n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列 …线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。三.顺序表顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。publicclassList{privateint[]array;privateintsize;privatestaticfinalintDEFAULT_CAPACITY10;// 默认构造方法publicList(){// 创建默认容量的数组arraynewint[DEFAULT_CAPACITY];// 初始化元素个数为0size0;}//判断顺序表是否为满如果满则true 否则 falsepublicbooleanisFull(){returnarray.lengthsize;}//将顺序表中的数组长度扩大为原来的2倍publicvoidgrow(){this.arrayArrays.copyOf(this.array,2*array.length);}// 新增元素,默认在数组最后新增publicvoidadd(intdata){if(isFull()){grow();}array[this.size]data;size;}// 在 pos位置新增元素publicvoidadd(intpos,intdata){try{checkPos(pos);}catch(PosIllegale){System.out.println(pos 的位置不合法);e.printStackTrace();}if(isFull()){grow();}for(intisize;ipos;i--){array[i]array[i-1];}array[pos]data;size;}//判断添加的pos位置是否合法privatevoidcheckPos(intpos)throwsPosIllegal{if(pos0||possize){thrownewPosIllegal(pos位置不合法);}}// 判定是否包含某个元素publicbooleancontains(inttoFind){for(inti0;isize;i){if(array[i]toFind){returntrue;}}returnfalse;}// 查找某个元素对应的位置publicintindexOf(inttoFind){for(inti0;isize;i){if(array[i]toFind){returni;}}return-1;}// 获取 pos位置的元素publicintget(intpos){if(pos0||possize){return-1;}returnarray[pos];}// 给 pos位置的元素设为 valuepublicvoidset(intpos,intvalue){try{checkPos(pos);array[pos]value;}catch(PosIllegale){System.out.println(pos位置不合法);e.printStackTrace();}}//删除第一次出现的关键字keypublicvoidremove(inttoRemove){if(indexOf(toRemove)-1){return;}intaindexOf(toRemove);for(intia;isize-1;i){array[i]array[i1];}size--;}// 获取顺序表长度publicintsize(){returnsize;}// 清空顺序表publicvoidclear(){}// 打印顺序表注意该方法并不是顺序表中的方法为了方便看测试结果给出的publicvoiddisplay(){for(inti0;isize;i){System.out.print(array[i] );}}}四、ArrayList的简介在集合框架中ArrayList是一个普通的类实现了List接口具体框架图如下1ArrayList是以泛型方式实现的使用时必须要先实例化2ArrayList实现了RandomAccess接口表明ArrayList支持随机访问3ArrayList实现了Cloneable接口表明ArrayList是可以clone的4ArrayList实现了Serializable接口表明ArrayList是支持序列化的5和Vector不同ArrayList不是线程安全的在单线程下可以使用在多线程中可以选择Vector或者CopyOnWriteArrayList6ArrayList底层是一段连续的空间并且可以动态扩容是一个动态类型的顺序表1.ArrayList的使用ArrayList 的构造publicstaticvoidmain(String[]args){//第一种无参数的构造方法Listlist1newArrayList();//第二种带容量参数的构造方法Listlist2newArrayList(10);list2.add(10);list2.add(20);list2.add(30);//注此处没有指代具体哪种类型的话默认为Object因此hello也可以存放list2.add(hello);//第三种将其他集合当做参数存放Listlist3newArrayList(list2);//此时list3中含有list2中的全部元素}ArrayList 的常见操作ArrayList 中的方法有很多但是常用的方法有以下几种publicstaticvoidmain(String[]args){ListlistnewArrayList();list.add(javase);list.add(javaee);list.add(JVM);list.add(java测开);System.out.println(list);System.out.println(list.get(1));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数组ListStringretlist.subList(0,4);System.out.println(ret);list.clear();System.out.println(list.size());}ArrayList的遍历ArrayList的遍历有已下几种遍历方法for循环下标foreach使用迭代器publicstaticvoidmain(String[]args){ListIntegerlistnewArrayList();list.add(10);list.add(20);list.add(30);list.add(40);list.add(50);for(inti0;ilist.size();i){System.out.println(list.get(i) );}for(Integerinteger:list){System.out.println(integer );}//使用迭代器IteratorIntegeritlist.listIterator();while(it.hasNext()){System.out.print(it.next() );}System.out.println();}ArrayList 的相关练习1.洗牌算法一副新牌四种花色♥♦♠♣数值分别为1–13经过一系列的洗牌之后分别发给三个人每人5张轮流抓牌最后展示剩余牌和三人手里的牌publicclassCard{privateStringsuit;//花色privateintrank;//牌面值publicCard(Stringsuit,intrank){this.suitsuit;this.rankrank;}OverridepublicStringtoString(){/*return Card{ suit suit \ , rank rank };*/returnString.format([%s %d],suit,rank);}}publicclassCardDemo{publicstaticfinalString[]suits{♥,♠,♣,♦};//买来一副新牌publicListCardbuyCard(){ListCardcardListnewArrayList(52);for(inti1;i13;i){for(intj0;j4;j){intranki;Stringsuitsuits[j];CardcardnewCard(suit,rank);cardList.add(card);}}returncardList;}//洗牌publicvoidshuffle(ListCardcardList){RandomrandomnewRandom();for(inticardList.size()-1;i0;i--){intindexrandom.nextInt(i);swap(cardList,i,index);}}privatevoidswap(ListCardcardList,inti,intj){/* Card tmp cardList[i]; cardList[i] cardList[j]; cardList[j] tmp; */CardtmpcardList.get(i);cardList.set(i,cardList.get(j));cardList.set(j,tmp);}//分别发牌publicListListCardplay(ListCardcardList){ListCardhand0newArrayList();ListCardhand1newArrayList();ListCardhand2newArrayList();ListListCardhandnewArrayList();hand.add(hand0);hand.add(hand1);hand.add(hand2);for(inti0;i5;i){for(intj0;j3;j){CardcardcardList.remove(0);//怎么把对应的牌 放到对应的人的手里面hand.get(j).add(card);}}returnhand;}}publicclassTest{publicstaticvoidmain(String[]args){CardDemocardDemonewCardDemo();//1. 买52张牌ListCardcardListcardDemo.buyCard();System.out.println(刚买回来的牌);System.out.println(cardList);//2. 洗牌cardDemo.shuffle(cardList);System.out.println(洗过的牌:);System.out.println(cardList);//3. 3个人每个人轮流发牌5张ListListCardretcardDemo.play(cardList);for(inti0;iret.size();i){System.out.println(第(i1)个牌ret.get(i));}System.out.println(剩下的牌);System.out.println(cardList);}2.杨辉三角杨辉三角classSolution{publicListListIntegergenerate(intnumRows){ListListIntegerretnewArrayList();ListIntegerlist1newArrayList();list1.add(1);//添加了第一行的数组ret.add(list1);//处理剩下行的数组for(inti1;inumRows;i){//开头元素ListIntegerlist2newArrayList();list2.add(1);//中间ListIntegerprelistret.get(i-1);for(intj1;ji;j){intval1prelist.get(j);intval2prelist.get(j-1);list2.add(val1val2);}//结尾list2.add(1);ret.add(list2);}returnret;}}