Sorting in linked-list...

[melicaster]

I need the node sorted (selection sort) whenever the data is entered front or end or deleted front or end. How to get it sort automatically everytime user entered a data?

countItems() doesn't seem worked to the selection sort...

This is my Node class. Mostly no problem...

public class Node
{
    int num;
    Node next;
    
    Node()
    {
        num = 0;
        next = null;
    }
    
    Node(int num, Node next)
    {
        this.num = num;
        this.next = next;
    }
}

This is the List class. Most problems occured here...

import java.util.*;

public class List
{
    Node head;
    List()
    {
        this.head = null;
    }
    
    public void addfront (int d)
    {
        Node newrec = new Node (d,null);
        
        newrec.next = head;
        head = newrec;
    }
    
    public  void addend(int d)
    {
        Node newNode = new Node(d,null);
        Node temp;
        
        if(head == null)
        {
            head = newNode;
        }
        else
        {
            temp = head;
            while(temp.next != null)
            {
                temp = temp.next;
            }
            temp.next = newNode;
        }
    }   
    
    public void deletefront()
    {
        Node temp = new Node();
        temp = head;
        if (temp == null)
        {
            showMessageDialog(null,"No Item in the list");
        }
        else
        {
            head = head.next;
            showMessageDialog(null,"Node Deleted!");
        }
    }
    
    public void deleteend()
    {
        Node current, temp = null;
        current = head;
        
        if (current == null)
        {
            showMessageDialog(null,"No Item in the list");
        }
        else if (head.next != null)
        {     
            while (current.next != null)
            {
                temp = current;
                current = current.next;
            }
            
            temp.next = null;
            
            showMessageDialog(null,"Node Deleted!");
        }
        else
        {
            head = null;
            showMessageDialog(null,"Node Deleted!");
        }
    }
    
    public void display()
    {
        Node current = head;
        String output = "";
        while (current != null)
        {
            output += current.num + "\n";
            current = current.next;
        }
        showMessageDialog(null, output + "\n\n DATA Displayed!");
    }
    
    public int countItems()
    {
        Node current = head;
        int count = 0;
        
        while(current != null)
        {
            ++count;
            current = current.next;
        }
        
        showMessageDialog(null, count);
        
        return count;
    }
    
    public void selectionSort()
    {
        Node current, a, previous, position;
        position = new Node();
        position.next = head;
        head = position;
        
        while (position.next != null)
        {
            current = previous = position.next;
            a = position.next;
            
            while (a != null)
            {
                if (a.countItems() < current.countItems())
                {
                    current = a;
                    while (previous.next != current)
                    {
                        previous = previous.next;
                    }
                }
                
                a = a.next;
            }
            
            if (current != previous)
            {
                Node t = position.next;
                swap(position, t, previous, current);
            }
            
            position = position.next;
        }
        head = head.next;
    }
}

This is the client class...

import static javax.swing.JOptionPane.*;

public class Client
{
    public static void main(String args[])
    {
        int choice, num;
        
        List list = new List();
        
        do
        {
            String menu = "1. Add node (Front)\n2. Add node (End)\n3. Delete node (Front)\n4. Delete Node (End)\n5. Display node\n6. Number of number inserted.\n7. Exit";
            
            choice = Integer.parseInt(showInputDialog(menu + "\nEnter choice"));
            
            switch (choice)
            {
                case 1:
                num = Integer.parseInt(showInputDialog("Enter data:"));
                list.addfront(num);
                break;
                
                case 2:
                num = Integer.parseInt(showInputDialog("Enter data:"));
                list.addend(num);
                break;
                
                case 3:
                list.deletefront();
                break;
                
                case 4:
                list.deleteend();
                
                case 5:
                list.display();
                break;
                
                case 6:
                list.countItems();
                break;
                
                case 7:
                break;
            }
        } while (choice != 7);
    }
}

Any helps would be greatly appreciated... You might asked why .util.linkedlist is available and I didn't use it. Because I am not allowed to.

Thanks in advanced.

[NormR1]

Can you explain how your code works? Does it preserve its order as new nodes are added?
Or can the user insert nodes anywhere and then call a sort method to sort the current list?

How to get it sort automatically everytime user entered a data?

I don't see how this would work. If the user wants a node inserted at the front of the list and you automatically sort it, then the inserted node may not be at the front of the list any longer.

[melicaster]

Sorry for my bad English. I think an user can insert the node anywhere and then call a soft method to sort the current list. And yes, it preserve it's order as new nodes are added.

[NormR1]

Do you have an algorithm for sorting a linked list?
Its been a long time since I had to do it, I can't come up with one.

[NormR1]

Here's an idea: If your add() method inserts the added node in the position so that the list stays sorted, then to sort the list, create a new list by moving the first node from the old list to the new one and then continue removing nodes from the old list and adding them to the new list. Since the add method preserves order the new list will be in order. Then set head of list to the new list.