Java Help - sorting a linked list

Author

sorting a linked list

Asembereng

2007-01-20, 7:09 pm

Hi i want to sort my linked list of int as a data type. how can i do
that..
here are the codes so far..

class UTGLLElement {
public int myData; // data item

public UTGLLElement next; // next link in list
// ------------------------------------------------------------

public UTGLLElement(int data) // constructor
{
myData = data;
}

// ------------------------------------------------------------

public void displayLink() // display this link
{
System.out.print(myData + " ");
}
// ------------------------------------------------------------

} // end class UTGLLElement
// //////////////////////////////////////////////////////////////

class LinkedList {
private UTGLLElement head; // ref to head link

private UTGLLElement tail; // ref to tail link
// ------------------------------------------------------------

public LinkedList() // constructor
{
head = null; // no links on list yet
tail = null;
}

// ------------------------------------------------------------

public LinkedList(UTGLLElement[] linkArr) // constructor (array as
{ // argument)
head = null;; // initialize list
for(int j=0; j<linkArr.length; j++) // copy array
addElement( linkArr[j] ); // to list
}
// ------------------------------------------------------------

public boolean isEmpty() // true if no links
{
return head == null;
}

// ------------------------------------------------------------

public void addElement(UTGLLElement k) { // make new link
UTGLLElement previous = null; // start at first
UTGLLElement current = head;
// until end of list,
while(current != null && k.myData > current.myData)
{ // or key > current,
previous = current;
current = current.next; // go to next item
}
if(previous==null) // at beginning of list
head = k; // first --> k
else // not at beginning
previous.next = k; // old prev --> k
k.next = current; // k --> old current
}

// ------------------------------------------------------------

public void insertFirst(int myInt) // insert at front of list

{
UTGLLElement newElement = new UTGLLElement(myInt); // make new link
if (isEmpty()) // if empty list,
tail = newElement; // newLink <-- tail
newElement.next = head; // newLink --> old head
head = newElement; // head --> newLink
}

// ------------------------------------------------------------

public void insertLast(int myInt) // insert at end of list
{
UTGLLElement newLink = new UTGLLElement(myInt); // make new link
if (isEmpty()) // if empty list,
head = newLink; // head --> newLink
else
tail.next = newLink; // old tail --> newLink

tail = newLink; // newLink <-- tail
}

// ------------------------------------------------------------

public UTGLLElement del(int key){
UTGLLElement current=head;
UTGLLElement prev=head;
while(current.myData != key)
{
if(current.next == null)
return null; // didn't find it
else
{
prev = current; // go to next link
current = current.next;
}
} // found it
if(current == head) // if first link,
head = head.next; // change first
else // otherwise,
prev.next = current.next; // bypass it
return current;
}
//--------------------------------------------------------------

// public void LinkedList(UTGLLElement[] myArray){
// head = null;; // initialize list
// for(int j=0; j<myArray.length; j++) // copy array
// addElement( myArray[j] ); // to list
//
// }
//--------------------------------------------------------------

public void insertionSort(){
for(UTGLLElement current=head; current !=null;current=current.next){
System.out.print(" here "+current);
}
}

public void displayList() {
System.out.print("Linked list elements : ");
UTGLLElement current = head; // start at beginning
while (current != null) // until end of list,
{
current.displayLink(); // print data
current = current.next; // move to next link
}
System.out.println("");
}
// ------------------------------------------------------------

public UTGLLElement remove() // return & delete first link
{ // (assumes non-empty list)
UTGLLElement temp = head; // save first
head = head.next; // delete first
return temp; // return value
}
// ------------------------------------------------------------

//

} // end class LinkedList
// //////////////////////////////////////////////////////////////

class TheMain {
public static void main(String[] args) { // make a new list
LinkedList theList = new LinkedList();
theList.insertFirst(78); // insert at front
theList.insertFirst(12);
theList.insertFirst(88);
theList.insertLast(20); // insert at the back
theList.insertLast(33);
theList.insertLast(55);
theList.displayList(); // display the list
theList.del(20);
theList.insertionSort();
//theList.insertionSort();

theList.displayList(); // display again
} // end main()
} // end class Fir

// //////////////////////////////////////////////////////////////
class LIFO {
private LinkedList theList;

// -------------------------------------------------------------

public LIFO() // constructor
{
theList = new LinkedList();
}
// -------------------------------------------------------------

// -------------------------------------------------------------

}// ENDS the LIFO class

Oliver Wong

2007-01-22, 7:08 pm

"Asembereng" <mljarju84@gmail.com> wrote in message
news:1169304549.758494.199830@l53g2000cwa.googlegroups.com...
> Hi i want to sort my linked list of int as a data type. how can i do
> that..
> here are the codes so far..
>
[snip code which contains a custom linked list implementation]

Add a method to convert your linked list of int into an array int[], and
then sort the array, and then convert the array back into a linked list.

- Oliver

Sponsored Links