1.List的介绍
在集合框架中，List是一个集合，继承于Connection
Connection中所包含的方法有；
Connection继承于Interable接口
List 的官方文档
站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。
2.常见的方法
List中的方法含有很多
其中的方法很多，但是常用的方法如下；
3.List的使用
注意；List是个接口，不能被直接的实例化
即以下的操作是不对的
List接口实例化的必须是类，所以我们可以使用List接口去实例化调用List接口的类，例如ArrayList，LinkedList。
二.线性表
线性表（linear list）是 n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列 …
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
三.顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
publicclassList{privateint[]array;privateintsize;privatestaticfinalintDEFAULT_CAPACITY=10;// 默认构造方法publicList(){// 创建默认容量的数组array=newint[DEFAULT_CAPACITY];// 初始化元素个数为0size=0;}//判断顺序表是否为满，如果满则true， 否则 falsepublicbooleanisFull(){returnarray.length==size;}//将顺序表中的数组长度扩大为原来的2倍publicvoidgrow(){this.array=Arrays.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(inti=size;i>=pos;i--){array[i]=array[i-1];}array[pos]=data;size++;}//判断添加的pos位置是否合法privatevoidcheckPos(intpos)throwsPosIllegal{if(pos<0||pos>size){thrownewPosIllegal("pos位置不合法");}}// 判定是否包含某个元素publicbooleancontains(inttoFind){for(inti=0;i<size;i++){if(array[i]==toFind){returntrue;}}returnfalse;}// 查找某个元素对应的位置publicintindexOf(inttoFind){for(inti=0;i<size;i++){if(array[i]==toFind){returni;}}return-1;}// 获取 pos位置的元素publicintget(intpos){if(pos<0||pos>size){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;}inta=indexOf(toRemove);for(inti=a;i<size-1;i++){array[i]=array[i+1];}size--;}// 获取顺序表长度publicintsize(){returnsize;}// 清空顺序表publicvoidclear(){}// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的publicvoiddisplay(){for(inti=0;i<size;i++){System.out.print(array[i]+" ");}}}四、ArrayList的简介
在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下
（1）ArrayList是以泛型方式实现的，使用时必须要先实例化
（2）ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
（3）ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
（4）ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
（5）和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
（6）ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
1.ArrayList的使用
ArrayList 的构造
publicstaticvoidmain(String[]args){//第一种，无参数的构造方法Listlist1=newArrayList();//第二种，带容量参数的构造方法Listlist2=newArrayList(10);list2.add(10);list2.add(20);list2.add(30);//注；此处没有指代具体哪种类型的话，默认为Object，因此hello也可以存放list2.add("hello");//第三种，将其他集合当做参数存放Listlist3=newArrayList(list2);//此时，list3中含有list2中的全部元素}ArrayList 的常见操作
ArrayList 中的方法有很多，但是常用的方法有以下几种
publicstaticvoidmain(String[]args){Listlist=newArrayList();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数组List<String>ret=list.subList(0,4);System.out.println(ret);list.clear();System.out.println(list.size());}ArrayList的遍历
ArrayList的遍历有已下几种遍历方法；for循环+下标，foreach，使用迭代器
publicstaticvoidmain(String[]args){List<Integer>list=newArrayList();list.add(10);list.add(20);list.add(30);list.add(40);list.add(50);for(inti=0;i<list.size();i++){System.out.println(list.get(i)+" ");}for(Integerinteger:list){System.out.println(integer+" ");}//使用迭代器Iterator<Integer>it=list.listIterator();while(it.hasNext()){System.out.print(it.next()+" ");}System.out.println();}ArrayList 的相关练习
1.洗牌算法
（一副新牌，四种花色（♥，♦，♠，♣），数值分别为1–13，经过一系列的洗牌之后，分别发给三个人每人5张（轮流抓牌），最后展示剩余牌和三人手里的牌）
publicclassCard{privateStringsuit;//花色privateintrank;//牌面值publicCard(Stringsuit,intrank){this.suit=suit;this.rank=rank;}@OverridepublicStringtoString(){/*return "Card{" + "suit='" + suit + '\'' + ", rank=" + rank + '}';*/returnString.format("[%s %d]",suit,rank);}}publicclassCardDemo{publicstaticfinalString[]suits={"♥","♠","♣","♦"};//买来一副新牌publicList<Card>buyCard(){List<Card>cardList=newArrayList<>(52);for(inti=1;i<=13;i++){for(intj=0;j<4;j++){intrank=i;Stringsuit=suits[j];Cardcard=newCard(suit,rank);cardList.add(card);}}returncardList;}//洗牌publicvoidshuffle(List<Card>cardList){Randomrandom=newRandom();for(inti=cardList.size()-1;i>0;i--){intindex=random.nextInt(i);swap(cardList,i,index);}}privatevoidswap(List<Card>cardList,inti,intj){/* Card tmp = cardList[i]; cardList[i] = cardList[j]; cardList[j] = tmp; */Cardtmp=cardList.get(i);cardList.set(i,cardList.get(j));cardList.set(j,tmp);}//分别发牌publicList<List<Card>>play(List<Card>cardList){List<Card>hand0=newArrayList<>();List<Card>hand1=newArrayList<>();List<Card>hand2=newArrayList<>();List<List<Card>>hand=newArrayList<>();hand.add(hand0);hand.add(hand1);hand.add(hand2);for(inti=0;i<5;i++){for(intj=0;j<3;j++){Cardcard=cardList.remove(0);//怎么把对应的牌 放到对应的人的手里面hand.get(j).add(card);}}returnhand;}}publicclassTest{publicstaticvoidmain(String[]args){CardDemocardDemo=newCardDemo();//1. 买52张牌List<Card>cardList=cardDemo.buyCard();System.out.println("刚买回来的牌：");System.out.println(cardList);//2. 洗牌cardDemo.shuffle(cardList);System.out.println("洗过的牌:");System.out.println(cardList);//3. 3个人每个人轮流发牌5张List<List<Card>>ret=cardDemo.play(cardList);for(inti=0;i<ret.size();i++){System.out.println("第"+(i+1)+"个牌："+ret.get(i));}System.out.println("剩下的牌：");System.out.println(cardList);}2.杨辉三角
杨辉三角
classSolution{publicList<List<Integer>>generate(intnumRows){List<List<Integer>>ret=newArrayList<>();List<Integer>list1=newArrayList<>();list1.add(1);//添加了第一行的数组ret.add(list1);//处理剩下行的数组for(inti=1;i<numRows;i++){//开头元素List<Integer>list2=newArrayList<>();list2.add(1);//中间List<Integer>prelist=ret.get(i-1);for(intj=1;j<i;j++){intval1=prelist.get(j);intval2=prelist.get(j-1);list2.add(val1+val2);}//结尾list2.add(1);ret.add(list2);}returnret;}}
