6.JAVA-链表实例

 1.实现链表的步骤

• 1).实现node节点类(用来保存链表中每个节点的数据,以及下一个节点成员)
• 2).实现linklist链表类(用来封装node节点类,和用户实现交互)
• 3).在linklist类里,实现添加,删除,根据要查的node数据来找表中的序号,根据要查的序号来找对应的node数据.
• 4).在linklist类里,实现toarrays方法,用来取出链表中的node数据的数组

 

2.类的实现

/*节点类*/ 
class node
{
    private string data;        //节点保存的数据
    private node next;            //下个节点

    public node(string data){
        this.data = data;
    }
    
    public string getdata()
    {
        return data;
    }
    public void setdata(string data)
    {
        this.data = data;
    }
    
    public node getnext()
    {
        return next;
    }
    public void setnext(string data)
    {
        this.next = new node(data);
    }
    
    /*description: 添加节点
     *return     :  
     */ 
    public void addnode(string data)
    {
        if(getnext()!=null)
        {
            this.next.addnode(data);
        }
        else
        {
            this.setnext(data);
        }
    }
    
    /*description: 获取节点数据
     *return     :  
     */ 
    public string getdata(int index)
    {
        string ret =null ;
        if(index == 0)    //如果递归到0,则返回当前数据
        {
            ret=data;
        }
        else            //否则继续递归查找
        {
            ret=this.next.getdata(--index);
        }
        return ret;
    }

    /*description:  递归地查找data位于链表哪个序号
     *return     :  -1(表示未找到)      
     */ 
    public int findindex(string data,int index)
    {
        if(this.data.equals(data))    //已找到
        {
            return index;
        }    
        else if (getnext()==null)    //未找到
        {
            return -1;
        }

        return this.next.findindex(data,++index);

    }

    /*description:  递归地查找data,并删除
     *data: 要找的data
     *prenode:    上个节点,如果为null则当前位于表头
     *index: 表示当前位于链表哪个序号
     *return  :  -1(表示未找到) 0~(len-1) (表示data位于链表哪个序号)         
     */ 
    public int deldata(string data,node prenode,int index)
    {
        int ret = -1;
        
        if(this.data.equals(data))    //删除
        {
            prenode.next = this.next;
            return index;
        }
        else if (getnext()==null)    //未找到
        {
            return ret;
        }

        return this.next.deldata(data,this,++index);
    }

}

/*链表类*/
class linklist
{
    private node next;        //负责管理的节点
    private int len;        //统计节点长度
    
    public linklist(string data)
    {
        next = new node(data);
        len =1;
    }

    /*description:  添加一个节点数据
     *return     :      
     */ 
    public void adddata(string data)
    {
        this.next.addnode(data);
        len++;    
    } 
    

    /*description:  删除一个节点数据
     *return     :  -1(未找到要删除的数据) 0~(len-1) (表示data位于链表哪个序号)         
     */ 
    public int deldata(string data)
    {
        int ret=-1;    
        if(len>=0)                //链表有数据
        {
            if(this.next.getdata().equals(data))    //删除表头需要特殊处理
            {
                this.next = this.next.getnext();
                ret = 0;
            }
            else
              ret = next.deldata(data,this.next,1);    
        }

        if(ret!= -1)    //已删除
        {
            len--;
        }

        return ret;
    } 


    /*description:  根据index找到对应的节点数据
     *return     :  返回节点数据    
     */ 
    public string getnodedata(int index)
    {
        string ret=null;
        if(index>=0 && index<(len))
        {
            ret = next.getdata(index);
        }
        return ret;
    }

    /*description:  根据data查找节点node位于链表哪个序号
     *return     :  -1(表示未找到)  0~(len-1) (表示data位于链表哪个序号)         
     */ 
    public int findnodeindex(string data)        
    {
        int ret=-1;        
        if(len>=0)                //链表有数据
        {
            ret = next.findindex(data,0);  //从序号0开始找
        }
        return ret;
    }        

    /*description:  将链表中所有的节点数据转为数组
     *return     :       
     */ 
    public string[] toarrays()
    {
        node tmp=this.next; 
        
        string[] arr = new string[len];
        

        for(int i=0; i< len; i++)
        {
            arr[i] = tmp.getdata();
            tmp = tmp.getnext();
        }
        return arr;
    }

    public int length()
    {
        return len;
    }
}

 

3.测试代码

public class test{
                public static void main(string args[]){
                linklist list = new linklist("小a");

                //添加节点数据
                list.adddata("小b");
                list.adddata("小c");
                list.adddata("小d");
                list.adddata("小e");

 
                //打印节点数据
                system.out.println("print node data:");
                for(int i=0;i<list.length();i++)
                {
                        system.out.println(list.getnodedata(i));
                }
                system.out.println("---------------------");

                //查找节点数据的序号
                system.out.println("小a的index位于:"+list.findnodeindex("小a"));
                system.out.println("小d的index位于:"+list.findnodeindex("小d"));
                system.out.println("小f的index位于:"+list.findnodeindex("小f"));  //返回-1,表示未找到

                //删除节点数据
                system.out.println("删除小a,并打印小a之前的位置:"+list.deldata("小a"));
                system.out.println("删除小e,并打印小e之前的位置:"+list.deldata("小e"));
                //通过数组打印数据
                system.out.println("\r\nprint node data by toarrays() :");
                string[] arr=list.toarrays();
                for(int i=0;i<arr.length;i++)
                {
                        system.out.println(arr[i]);
                }
                system.out.println("---------------------");
       }       
}

运行打印:

 

 

 

ps:这样写,只是简单的实现某个数据类型的链表.在后续章节,会学习如何让链表来自动匹配多态数据类型