How do I turn my custom linked list into an array?

Question

I have to implement a method:

E[] toArray(E[] a) // Pass an array, convert to singly linked list, then return the array. 

from java.util Interface List<E>

As I mentioned, I have to pass an array, convert it to a singly linked list, sort it, then return the array.

In the Node class I have this to work with:

public Node(E v, Node<E> next) {
    // pre: v is a value, next is a reference to remainder of list
    // post: an element is constructed as the new head of list
    data = v;
    nextElement = next;
}

public Node(E v) {
    // post: constructs a new tail of a list with value v
    this(v,null);
}

public Node<E> next() {
    // post: returns reference to next value in list
    return nextElement;
}

public void setNext(Node<E> next)  {
    // post: sets reference to new next value
    nextElement = next;
}

public E value() {
    // post: returns value associated with this element
    return data;
}

public void setValue(E value) {
    // post: sets value associated with this element
    data = value;
}

Am I barking up the wrong tree or can someone help me with this here? Sorry if this is the wrong place for such questions.

Answer 1

Obvious wrong answer:

    E[] toArray(E[] a)
    { return a; }  // Prove I didn't make the linked list.

I assume there are some side effect to constructing and sorting the linked list that you completely skipped? Or maybe the return is supposed to be the sorted list, not the array, possibly the sorted list coerced back into an array?

Answer 2

I hope this does what you want:

/**
 * You need to pass in the class of the object you are creating
 * because you can't instantiate a generic class.
 */
public static <E> E[] toArray(E[] a, Class<E> clazz) {
    Node<E> root = null;
    Node<E> prev = null;
    Node<E> curr = null;

    for (E e : a) {
        curr = new Node<E>(e);
        if (prev != null) {
            prev.setNext(curr);
        }
        else {
            root = curr;
        }
        prev = curr;
    }

    curr =  root;

    // Cast is unsafe. I don't know a better way to do this.
    E[] newArray = (E[]) Array.newInstance(clazz, a.length);
    int i = 0; 
    while (curr != null) {
        newArray[i] = curr.value();
        curr = curr.next();
        i++;
    }

    return newArray;
}

As I say in the code, I don't know how to correctly instantiate a generic class. Can someone correct me?

Answer 3

The following code will create the single linked list and copy that back to new copy of the array. For the sort you need to make sure you make the \"E"\ type implementes comparable. One way is to change the generic declarator of \"E"\, to <E extends Comparable<? super E>>.

    E[] toArray(E[] a)
    {
        E[] result ;
        Class<?> type ;
        Node<E> head, temp, current ;

        /*
         * Makes a copy of the original array
         */
        type = a.getClass().getComponentType() ;
        result = (E[])java.lang.reflect.Array.newInstance(type, a.length);
        for(int idx = 0; idx < a.length; idx++)
            result[idx] = a[idx] ;

        /*
         * Sort the array (selection copy)
         */
        for(int idx = 0; idx < result.length; idx++)
        {
            int best = idx ;
            for(int jdx = idx + 1; jdx < result.length; jdx++)
            {
                if (result[best].compareTo(result[jdx]) > 0)
                {
                    best = jdx ;
                }
            }
            // swap
            if (best != idx)
            {
                E temporal = result[idx] ;
                result[idx] = result[best] ;
                result[best] = temporal ;
            }
        }

        /*
         * Compose the single linked list (SORTED)
         */
        head = new Node<E>(null, null) ;

        // Create the single linked list
        current = head ;
        for(E element : result)
        {
            temp = new Node<E>(element, null) ;
            current.setNext(temp) ;
            current = current.next();
        }

        /*
         * Copy the single linked list to the array 
         * (Not needed, added just for educational purpose,
             * the result array is already SORTED)
         */

        current = head.next ;
        // copies the values to the result array
        for(int index = 0; current != null ; current = current.next)
            result[index++] = current.value();

        return result ;
    }