How can I remove an element in a repeated list?

Java code: writing NaturalMergeSort code to sort chain of elements

• Write a natural merge sort code that sorts a chain of elements. Should be a member of the class chain: /** linked implementation of LinearList */ package dataStructures; import java.util.*; public class Chain implements LinearList { // data members protected ChainNode firstNode; protected int size; // constructors /** create a list that is empty */ public Chain(int initialCapacity) { // the default initial values of firstNode and size // are null and 0, respectively } public Chain() {this(0);} // methods /** @return true iff list is empty */ public boolean isEmpty() {return size == 0;} /** @return current number of elements in list */ public int size() {return size;} /** @throws IndexOutOfBoundsException when * index is not between 0 and size - 1 */ void checkIndex(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException ("index = " + index + " size = " + size); } /** @return element with specified index * @throws IndexOutOfBoundsException when * index is not between 0 and size - 1 */ public Object get(int index) { checkIndex(index); // move to desired node ChainNode currentNode = firstNode; for (int i = 0; i < index; i++) currentNode = currentNode.next; return currentNode.element; } /** @return index of first occurrence of theElement, * return -1 if theElement not in list */ public int indexOf(Object theElement) { // search the chain for theElement ChainNode currentNode = firstNode; int index = 0; // index of currentNode while (currentNode != null && !currentNode.element.equals(theElement)) { // move to next node currentNode = currentNode.next; index++; } // make sure we found matching element if (currentNode == null) return -1; else return index; } /** Remove the element with specified index. * All elements with higher index have their * index reduced by 1. * @throws IndexOutOfBoundsException when * index is not between 0 and size - 1 * @return removed element */ public Object remove(int index) { checkIndex(index); Object removedElement; if (index == 0) // remove first node { removedElement = firstNode.element; firstNode = firstNode.next; } else { // use q to get to predecessor of desired node ChainNode q = firstNode; for (int i = 0; i < index - 1; i++) q = q.next; removedElement = q.next.element; q.next = q.next.next; // remove desired node } size--; return removedElement; } /** Insert an element with specified index. * All elements with equal or higher index * have their index increased by 1. * @throws IndexOutOfBoundsException when * index is not between 0 and size */ public void add(int index, Object theElement) { if (index < 0 || index > size) // invalid list position throw new IndexOutOfBoundsException ("index = " + index + " size = " + size); if (index == 0) // insert at front firstNode = new ChainNode(theElement, firstNode); else { // find predecessor of new element ChainNode p = firstNode; for (int i = 0; i < index - 1; i++) p = p.next; // insert after p p.next = new ChainNode(theElement, p.next); } size++; } /** convert to a string */ public String toString() { StringBuffer s = new StringBuffer("["); // put elements into the buffer ChainNode currentNode = firstNode; while(currentNode != null) { if (currentNode.element == null) s.append("null, "); else s.append(currentNode.element.toString() + ", "); currentNode = currentNode.next; } if (size > 0) s.delete(s.length() - 2, s.length()); // remove last ", " s.append("]"); // create equivalent String return new String(s); } /** create and return an iterator */ public Iterator iterator() {return new ChainIterator();} /** chain iterator */ private class ChainIterator implements Iterator { // data member private ChainNode nextNode; // constructor public ChainIterator() {nextNode = firstNode;} // methods /** @return true iff list has a next element */ public boolean hasNext() {return nextNode != null;} /** @return next element in list * @throws NoSuchElementException * when there is no next element */ public Object next() { if (nextNode != null) { Object elementToReturn = nextNode.element; nextNode = nextNode.next; return elementToReturn; } else throw new NoSuchElementException("No next element"); } /** unsupported method */ public void remove() { throw new UnsupportedOperationException ("remove not supported"); } } Linearlist code is: /** interface for linear lists */ package dataStructures; public interface LinearList { public boolean isEmpty(); public int size(); public Object get(int index); public int indexOf(Object theElement); public Object remove(int index); public void add(int index, Object theElement); public String toString(); } Format should be similar to: public class ChainWithNaturalMergeSort extends Chain { static ArrayQueue queue = new ArrayQueue(10); static int numberOfSegments; public ChainWithNaturalMergeSort(int initialCapacity) { super(initialCapacity);} public ChainWithNaturalMergeSort() { super();} public void naturalMergeSort() { Insert code here }

• Answer:

  Thanks for your question. Merge sort is one of my favorite algorithms, actually; it's the first sorting algorithm I learned. It's almost miraculous how simple its expression is: sort(list) = if (list has 1 or 0 elements return list) else sort(first half of list) sort(second half of list) merge the results. There are a number of merge-sort algorithms and demos on the net, one animation you might enjoy is at: http://www2.ics.hawaii.edu/~qizhang/ics665/mergesort.html Anyway, it is remarkable that if you look at the code to this algorithm, it is hard even to see where it compares elements! Most of the code just handles trivialities, the comparison is hidden away. By the way I assume you are familiar with the java "Comparable" interface. This is interface that objects which can be compared implement. So, when you sort something, you have to make sure all your objects implement "Comparable". By the way, for general coding practice, I recommend the site http://www.topcoder.com . It has various programming competitions and it's a good way to learn Java (or other languages). OK: To compile the code, put the ChainWithNaturalMergeSort class source below in the dataStructures directory, the same directory where Chain is. The compile it just as you would compile Chain.java. I've included a main() method that lets you test the implementation. I find it's always a good idea to have one of these. To run the class, from one directory above dataStructures, just type something like: java dataStructures.ChainWithNaturalMergeSort a b c... Here are examples of how I ran it: java dataStructures.ChainWithNaturalMergeSort The initial value of the chain is: [] The sorted value of the chain is: [] java dataStructures.ChainWithNaturalMergeSort one-element The initial value of the chain is: [one-element] The sorted value of the chain is: [one-element] java dataStructures.ChainWithNaturalMergeSort one-element two-element The initial value of the chain is: [one-element, two-element] The sorted value of the chain is: [one-element, two-element] java dataStructures.ChainWithNaturalMergeSort two-element one-element The initial value of the chain is: [two-element, one-element] The sorted value of the chain is: [one-element, two-element] java dataStructures.ChainWithNaturalMergeSort p q r s t u v f g h i j k l m n o w x y z a b c d e The initial value of the chain is: [p, q, r, s, t, u, v, f, g, h, i, j, k, l, m, n, o, w, x, y, z, a, b, c, d, e] The sorted value of the chain is: [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z] Feel free to ask any questions and good luck. package dataStructures; import java.util.Iterator; public class ChainWithNaturalMergeSort extends Chain { //constructors public ChainWithNaturalMergeSort(int initialCapacity) { super(initialCapacity);} public ChainWithNaturalMergeSort() { super();} //methods /** Sort the list according to the natural order of its elements. Each element must implement the Comparator interface. This uses a merges sort algorithm */ public void naturalMergeSort() { int nelements=size(); // number of elements if (nelements==0||nelements==1)return; // Already sorted Comparable[] array=new Comparable[nelements]; //first we get everything into an array, //since these are a bit more efficient and easier to work with Iterator iter= iterator(); //Iterate through each element of the Chain for (int i=0;i<nelements;++i) // Set the value of the i'th array element to the i'th element in the chain. array[i]=(Comparable)(iter.next()); //Note that this will give a "class cast exception" if the elements are not Comparables. sort(array); //merge sort the value ChainNode current=firstNode; //and set each element in the chain to the sorted value. for (int i=0;i<nelements;++i){ current.element=array[i]; current=current.next; } } //This is the routine that actually does the work. It takes an array of Comparables and sorts it using merge sort. void sort(Comparable[] array){ int nelements=array.length; if (nelements<=1)return; // already sorted int midpoint=nelements/2; // get the first half Comparable[] array1=new Comparable[midpoint]; // we partition the array Comparable[] array2=new Comparable[nelements-midpoint]; System.arraycopy(array,0,array1,0,array1.length); // set up the first array System.arraycopy(array,array1.length,array2,0,array2.length); //set up the second array sort(array1); //recursively sort the first array sort(array2); //recursively sort the second array //The following line simply merges the sorted arrays we've made, and then copies the result back to the original array. System.arraycopy(merge(array1,array2), 0, array, 0, nelements); } //This function takes two sorted arrays as input and returns the sorted array that has all the elements of each array Comparable[] merge(Comparable[] array1, Comparable[] array2){ Comparable[] result=new Comparable[array1.length+array2.length]; //will hold the result int nextinsert=0; // next element of result to set int nextarray1element=0; // next element of array1 to check int nextarray2element=0; // next element of array2 to check while(nextinsert<result.length){ //while there are still more elements if (nextarray1element>=array1.length) // have we finished array1? if so, add an array2 element result[nextinsert++]=array2[nextarray2element++]; else if (nextarray2element>=array2.length) //similarly for array2 result[nextinsert++]=array1[nextarray1element++]; //The following line is the only place in the whole class we actually compare anything!! //we see if the next array1 element is smaller than or equal to according to the natural order to the next array2 element, // and if so we add it to the result. //Because we use "<=0" not "<0" this is a "stable sort" which means it doesn't change the order of equal elements in the input. else if (array1[nextarray1element].compareTo(array2[nextarray2element])<=0) result[nextinsert++]=array1[nextarray1element++]; else result[nextinsert++]=array2[nextarray2element++]; } return result; } //The next routine is simply used for testing. To test, just call the function main with arguments the strings to be sorted. public static void main(String[]argv){ ChainWithNaturalMergeSort chain=new ChainWithNaturalMergeSort(); for (int i=0;i<argv.length;++i) chain.add(i,argv[i]); System.out.println("The initial value of the chain is: \n"+chain); chain.naturalMergeSort(); System.out.println("The sorted value of the chain is: \n"+chain); } }