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

Question

我必须实现一个方法:

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

来自 java.util Interface List<E>

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

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