如何将自定义链表转换为数组？

Question

我必须实现一个方法：

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

来自 java.util Interface List

正如我提到的，我必须传递一个数组，将其转换为单链表，排序它，然后返回数组。

在 Node 类中，我需要处理这个问题：

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;
}

我是不是找错了树，或者有人可以帮我解决这个问题吗？很抱歉，如果这是提出此类问题的错误地方。

Answer 1

以下代码将创建单个链接列表并将其复制回数组的新副本。对于这种排序，您需要确保使“E”类型实现具有可比性。
一种方法是将“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 ;
    }

Answer 2

明显的错误答案：

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

我认为构建和排序您完全跳过的链表有一些副作用？或者也许返回应该是排序列表，而不是数组，可能是排序列表强制回数组？

Answer 3

我希望这能满足您的需求：

/**
 * 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;
}

正如我在代码中所说，我不知道如何正确实例化泛型类。有人可以纠正我吗？