Friday, December 6, 2013

a simple circular linked list in Java















class Node {
    public int data;
    public Node next;
}

class LinkList {
    private Node head;
    // LinkList constructor
    public LinkList() {        head = null;    }

    // Returns true if list is empty
    public boolean isEmpty() {        return head == null;    }

    // Inserts a new Node at the head of the list
    public void insert(int a) {
        Node node = new Node();
        node.data = a;
        node.next = null;
       
        if (head == null)
        {
            head = node;
            node.next = node;  // a snake bites its tail.
        }   
        else
        {
            Node last = getLastNode();
            // insert node at the end of list.
            last.next = node;
            node.next = head; // bite head again.
        }
    }

    // tops the Node at the head of the list
    public void top() {   
        if (!isEmpty())
        {
            Node last = getLastNode();
            if (head == last)
                head=null;
            else
            {
                head = head.next;   
                last.next = head;
            }   
        }
        else
            System.out.println("empty!!!");
    }

    private Node getLastNode()
    {
        // Find the last node.
        Node cursor = head;
        Node last = head;
        while (cursor != null)
        {
            if (cursor.next == head) { last = cursor; break;}
            cursor = cursor.next;
        }
       
        return last;
    }
   
    // Prints list data
    public void printList() {
        Node cursor = head;
        System.out.print("List:  ");
        while (cursor != null) {
            System.out.print(cursor.data + " ");
            cursor = cursor.next;
            if (cursor == head) break;
        }

        System.out.println("");
    }

    public static void main(String[] args) {
        LinkList list = new LinkList();
        list.insert(1);
        list.insert(2);
        list.insert(3);
       
        list.printList();
        list.top();
        list.top();
        list.top();
        list.top();
        list.printList();
        list.insert(3);
        list.insert(2);
        list.insert(3);
        list.printList();
    }
}

No comments:

Post a Comment