6.JAVA-链表实例

2019-04-30 23:40:32来源：博客园阅读 ()

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("---------------------");
       }       
}