単方向リンク表(single LinkdList)java実現

9491 ワード

package com.important.data.struct.LinkedListSingle;

public class SingleLinkedList
{

    public static void main(String[] args)
    {
        SingleLinkedListType singleLinkedListType = new SingleLinkedListType<>();
        for(int i=0;i<5;i++){
            String temp = i+"";
            singleLinkedListType.add(temp);
        }
        System.out.println("      : ");
        System.out.println(singleLinkedListType.size());
//        System.out.println("             : ");
//        System.out.println(singleLinkedListType.get(1));
        System.out.println("    :");
        singleLinkedListType.println();

//        singleLinkedListType.add(0, "xixi");
//        singleLinkedListType.println();

//        singleLinkedListType.addFirst("kaishi");
//        singleLinkedListType.println();
//        System.out.println(singleLinkedListType.size());

//        singleLinkedListType.remove(2);
//        singleLinkedListType.println();

//        singleLinkedListType.removeTail();
//        singleLinkedListType.println();

        singleLinkedListType.reverse();
        System.out.println("          : ");
        singleLinkedListType.println();

    }

}
class SingleLinkedListType{

    //             
    private static class Node{
        public T date;  //   
        Node next;   //   
        @SuppressWarnings("unused")
        public Node(T d,Node n){
            date = d;
            next = n;
        }
        public Node(T d){
            date = d;
            next = null;
        }
    }

    private int theSize;
    private Node head;

    public SingleLinkedListType()
    {
        clear();
    }
    //  
    public void clear(){
        theSize = 0;
        head = null;
    }

    //  
    public int size(){
        return theSize;
    }

    //    
    public void add(T x){
        Node newNode = new Node(x);
        if(head == null){
            head = newNode ;
        }else {
            Node pNode = head;
            while(pNode.next!=null){
                   pNode = pNode.next;
            }
            pNode.next = newNode;
        }
        theSize++;
    }

    //    
    public void add(int index ,T x){
        checkRange(index);
        Node pNode = getNode(index);
        Node newNode = new Node(x);
        newNode.next = pNode.next;
        pNode.next = newNode;
        theSize++;
    }

    //     
    public void addFirst(T x){
        Node newNode = new Node(x);
        newNode.next = head;
        head =newNode;
        theSize++;
    }

  //  index    
    public void checkRange(int index){
        if (index<0 || index > size())
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size();
    }

    //      
    public T get(int index){
        Node pNode = getNode(index);
        return pNode.date;
    }

    //    
    public Node getNode(int index){
        checkRange(index);
        Node pNode = head;
        for(int i=0;ireturn pNode;
    }

    //     
    public void removeTail(){
        remove(size()-1);
        theSize--;
    }

    //    
    public void remove(int index){
        checkRange(index);

        Node pNode = getNode(index);
        Node temp = head;
        for(int i=0;i1;i++){
            temp = temp.next;
        }
        temp.next = pNode.next;
        pNode.next = null;
        theSize--;
    }

    //  
    public void println(){
        Node pNode = head;
        while(pNode!=null){
            System.out.print(pNode.date+" ");
            pNode = pNode.next;
        }
        System.out.println();
    }


    //    
    public void reverse(){
        Node pre = head;     //      
        Node curr = head.next;   //    
        Node next ;  //           

        while(curr!=null){
            next = curr.next;   //                      
            curr.next = pre;    //                      ,      
            pre = curr;     //                        
            curr = next;    //                       
        }
        head.next = null;   //
        head = pre;     //                        

    }


}