Name: dgC58589 Date: 01/09/98


The toArray() function for linked lists is O(n^2).

The problem starts in toArray() in AbstractCollection. It asks for
iterator() which is implemented in AbstractList in a way such that for
a LinkedList it will allocate an ListIterator each time next() is
called on it. If one implements LinkedList.itrator() to return
listIterator() then everything works ok.

// Author: John Boyer
// Date : 26 Dec 1997
//
 
import java.io.*;
import java.lang.*;
import java.util.*;

class MyCollections extends Collections
{
    // ***********
    // my to array using listIterator
    // the code here is identicla with the one in
    // toArray() but the use of listIterator() instead
    // of iterator()

    static Object[] mta(List list)
    {
        int n = list.size();
        Object a[] = new Object[list.size()];
        ListIterator t = list.listIterator();
        for (int j=0; j<a.length; j++) {
                a[j] = t.next();
        }
        return a;
    }

    public static void sort(List list)
    {
        System.out.println("toArray " + list.size());
        long st = System.currentTimeMillis();
        // *********** use buggy toArray because of iterator()
        Object a[] = list.toArray();
        // *********** use normal implementation
        //Object a[] = mta(list);
        long en = System.currentTimeMillis();
        System.out.println("toArray took " + (en - st) + " ms. [" + ((en-st)/(double)list.size()) + "]");

        System.out.println("Sort " + list.size());
        st = System.currentTimeMillis();
        Arrays.sort(a);
        en = System.currentTimeMillis();
        System.out.println("Sort took " + (en - st) + " ms. [" + ((en-st)/(double)list.size()) + "]");

        System.out.println("Update " + list.size());
        st = System.currentTimeMillis();
        ListIterator i = list.listIterator();
        for (int j=0; j<a.length; j++)
        {
            i.next();
            i.set(a[j]);
        }
        en = System.currentTimeMillis();
        System.out.println("Update took " + (en - st) + " ms. [" + ((en-st)/(double)list.size()) + "]");
    }
}

//==========================================================================

abstract class Node implements Comparable
{
        public abstract int compareTo(Object obj);
}

//==========================================================================

class ExtLinkedList extends LinkedList
{
        public void AddAfter(Node predecessor, Node toAdd)
        {
                add(toAdd);
        }

        public Node GetFirst()
        {
return (Node) get(0);
        }

        public void sort()
        {
                MyCollections C = new MyCollections();
                C.sort(this);
        }
}

//==========================================================================

class IntNode extends Node
{
        private int V;

        public IntNode(int value)
        {
                V = value;
        }

        public int GetValue() { return V; }
        public void SetValue(int v) { V = v; }

        public int compareTo(Object obj)
        {
        IntNode operand2 = (IntNode) obj;

                if (V < operand2.V) return -1;
                if (V > operand2.V) return 1;
                return 0;
        }
}

//==========================================================================

class SortDemo
{
        ExtLinkedList theList;

        public SortDemo(int N)
        {
         IntNode last=null, temp;

                theList = new ExtLinkedList();
                for (int i = 0; i < N; i++)
                {
                        temp = new IntNode((int) (Math.random()*N));
                        theList.AddAfter(last, temp);
                        last = temp;
                }
        }

        public void Sort()
        {
                theList.sort();
        }
}

//=====================================================================

class sorttest
{
        public static void main(String args[])
        throws IOException
        {
                int N = Integer.parseInt(args[0]);

                SortDemo sortObject = new SortDemo(N);
                sortObject.Sort();
        }
}

(Review ID: 22828)
======================================================================