JAVA 数据结构链表操作循环链表
JAVA链表操作:循环链表
主要分析示例:
一、单链表循环链表
二、双链表循环链表
其中单链表节点和双链表节点类和接口ICommOperate<T>与上篇一致,这里不在赘述。参考:JAVA链表操作:单链表和双链表https://www.nhooo.com/article/95113.htm
一、单链表循环链表
packageLinkListTest; importjava.util.HashMap; importjava.util.Map; publicclassSingleCycleLinkListimplementsICommOperate<SNode>{ privateSNodehead=newSNode("HEAD");//公共头指针,声明之后不变 privateintsize=0; publicintgetSize(){ returnthis.size; } /* *链表插入,每次往末端插入,判定末端的标准为next是否指向head **/ @Override publicbooleaninsertNode(SNodenode){ booleanflag=false; initLinkList();//初始化链表 if(this.size==0){//空链表 this.head.setNextNode(node); node.setNextNode(this.head); }else{ SNodecurrent=this.head; while(current.getNextNode()!=this.head){//找到末端节点 current=current.getNextNode(); } current.setNextNode(node); node.setNextNode(this.head);//循坏链表,尾节点指向head } this.size++; flag=true; returnflag; } /* *插入链表指定位置pos,从1开始,而pos大于size则插入链表末端 **/ @Override publicbooleaninsertPosNode(intpos,SNodenode){ booleanflag=true; SNodecurrent=this.head.getNextNode(); initLinkList();//初始化链表 if(this.size==0){//链表为空 this.head.setNextNode(node); node.setNextNode(this.head);//循坏链表,尾节点指向head this.size++; }elseif(this.size<pos){//pos位置大于链表长度,插入末端 insertNode(node); }elseif(pos>0&&pos<=this.size){//链表内节点 //1、找到要插入pos位置节点和前节点,node将插入两个节点之间 intfind=0; SNodepreNode=this.head;//前节点 SNodecurrentNode=current;//当前节点 while(find<pos-1&¤tNode!=this.head){ preNode=current;//前节点后移 currentNode=currentNode.getNextNode();//当前节点后移 find++; if(find<pos-1&¤tNode!=this.head){//未结束寻找节点前,后移前节点 current=current.getNextNode(); } } //System.out.println(preNode); //System.out.println(currentNode); //2、插入节点 preNode.setNextNode(node); node.setNextNode(currentNode); this.size++; }else{ System.out.println("位置信息错误"); flag=false; } returnflag; } privatevoidinitLinkList(){ if(size==0){ this.head.setNextNode(this.head); } } /* *指定链表的节点pos,删除对应节点。方式:找到要删除节点的前后节点,进行删除,下标从1开始 **/ @Override publicbooleandeleteNode(intpos){ booleanflag=false; SNodecurrent=this.head.getNextNode(); if(pos<=0||pos>this.size||current==this.head){ System.out.println("位置信息错误或链表无信息"); }else{ //1、找到要删除节点的前后节点 intfind=0; SNodepreNode=this.head;//前节点 SNodenextNode=current.getNextNode();//后节点 while(find<pos-1&&nextNode!=this.head){ preNode=current;//前节点后移 nextNode=nextNode.getNextNode();//后节点后移 find++; if(find<pos-1&&nextNode!=this.head){//未结束找节点前,后移"前节点" current=current.getNextNode(); } } //System.out.println(preNode); //System.out.println(nextNode); //2、删除节点 preNode.setNextNode(nextNode); System.gc();//回收删除节点 this.size--; flag=true; } returnflag; } /* *指定链表的节点pos,修改对应节点,下标从1开始 **/ @Override publicbooleanupdateNode(intpos,Map<String,Object>map){ booleanflag=false; SNodenode=getNode(pos,map);//获得相应位置pos的节点 if(node!=null){ Stringdata=(String)map.get("data"); node.setData(data); flag=true; } returnflag; } /* *找到指定链表的节点pos,下标从1开始 **/ @Override publicSNodegetNode(intpos,Map<String,Object>map){ SNodecurrent=this.head.getNextNode(); if(pos<=0||pos>this.size||current==this.head){ System.out.println("位置信息错误或链表不存在"); returnnull; } intfind=0; while(find<pos-1&¤t!=this.head){ current=current.getNextNode(); find++; } returncurrent; } /* *打印链表 **/ @Override publicvoidprintLink(){ intlength=this.size; if(length==0){ System.out.println("链表为空!"); return; } SNodecurrent=this.head.getNextNode(); System.out.println("总共有节点数:"+length+"个"); intfind=0; while(current!=this.head){ System.out.println("第"+(++find)+"个节点:"+current); current=current.getNextNode(); } } publicstaticvoidmain(String[]args){ SingleCycleLinkListscll=newSingleCycleLinkList(); SNodenode1=newSNode("节点1"); SNodenode2=newSNode("节点2"); SNodenode3=newSNode("节点3"); SNodenode4=newSNode("节点4"); SNodenode5=newSNode("节点5"); SNodenode6=newSNode("插入指定位置"); //scll.insertPosNode(scll.getSize()+1,node1); //scll.insertPosNode(scll.getSize()+1,node2); //scll.insertPosNode(scll.getSize()+1,node3); //scll.insertPosNode(scll.getSize()+1,node4); //scll.insertPosNode(scll.getSize()+1,node5); scll.insertNode(node1); scll.insertNode(node2); scll.insertNode(node3); scll.insertNode(node4); scll.insertNode(node5); System.out.println("*******************输出链表*******************"); scll.printLink(); System.out.println("*******************获得指定链表节点*******************"); intpos=2; System.out.println("获取链表第"+pos+"个位置数据:"+scll.getNode(pos,null)); System.out.println("*******************向链表指定位置插入节点*******************"); intpos1=3; System.out.println("将数据插入第"+pos1+"个节点:"); scll.insertPosNode(pos1,node6); scll.printLink(); System.out.println("*******************删除链表指定位置节点*******************"); intpos2=3; System.out.println("删除第"+pos2+"个节点:"); scll.deleteNode(pos2); scll.printLink(); System.out.println("*******************修改链表指定位置节点*******************"); intpos3=3; System.out.println("修改第"+pos3+"个节点:"); Map<String,Object>map=newHashMap<>(); map.put("data","thisisatest"); scll.updateNode(pos3,map); scll.printLink(); } }
二、双链表循环链表
packageLinkListTest; importjava.util.HashMap; importjava.util.Map; publicclassDoubleCycleLinkListimplementsICommOperate<DNode>{ privateDNodehead=newDNode("HEAD");//公共头指针,声明之后不变 privateintsize=0;//记录链表节点数量 publicintgetSize(){ returnthis.size; } /* *链表插入,每次往末端插入,判定末端的标准为next是否指向head **/ @Override publicbooleaninsertNode(DNodenode){ booleanflag=false; initLinkList();//初始化链表 DNodecurrent=this.head; if(this.size==0){//空链表 this.head.setNextNode(node); node.setPriorNode(this.head); node.setNextNode(this.head); }else{//链表内节点 while(current.getNextNode()!=this.head){//找到末端节点 current=current.getNextNode(); } current.setNextNode(node); node.setPriorNode(current); node.setNextNode(this.head);//循坏链表,尾节点指向head } this.size++; flag=true; returnflag; } /* *插入链表指定位置pos,从1开始,而pos大于size则插入链表末端 **/ @Override publicbooleaninsertPosNode(intpos,DNodenode){ booleanflag=true; initLinkList();//初始化链表 DNodecurrent=this.head.getNextNode(); if(this.size==0){//链表为空 this.head.setNextNode(node); node.setPriorNode(this.head); node.setNextNode(this.head); this.size++; }elseif(pos>this.size){//pos位置大于链表长度,插入末端 insertNode(node); }elseif(pos>0&&pos<=this.size){//链表内节点 //1、找到要插入位置pos节点,插入pos节点当前位置 intfind=0; while(find<pos-1&¤t.getNextNode()!=this.head){ current=current.getNextNode(); find++; } //2、插入节点 if(current.getNextNode()==this.head){//尾节点 node.setPriorNode(current); node.setNextNode(this.head); current.setNextNode(node); }elseif(current.getNextNode()!=this.head){//中间节点 node.setPriorNode(current.getPriorNode()); node.setNextNode(current); current.getPriorNode().setNextNode(node); current.setPriorNode(node); } this.size++; }else{ System.out.println("位置信息错误"); flag=false; } returnflag; } privatevoidinitLinkList(){ if(size==0){ this.head.setNextNode(this.head); this.head.setPriorNode(this.head); } } /* *指定链表的节点pos,删除对应节点。方式:找到要删除节点的前后节点删除,下标从1开始 **/ @Override publicbooleandeleteNode(intpos){ booleanflag=false; DNodecurrent=this.head.getNextNode(); if(pos<=0||pos>this.size||current==this.head){ System.out.println("位置信息错误或链表不存在"); }else{ //1、找到要删除位置pos节点 intfind=0; while(find<pos-1&¤t.getNextNode()!=this.head){ current=current.getNextNode(); find++; } //2、删除节点 if(current.getNextNode()==this.head){//尾节点 current.getPriorNode().setNextNode(this.head); }elseif(current.getNextNode()!=this.head){//中间节点 current.getPriorNode().setNextNode(current.getNextNode()); current.getNextNode().setPriorNode(current.getPriorNode()); } System.gc();//回收删除节点 this.size--; flag=true; } returnflag; } /* *指定链表的节点pos,修改对应节点,下标从1开始 **/ @Override publicbooleanupdateNode(intpos,Map<String,Object>map){ booleanflag=false; DNodenode=getNode(pos,map); if(node!=null){ Stringdata=(String)map.get("data"); node.setData(data); flag=true; } returnflag; } /* *找到指定链表的节点pos,下标从1开始 **/ @Override publicDNodegetNode(intpos,Map<String,Object>map){ DNodecurrent=this.head.getNextNode(); if(pos<=0||pos>this.size||current==this.head){ System.out.println("位置信息错误或链表不存在"); returnnull; } intfind=0; while(find<pos-1&¤t!=this.head){ current=current.getNextNode(); find++; } returncurrent; } /* *打印链表 **/ @Override publicvoidprintLink(){ intlength=this.size; if(length==0){ System.out.println("链表为空!"); return; } DNodecurrent=this.head.getNextNode(); intfind=0; System.out.println("总共有节点数:"+length+"个"); while(current!=this.head){ System.out.println("第"+(++find)+"个节点:"+current); current=current.getNextNode(); } } publicstaticvoidmain(String[]args){ DoubleCycleLinkListdcll=newDoubleCycleLinkList(); DNodenode1=newDNode("节点1"); DNodenode2=newDNode("节点2"); DNodenode3=newDNode("节点3"); DNodenode4=newDNode("节点4"); DNodenode5=newDNode("节点5"); DNodenode6=newDNode("插入指定位置"); dcll.insertPosNode(10,node1); dcll.insertPosNode(10,node2); dcll.insertPosNode(8,node3); dcll.insertPosNode(88,node4); dcll.insertPosNode(8,node5); //dcll.insertNode(node1); //dcll.insertNode(node2); //dcll.insertNode(node3); //dcll.insertNode(node4); //dcll.insertNode(node5); System.out.println("*******************输出链表*******************"); dcll.printLink(); System.out.println("*******************获得指定链表节点*******************"); intpos=2; System.out.println("获取链表第"+pos+"个位置数据:"+dcll.getNode(pos,null)); System.out.println("*******************向链表指定位置插入节点*******************"); intpos1=dcll.getSize()+1; System.out.println("将数据插入第"+pos1+"个节点:"); dcll.insertPosNode(pos1,node6); dcll.printLink(); System.out.println("*******************删除链表指定位置节点*******************"); intpos2=7; System.out.println("删除第"+pos2+"个节点:"); dcll.deleteNode(pos2); dcll.printLink(); System.out.println("*******************修改链表指定位置节点*******************"); intpos3=3; System.out.println("修改第"+pos3+"个节点:"); Map<String,Object>map=newHashMap<>(); map.put("data","thisisatest"); dcll.updateNode(pos3,map); dcll.printLink(); } }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!