算法之循环链表

循环链表：单链表的基础上，首位相应，形成一个环，取第一项和末尾项，时间复杂度为0（1）

意义：感觉不到太大的意义，主要是任意位置能够对整表进行循环遍历，

code:

package math;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.UUID;

import math.SingleLinkList.Obj;

/**
 * @author bin
 * date : 15/1/5
 * desc : 实现循环链表 由于写了单链表 这个就简单写下，主要是单链表闭合成一个环 
 *        让最后一项 内存地址 指向首项
 */
public class LoopLinkList {
    public List l;
    public int currentLen;//当前长度
    public Map m;
    public String address;//
    
    public class Obj{
        private String address;
        private Object obj;
        
        public Obj(String str,Object o){
            this.address = str;
            this.obj = o;
        }
        public Obj(){
            
        }
    }        
    public LoopLinkList(){
        this.currentLen = 0;
        //初始化，内存地址
        this.address = this.getUUid();
        //初始化map
        m = new HashMap();
    }
    public void creatList(int i){
        this.check(i);
        Random r = new Random();
        String tempStr = new String();
        String uuid = new String();
        int rint;
        for (int j = 0; j < i; j++) {
            rint =  r.nextInt(40);
            System.out.println(rint);
            uuid  = this.getUUid();
            Obj o = new Obj(uuid, rint);
            if(j == 0){
            //当前的记录
                m.put(address, o);
            }else if(j == i-1){
                o = new Obj(address,rint);
                m.put(tempStr, o);
            }else{
                m.put(tempStr, o);
            }
            tempStr = uuid;
            currentLen = currentLen+1;
            }
        } 
    public Object getEle(int i){
        this.check(i);
        int start = 0;
        Obj o = new Obj();
        if(currentLen < 1 ){
            throw new RuntimeException("不合理得参数");
        }else if(i > currentLen){
            throw new RuntimeException("越界错误");
        }else{
            while (start <= i-1) {
                if(start == 0){
                    o = (LoopLinkList.Obj) m.get(address);
                }else{
                    //System.out.println(m.get(o.address).toString());
                    o = (LoopLinkList.Obj) m.get(o.address);
                }
                start++;                                                                     
            }
            return o;
        }
    }
    
    public void loop(Obj o){
        int count = 0;
        System.out.println("-------------------");
        System.out.println(o.obj);
        while (count < currentLen-1) {
            o = (Obj) m.get(o.address);
            System.out.println(o.obj);
            count++;
        }
    }
    public static void main(String[] args) {
        LoopLinkList l = new LoopLinkList();
        l.creatList(10);
        LoopLinkList loop = new LoopLinkList();
        Obj o = loop.new Obj();
        o = (Obj) l.getEle(4);
        l.loop(o);
        
    }
        public void check(int i){
            if(i<=0){
                throw new RuntimeException("不合法得参数");
        } 
    }
     
    //生成唯一得地址信息
    public String getUUid(){
        UUID uuid = UUID.randomUUID();
        return uuid.toString();
    }
}

结果，

13
27
23
31
23
14
6
27
31
27
-------------------
31
23
14
6
27
31
27
13
27
23