Anyones know how to implement radix sort on linkedlist in java?
I tried and got error
package layout; import java.util.Scanner; /* Class Node */ class Node { protected int data; protected Node next, prev; /* Constructor */ public Node() { data = 0; next = null; } /* Constructor */ public Node( int d, Node n ) { data = d; next = n; } /* Function to set link to next node */ public void setLinkNext( Node n ) { next = n; } /* Funtion to get link to next node */ public Node getLinkNext() { return next; } /* Function to set data to node */ public void setData( int d ) { data = d; } /* Function to get data from node */ public int getData() { return data; } } /* Class linkedList */ class linkedList { protected Node start, end; public int size; /* Constructor */ public linkedList() { start = null; end = null; size = 0; } /* Function to check if list is empty */ public boolean isEmpty() { return start == null; } /* Function to get size of list */ public int getSize() { return size; } public Node getNodeStart() { return start; } public Node getNodeEnd() { return end; } /* Function to insert element */ public void insertHead( int val ) { Node p = new Node( val, null ); if ( start == null ) { start = p; end = start; } else { p.setLinkNext( start ); start = p; } size++; } void insertTail( int val ) { Node p = new Node( val, null );; if ( start == null ) { start = p; end = start; } else { end.setLinkNext( p ); end = p; } p.setLinkNext( null ); size++; } void Output() { Node p = start; while ( p != null ) { System.out.print( p.getData() + " <-> " ); p = p.getLinkNext(); } } /* Function to convert List to a String */ public String display() { String ListString01 = ""; Node ptr = start; ListString01 = ListString01 + ptr.getData() + ", "; if ( size == 0 ) { ListString01 = "List is empty"; return ListString01; } ptr = start.getLinkNext(); while ( ptr.getLinkNext() != null ) { ListString01 = ListString01 + ptr.getData() + ", "; ptr = ptr.getLinkNext(); } ListString01 = ListString01 + ptr.getData() + ", "; return ListString01; } void initList( linkedList List ) { List.start = List.end = null; } int findMax() { Node p; p = new Node(); p = this.start; int max = p.data; while ( p != null ) { if ( max < p.data ) max = p.data; p = p.getLinkNext(); } return max; } int countDigit( int n ) { int count = 0; while ( n > 0 ) { n = n / 10; count++; } return count; } int getMaxDigit() { int max = this.findMax(); return countDigit( max ); } void appendList( linkedList List2 ) { if ( this.start == null ) this.start = List2.start; else { this.end.setLinkNext( List2.start ); if ( List2.start != null ) this.end = List2.end; } } int getDigit( int n, int t ) { long temp = 1; for ( int i = 0; i < n; i++ ) temp = temp * 10; return (int) ( ( t / temp ) % 10 ); } void sendToBox( int n, linkedList temp[] ) { Node p; p = new Node(); p = this.start; while ( p != null ) { temp[ getDigit( n, p.data ) ].insertTail( p.data ); p = p.getLinkNext(); } } void radixSort() { linkedList[] temp = new linkedList[ 10 ]; int i; if ( this.start == this.end ) return; for ( i = 0; i < 10; i++ ) temp[ i ] = new linkedList(); int num = this.getMaxDigit(); for ( i = 0; i < num; i++ ) { sendToBox( i, temp ); for ( int j = 0; j < 10; j++ ) { this.appendList( temp[ j ] ); initList( temp[ j ] ); } } } @SuppressWarnings( "deprecation") public static void main( String arg[] ) { linkedList list01; list01 = new linkedList(); int k = 10; int a[] = { 12, 23, 34, 78, 91, 44, 52, 68, 79, 77 }; for ( int i = 0; i < k; i++ ) { list01.insertHead( a[ i ] ); } System.out.println( "oOo m01.Output(); oOo" ); list01.Output(); System.out.println( " " ); System.out.println( "oOo m01.display( ); oOo" ); String s01 = list01.display(); System.out.println( s01 ); list01.radixSort(); System.out.println( "oOo List after sort; oOo" ); String s02 = list01.display(); System.out.println( s02 ); } }
Output:
oOo m01.Output(); oOo
77 <-> 79 <-> 68 <-> 52 <-> 44 <-> 91 <-> 78 <-> 34 <-> 23 <-> 12 <->
oOo m01.display( ); oOo
77, 79, 68, 52, 44, 91, 78, 34, 23, 12,
oOo List after sort; oOo
77, 79, 68, 52, 44, 91, 78, 34, 23, 12, 91, 52, 12, 23, 44, 34, 77, 68, 78, 79, 12, 12, 23, 23, 34, 34, 44, 44, 52, 52, 68, 68, 77, 79, 78, 77, 78, 79, 91, 91,