链表基本概念1.链表的基本形式2.单向链表的完整实现认识链表链表=可变长的对象数组，属于动态对象数组的范畴链表是一种最简单的线性数据结构，之所以会存在有数据结构问题主要是解决亮点：存储的数据不受限制，查找速度快对象数组有那些问题呢？对象数组可以保存一组对象方便开发对象数组的长度固定，而且数据的删除，修改，增加处理麻烦所有的开发之中都100%不可能避免掉对象数组的使用正因为如此现在如果要想让其可以编写出便于维护的代码，那么就需要实现一个动态对象数组，那么就可以使用链表完成但是现在如果要想实现动态的对象数组，要考虑两个问题：为了适应于所有的开发要求，此对象数组要求可以保存所有的数据类型，那么一首选Object类型为了可以保存多个数据，需要采用引用的方式来进行保存，但是数据本身是不可能保存顺序的所以需要有一个可以负责保存顺序的类来包装这个数据分析结论：保存数据为了方便使用Object数据本身不包含有先后的逻辑关系，所以将数据封装在一个Node类，负责关系的维护范例：定义出如下的一个类
classNode{//b表示定义的节点privateObjectdata;//要保存的数据privateNodenext;//保存下一个节点publicNode(Objectdata){//有数据才可以保存节点this.data=data;}publicvoidsetNext(Nodenext){//设置节点this.next=next;}publicNodegetNext(){//取得节点returnthis.next;}}publicclasslinkedList{publicstaticvoidmain(Stringargs[]){}}完成节点之后，下面就可以进行节点的基本使用了范例：采用循环的方式操作节点
classNode{//b表示定义的节点privateObjectdata;//要保存的数据privateNodenext;//保存下一个节点publicNode(Objectdata){//有数据才可以保存节点this.data=data;}publicvoidsetNext(Nodenext){//设置节点this.next=next;}publicNodegetNext(){//取得节点returnthis.next;}publicObjectgetData(){returnthis.data;}}publicclasslinkedList{publicstaticvoidmain(Stringargs[]){//1.定义各自独立的操作节点Noderoot=newNode("火车头");Noden1=newNode("车厢1");Noden1=newNode("车厢2");//2.设置彼此间的关系root.setNext(n1);n1.setNext(n2);//3.输出NodecurrentNode=root;//从根节点开始取出数据while(currentNode!=null){System.out.println(currentNode.getData());//取出数据currentNode=currentNode.getNext();//下一个节点}}}以上的操作如果使用循环并不方便。最好的做法是递归调用范例：利用递归的方式实现内容的取得
classNode{//b表示定义的节点privateObjectdata;//要保存的数据privateNodenext;//保存下一个节点publicNode(Objectdata){//有数据才可以保存节点this.data=data;}publicvoidsetNext(Nodenext){//设置节点this.next=next;}publicNodegetNext(){//取得节点returnthis.naxt;}publicObjectgetData(){returnthis.data;}}classlink{//表示一个链表操作类，利用此类来隐藏Node的节点匹配publicvoidadd(Objectobj){//向链表里面追加数据}publicvoidprint(){//输出链表中的全部数据}}publicclasslinkedList{publicstaticvoidmain(Stringargs[]){Linkall=newLink();all.add("商品1");all.add("商品2");all.add("商品3");all.print();}}用户不关心Node，用户只关心通过Link操作完成后可以取得数据范例：完善程序
classLink{//外部的程序只关心此类privateclassNode{//使用私有内部类，防止外部使用此类privateObjectdata;privateNodenext;publicNode(Objectdata){this.data=data;}}//************************************privateNoderoot;//根元素}publicclasslinkedList{publicstaticvoidmain(Stringargs[]){}}如果要开发程序，那么一定要创建自己的操作标准，那么一旦说到标准就应该想到使用接口来完成
interfaceLink{}classLinkImplimplementsLink{//外部的程序只关心此类privateclassNode{//使用私有内部类，防止外部使用此类privateObjectdata;privateNodenext;publicNode(Objectdata){this.data=data;}}//************************************privateNoderoot;//根元素}publicclasslinkedList{publicstaticvoidmain(Stringargs[]){}}在随后完善代码的过程之中，除了功能的实现之外，实际上也属于接口功能的完善实现数据增加操作publicvoidadd(Objectdata)1.需要在接口里面定义好数据增加的操作方法
interfaceLink{publicvoidadd(Objectdata);//数据增加}classLinkImplimplementsLink{//外部的程序只关心此类privateclassNode{//使用私有内部类，防止外部使用此类privateObjectdata;privateNodenext;publicNode(Objectdata){this.data=data;}}//************************************privateNoderoot;//根元素}publicclasslinkedList{publicstaticvoidmain(Stringargs[]){}}2.进行代码的实现，同样实现的过程之中LinkImpl类只关心根节点，而具体的子节点的排序都交由Node类负责处理在Link类中实现add()方法：
interfaceLink{publicvoidadd(Objectdata);//数据增加}classLinkImplimplementsLink{//外部的程序只关心此类privateclassNode{//使用私有内部类，防止外部使用此类privateObjectdata;privateNodenext;publicNode(Objectdata){this.data=data;}}//************************************privateNoderoot;//根元素publicvoidadd(Objectdata){if(data==null){//现在没有要增加的数据return;//结束调用}NodenewNode=newNode(data);//创建新的节点if(this.root==null){//保留有根节点this.root=root;}else{//应该交由Node类负责处理this.root.addNode(newNode);}}}publicclasslinkedList{publicstaticvoidmain(Stringargs[]){}}在Node类中进行数据的追加操作：
interfaceLink{publicvoidadd(Objectdata);//数据增加}classLinkImplimplementsLink{//外部的程序只关心此类privateclassNode{//使用私有内部类，防止外部使用此类privateObjectdata;privateNodenext;publicNode(Objectdata){this.data=data;}publicvoidaddNode(NodenewNode){if(this.next==null){this.next=newNode;}else{this.next.addNode(newNode);}}}//************************************privateNoderoot;//根元素publicvoidadd(Objectdata){if(data==null){//现在没有要增加的数据return;//结束调用}NodenewNode=newNode(data);//创建新的节点if(this.root==null){//保留有根节点this.root=root;}else{//应该交由Node类负责处理this.root.addNode(newNode);}}}publicclasslinkedList{publicstaticvoidmain(Stringargs[]){}}此时的代码实现过程与基本的实现是完全一样的取得保存元素个数：publicintsize()每个Link接口的对象都要保存各自的内容，所以为了方便控制保存个数，可以增加一个Link类中的属性，并且用此属性在数据成功追加之后实现自增操作在Link类中定义一个count属性，默认值为：0
interfaceLink{publicvoidadd(Objectdata);//数据增加}classLinkImplimplementsLink{//外部的程序只关心此类privateclassNode{//使用私有内部类，防止外部使用此类privateObjectdata;privateNodenext;publicNode(Objectdata){this.data=data;}publicvoidaddNode(NodenewNode){if(this.next==null){this.next=newNode;}else{this.next.addNode(newNode);}}}//************************************privateNoderoot;//根元素privateintcount=0;//当数据已经成功添加完毕之后实现计数的统计publicvoidadd(Objectdata){if(data==null){//现在没有要增加的数据return;//结束调用}NodenewNode=newNode(data);//创建新的节点if(this.root==null){//保留有根节点this.root=root;}else{//应该交由Node类负责处理this.root.addNode(newNode);}this.count++;//当节点保存完毕之后就可以进行数据增加了}}publicclasslinkedList{publicstaticvoidmain(Stringargs[]){}}而在Link接口里面追加size()的方法，同时在LinkImpl子类里面进行方法的覆写
interfaceLink{publicvoidadd(Objectdata);//数据增加publicintsize();//取得保存元素的个数publicbooleanisEmpty();//判断是否为空集合}范例：在LinkImpl类中实现此方法
interfaceLink{publicvoidadd(Objectdata);//数据增加publicintsize();//取得保存元素的个数publicbooleanisEmpty();//判断是否为空集合publicbooleancontains(Objectdata);//判断是否有指定的元素}2.在LinkImpl子类里面要通过根元素开始调用查询，所有的查询交由Node类负责在LinkImpl发出具体的查询要求之前，必须要保证有集合数据
publicbooleancontains(Objectdata){if(this.root==null){//没有集合数据returnfalse;}returnthis.root.containsNode(data);//根元素交给Node类完成}在Node类中实现数据的查询
publicObjectgetNode(intindex){//传递索引的序号if(LinkImpl.this.foot++==index){//当前的索引为要查找的索引returnthis.data;//返回当前节点对象}else{returnthis.next.getNode(index);}}在Link类中实现get()方法
publicObjectget(intindex){if(index>=this.count){//索引不存在returnnull;}this.foot=0;//查询之前执行一次清零操作returnthis.root.getNode(index);}
这种查询的模式与contains()最大的不同一个是数字索引，一个是内容修改数据：publicvoidset(intindex,Objectobj)与get()相比set()方法依然需要进行循环的判断，只不过get()索引判断成功之后会返回数据，而set()只需要用新的数据更新已有节点数据即可1.在Link接口里面创建一个新的方法publicvoidset(intindex,Objectobj)2.修改LnikImopl子类，流程与get()差别不大：在Node类里面追加一个新的setNode()方法；
publicvoidsetNode(intindex,Objectobj){if(LinkImpl.this.foot++==index){this.obj=obj;//重新保存数据}else{this.next.setNode(index,obj);}}在LinkImpl子类里面覆写set()方法，在set()方法编写的时候也需要针对于给定的索引进行验证
publicvoidset(intindex,Objectobj){if(index>=this.count){//索引不存在returnnull;}this.foot=0;//查询之前执行一次清零操作this.root.setNode(index,obj);}set()与get()方法实际上在使用时都有一个固定的条件：集合中的保存数据顺序应该为添加顺序数据删除：publicvoidremove(Objectobj)如果要进行数据的删除，那么对于整个链表而言就是节点的删除操作而节点的删除操作过程之中需要考虑的问题是什么？要删除的是根节点还是子节点问题1.要删除的是根节点：Link类处理，因为根节点有关的所有节点都应该交由Link类管理Link.root=Link.root.next2.要删除的是子节点：交由Node类负责处理删除节点的上一个节点.next=删除节点.next1.在Link接口里面创建一个新的方法publicvoidremove(Objectdata);//删除数据2.修改LnikImopl类的操作：在Node类中增加一个removeNode()的方法
//第一次：this.LinkImpl.root.next,previous=LinkImpl.root;//第二次：this.LinkImpl.root.next.next,previous=LinkImpl.root.nextpublicvoidremove(Nodeprevious,Objectdata){if(this.data.equals(data)){previous.next=this.next;//空出当前节点}else{this.next.removeNode(this,data);}}在Link类中增加新的操作：
publicvoidremove(Objectdata){if(this.contains(data)){//数据如果存在则删除if(this.root.equals(data)){//根元素为要删除的元素this.root=this.root.next;//第二个元素作为根元素}else{//不是根元素，根元素一斤判断完了this.root.next.removeNode(this.root,data);}this.count--;}}整个删除操作很好的体现了this的特性contains()和remove()方法必须有对象比较的支持，对象比较使用的就是Object类中的equals()方法清空链表：publicvoidclear()当链表中的数据不需要在使用的时候，那么可以进行清空，而清空最简单的做法就是将root设置为null1.在Link接口里面创建一个新的方法publicvoidclear();//清空链表2.直接在LinkImpl类中修改清空操作
publicvoidclear(){this.foot=null;this.count=0;//元素的保存个数清0System.gc();//回收内存空间}实际上这种代码还欠缺一个很好的内存释放问题返回数据：publicObject[]toArray()恒定的概念：链表就是动态对象数组，但是要想操作链表中的数据，那么最好的做法是将其转换为对象数组返回所以这个时候就需要针对数据做递归处理1.在Link接口里面定义返回对象数组的方法publicObject[]toArray()2.修改LnikImopl子类由于Node类需要操作链表数据读取，所以应该在LinkImpl子类里面应该提供有一个对象数组的属性publicObjectretData[]=null;在LinkImpl子类里面覆写toArray()方法，并且要根据长度开辟数组空间
publicObject[]toArray(){if(this.root==null){returnnull;}this.retData=newObject[this.count];this.foot=0;this.root.toArrayNode();returnthis.retData;}
在Node类里面实现数据的保存操作
publicvoidtoArrayNode(){LinkImpl.this.retData[LinkImpl.this.foot++]=this.data;if(this.next!=null){this.next.toArrayNode();}}不过以上的设计都没有考虑过性能问题
publicObject[]toArray(){if(this.root==null){//现在没有数据returnnewObject[0];//没有数据返回}this.retData=newObject[this.count];//根据已有的数据个数开辟数组个数this.foot=0;//脚标重置this.root.toArrayNode();//交给Node类负责returnthis.retData;}3.真正获得数据的过程（节点迭代过程）应该有Node类负责
//第1次调用：this=LinkImpl.root9//第2次调用：this=LinkImpl.root.naxtpublicvoidtoArrayNode(){//递归调用LinkImpl.this.retData[LinkImpl.this.foot++]=this.data;if(this.naxt!=null){//还有下一个节点this.naxt.toArrayNode();}}综合实战：宠物商店接口实际上是属于某几类事物的抽象，也就是说在整个的定义结构上，接口标准应该优先于类定义出来，而后类按照指定的接口标准进行实现如果说现在有这样的一个案例要求：定义一个宠物商店，在这个宠物商店里面可以实现宠物的上架，下架，关键字查询现在假设宠物里面只包含两个信息（名字，年龄），而后要求通过类的结构关系描述出本程序宠物商店应该是一个程序类，因为宠物商店可能有很多种，但是其具备的特征肯定只有一个，而后宠物商店只与宠物标准有关（符合此标准的可能有多种宠物类型）而宠物商店里面需要保存有多中宠物信息（不知道个数的对象数组，应该采用链表实现）1.应该建立宠物的标准服务接口
interfacePet{publicStringgetName();publicintgetAge();}2.定义宠物商店，宠物尚待年不关心具体的宠物类型，只关心宠物标准
classPetShop{privateIlinkallPets=newLinkImpl();//动态对象数组publicvoidadd(Petpet){//追加的是宠物this.allPets.add(pet);//宠物信息追加}publicvoiddelete(Petpet){//删除宠物信息this.allPets.remove(pet);//equals()支持}publicILinksearch(StringkeyWord){//返回查询结果ILinkresult=newLinkImpl();//查询结果Objectdata[]=this.allPets.toArray();//变为对象数组返回for(intx=0;x classDog{//狗privateStringname;privateintage;publicDog(Stringname,intage){this.name=name;this.age=age;}publicbooleanequals(Objectobj){if(this==obj){returntrue;}if(obj==null){returnfalse;}if(!(objinstanceofDog)){returnfalse;}Dogpet=(Dog)obj;returnthis.name.equals(pet.name)&&this.age==pet.age;}publicStringgetName(){returnthis.name;}publicintgetAge(){returnthis.age;}publicStringtoString(){return"【宠物狗】name="+this,name+",age="+this.age;}}classCat{privateStringname;privateintage;publicCta(Stringname,intage){this.name=name;this.age=age;}publicbooleanequals(Objectobj){if(this==obj){returntrue;}if(obj==null){returnfalse;}if(!(objinstanceofCat)){returnfalse;}Catpet=(Cat)obj;returnthis.name.equals(pet.name)&&this.age==pet.age;}publicStringgetName(){returnthis.name;}publicintgetAge(){returnthis.age;}publicStringtoString(){return"【宠物猫】name="+this,name+",age="+this.age;}}4.测试 publicclasslinkedList{publicstaticvoidmain(Stringargs[]){PetShopshop=newPetShop();//宠物商店准备好了shop.add(newDog("狗子",1));shop.add(newDog("二狗子",1));shop.add(newCat("喵喵",1));shop.add(newCat("小瞄",1));shop.delete(newDog("二狗子",1));//删除操作ILinkresult=shop.search("瞄");Objectdata[]=result.toArray();for(intx=0;x