A
Asembereng
Hi i want to do insertion sort, merge sort and quick sort on my
linkList of ints.. do anyone have an idea how to do it??
these are the codes. And i also need to define a lifo fifo class..
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
linkList of ints.. do anyone have an idea how to do it??
these are the codes. And i also need to define a lifo fifo class..
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