JAVA 鏈表操作：循環鏈表，java表操作循環

JAVA 鏈表操作：循環鏈表，java表操作循環

主要分析示例：

一、單鏈表循環鏈表

二、雙鏈表循環鏈表

其中單鏈表節點和雙鏈表節點類和接口ICommOperate<T>與上篇一致，這裡不在贅述。參考：JAVA鏈表操作：單鏈表和雙鏈表http://www.cnblogs.com/xiaoxing/p/5969133.html

一、單鏈表循環鏈表

package LinkListTest;

import java.util.HashMap;
import java.util.Map;

public class SingleCycleLinkList implements ICommOperate<SNode> {
    private SNode head = new SNode("HEAD") ; // 公共頭指針，聲明之後不變
    private int size = 0 ;
    public int getSize() {
        return this.size;
    }
    
    /*
     * 鏈表插入，每次往末端插入,判定末端的標准為next是否指向head
     * */
    @Override
    public boolean insertNode(SNode node) {
        boolean flag = false  ; 
        
        initLinkList() ; // 初始化鏈表
        if( this.size==0 ){  // 空鏈表
            this.head.setNextNode(node) ;
            node.setNextNode(this.head) ;
        }else{
            SNode current = this.head ;
            while( current.getNextNode()!=this.head ){ // 找到末端節點
                current = current.getNextNode() ;
            }
            current.setNextNode(node) ;
            node.setNextNode(this.head) ; // 循壞鏈表，尾節點指向head
        }
        this.size++ ;
        flag = true ;
        
        return flag;
    }
    
    /*
     * 插入鏈表指定位置pos,從1開始,而pos大於size則插入鏈表末端
     * */
    @Override
    public boolean insertPosNode(int pos, SNode node) {
        boolean flag = true ; 
        SNode current = this.head.getNextNode() ;
        
        initLinkList() ;// 初始化鏈表
        if( this.size==0 ){                 // 鏈表為空
            this.head.setNextNode(node) ;
            node.setNextNode(this.head) ;// 循壞鏈表，尾節點指向head
            this.size++ ;
        }else if( this.size<pos ){           // pos位置大於鏈表長度，插入末端
            insertNode(node) ;
        }else if( pos>0 && pos<=this.size ){ // 鏈表內節點
            // 1、找到要插入pos位置節點和前節點，node將插入兩個節點之間
            int find = 0;
            SNode preNode = this.head; // 前節點
            SNode currentNode = current; // 當前節點
            while( find<pos-1 && currentNode!=this.head ){
                preNode = current ;                          // 前節點後移
                currentNode = currentNode.getNextNode() ; // 當前節點後移
                find++ ;
                if( find<pos-1 && currentNode!=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 ;
        }
        
        return flag;
    }

    private void initLinkList(){
        if( size==0 ){
            this.head.setNextNode(this.head);
        }
    }
    
    /*
     * 指定鏈表的節點pos，刪除對應節點。方式：找到要刪除節點的前後節點,進行刪除,下標從1開始
     * */
    @Override
    public boolean deleteNode(int pos) {
        boolean flag = false; 
        SNode current = this.head.getNextNode() ;
        if( pos<=0 || pos>this.size || current==this.head ){
            System.out.println("位置信息錯誤或鏈表無信息");
        }else{
            // 1、找到要刪除節點的前後節點
            int find = 0;
            SNode preNode = this.head; // 前節點
            SNode nextNode = 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 ;
        }
        
        return flag;
    }
    
    /*
     * 指定鏈表的節點pos，修改對應節點,下標從1開始
     * */
    @Override
    public boolean updateNode(int pos, Map<String, Object> map) {
        boolean flag = false ;
        SNode node = getNode(pos, map); // 獲得相應位置pos的節點
        if( node!=null ){
            String data = (String) map.get("data") ;
            node.setData(data);
            flag = true ;
        }
        return flag;
    }
    
    /*
     * 找到指定鏈表的節點pos,下標從1開始
     * */
    @Override
    public SNode getNode(int pos, Map<String, Object> map) {
        SNode current = this.head.getNextNode() ;
        if( pos<=0 || pos>this.size || current==this.head ){
            System.out.println("位置信息錯誤或鏈表不存在");
            return null;
        }
        int find = 0 ;
        while( find<pos-1 && current!=this.head ){
            current = current.getNextNode() ;
            find++ ;
        }
        return current;
    }

    /*
     * 打印鏈表
     * */
    @Override
    public void printLink() {
        int length = this.size ;
        if( length==0 ){
            System.out.println("鏈表為空！");
            return ;
        }
        SNode current = this.head.getNextNode() ;
        System.out.println("總共有節點數: " + length +" 個");
        int find = 0 ;
        while( current!=this.head ){
            System.out.println("第 " + (++find) + " 個節點 ：" + current);
            current=current.getNextNode() ;
        }
    }
    
    public static void main(String[] args) {
        SingleCycleLinkList scll = new SingleCycleLinkList() ;
        SNode node1 = new SNode("節點1");
        SNode node2 = new SNode("節點2");
        SNode node3 = new SNode("節點3");
        SNode node4 = new SNode("節點4");
        SNode node5 = new SNode("節點5");
        SNode node6 = new SNode("插入指定位置");
//        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("*******************獲得指定鏈表節點*******************");
        int pos = 2 ;
        System.out.println("獲取鏈表第 "+pos+" 個位置數據 ："+scll.getNode(pos, null));
        
        System.out.println("*******************向鏈表指定位置插入節點*******************");
        int pos1 = 3 ;
        System.out.println("將數據插入第"+pos1+"個節點：");
        scll.insertPosNode(pos1, node6) ;
        scll.printLink();
        
        System.out.println("*******************刪除鏈表指定位置節點*******************");
        int pos2 = 3 ;
        System.out.println("刪除第"+pos2+"個節點：");
        scll.deleteNode(pos2) ;
        scll.printLink();
        
        System.out.println("*******************修改鏈表指定位置節點*******************");
        int pos3 = 3 ;
        System.out.println("修改第"+pos3+"個節點：");
        Map<String, Object> map = new HashMap<>() ;
        map.put("data", "this is a test") ;
        scll.updateNode(pos3, map) ;
        scll.printLink();
    }

}

 二、雙鏈表循環鏈表

package LinkListTest;

import java.util.HashMap;
import java.util.Map;

public class DoubleCycleLinkList implements ICommOperate<DNode>{
    private DNode head = new DNode("HEAD"); // 公共頭指針，聲明之後不變
    private int size = 0 ; // 記錄鏈表節點數量
    
    public int getSize() {
        return this.size;
    }
    
    /*
     * 鏈表插入，每次往末端插入,判定末端的標准為next是否指向head
     * */
    @Override
    public boolean insertNode(DNode node) {
        boolean flag = false ; 
        
        initLinkList() ; // 初始化鏈表
        DNode current = 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 ;
        
        return flag;
    }
    
    /*
     * 插入鏈表指定位置pos,從1開始,而pos大於size則插入鏈表末端
     * */
    @Override
    public boolean insertPosNode(int pos, DNode node) {
        boolean flag = true; 
        
        initLinkList() ; // 初始化鏈表
        DNode current = this.head.getNextNode() ;
        if( this.size==0 ){                     // 鏈表為空
            this.head.setNextNode(node) ;
            node.setPriorNode(this.head);
            node.setNextNode(this.head) ;
            this.size++ ;
        }else if( pos>this.size ){                 // pos位置大於鏈表長度，插入末端
            insertNode(node) ;
        }else if( pos>0 && pos<=this.size ){    // 鏈表內節點
            // 1、找到要插入位置pos節點,插入pos節點當前位置
            int find = 0;
            while( find<pos-1 && current.getNextNode()!=this.head ){
                current = current.getNextNode() ;
                find++ ;
            }
            // 2、插入節點
            if( current.getNextNode()==this.head ){ // 尾節點
                node.setPriorNode(current);
                node.setNextNode(this.head);
                current.setNextNode(node);
            } else if( 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 ;
        }
        return flag;
    }

    private void initLinkList(){
        if( size==0 ){
            this.head.setNextNode(this.head);
            this.head.setPriorNode(this.head);
        }
    }
    
    /*
     * 指定鏈表的節點pos，刪除對應節點。方式：找到要刪除節點的前後節點刪除,下標從1開始
     * */
    @Override
    public boolean deleteNode(int pos) {
        boolean flag = false; 
        DNode current = this.head.getNextNode() ;
        if( pos<=0 || pos>this.size || current==this.head ){
            System.out.println("位置信息錯誤或鏈表不存在");
        }else{
            // 1、找到要刪除位置pos節點
            int find = 0;
            while( find<pos-1 && current.getNextNode()!=this.head ){
                current = current.getNextNode() ;
                find++ ;
            }
            // 2、刪除節點
            if( current.getNextNode()==this.head ){ // 尾節點
                current.getPriorNode().setNextNode(this.head) ;
            } else if( current.getNextNode()!=this.head ) {  //中間節點
                current.getPriorNode().setNextNode(current.getNextNode()) ;
                current.getNextNode().setPriorNode(current.getPriorNode()) ;
            } 
            System.gc(); // 回收刪除節點
            this.size-- ;
            flag = true ;
        }
        return flag;
    }
    
    /*
     * 指定鏈表的節點pos，修改對應節點,下標從1開始
     * */
    @Override
    public boolean updateNode(int pos, Map<String, Object> map) {
        boolean flag = false ;
        DNode node = getNode(pos, map);
        if( node!=null ){
            String data = (String) map.get("data") ;
            node.setData(data);
            flag = true ;
        }
        return flag;
    }

    /*
     * 找到指定鏈表的節點pos,下標從1開始
     * */
    @Override
    public DNode getNode(int pos, Map<String, Object> map) {
        DNode current = this.head.getNextNode() ;
        if( pos<=0 || pos>this.size || current==this.head ){
            System.out.println("位置信息錯誤或鏈表不存在");
            return null;
        }
        int find = 0 ;
        while( find<pos-1 && current!=this.head ){
            current = current.getNextNode() ;
            find++ ;
        }
        return current;
    }

    /*
     * 打印鏈表
     * */
    @Override
    public void printLink() {
        int length = this.size ;
        if( length==0 ){
            System.out.println("鏈表為空！");
            return ;
        }
        DNode current = this.head.getNextNode() ;
        int find = 0 ; 
        System.out.println("總共有節點數: " + length +" 個");
        while( current!=this.head ){
            System.out.println("第 " + (++find) + " 個節點 ：" + current);
            current=current.getNextNode() ;
        }
    }
    
    public static void main(String[] args) {
        DoubleCycleLinkList dcll = new DoubleCycleLinkList() ;
        DNode node1 = new DNode("節點1");
        DNode node2 = new DNode("節點2");
        DNode node3 = new DNode("節點3");
        DNode node4 = new DNode("節點4");
        DNode node5 = new DNode("節點5");
        DNode node6 = new DNode("插入指定位置");
        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("*******************獲得指定鏈表節點*******************");
        int pos = 2 ;
        System.out.println("獲取鏈表第 "+pos+"個位置數據 ："+dcll.getNode(pos, null));
        
        System.out.println("*******************向鏈表指定位置插入節點*******************");
        int pos1 = dcll.getSize()+1 ;
        System.out.println("將數據插入第"+pos1+"個節點：");
        dcll.insertPosNode(pos1, node6) ;
        dcll.printLink();
        
        System.out.println("*******************刪除鏈表指定位置節點*******************");
        int pos2 = 7 ;
        System.out.println("刪除第"+pos2+"個節點：");
        dcll.deleteNode(pos2) ;
        dcll.printLink();
        
        System.out.println("*******************修改鏈表指定位置節點*******************");
        int pos3 = 3 ;
        System.out.println("修改第"+pos3+"個節點：");
        Map<String, Object> map = new HashMap<>() ;
        map.put("data", "this is a test") ;
        dcll.updateNode(pos3, map) ;
        dcll.printLink();
    }
}