java - 反转链表模板类

Question

我正在尝试反转使用 java 中的内置链接列表类创建的链接列表。下面的实现是可行的吗？此外，在实际的软件工程环境中，开发人员会使用模板类还是他们自己的？谢谢!

LinkedList<String> example1 = new LinkedList<>();
example1.add("Ben");
example1.add("Sam");
example1.add("Kyle");
Object objectArr[];
String stringArr[];
objectArr =  example1.toArray();
stringArr = Arrays.copyOf(objectArr, objectArr.length, String[].class);
ArrayList<String> newList = new ArrayList<String>(Arrays.asList(stringArr));
Collections.reverse(newList);
example1.clear();
example1.addAll(newList);

Answer 1

Is the below implementation something that is viable?

实际上并不像您实现的那样，因为您需要做的就是反转 LinkedList对象正在调用 Collections.reverse(List<?> list)直接静态方法，无需创建两个 arrays和一个ArrayList然后重建LinkedList .

in an actual software engineering environment would developers use the template class or their own?

这取决于您想要实现的目标，一个巧妙的方法是使用 Java 提供给您的内容并使用 reverse()方法。但如果性能是问题

来自文档(我的重点):

public static void reverse(List<?> list) Reverses the order of the elements in the specified list. This method runs in linear time.

这意味着:列表增长得越多，时间就越长。例如，包含 10 个元素的列表所需时间是包含 5 个元素的列表所需时间的两倍，依此类推。

这里的问题是:我们能否提高性能。我不确定我是否能正确回答这个问题，但我创建了一个简单的测试来比较 3 种反转方式(当然其他用户可能对如何反转有其他改进的想法)，在这里结果是:

import java.util.Collections;
import java.util.LinkedList;

public class LinkedListReversePerformance {

    static LinkedList<String> list1 = new LinkedList<>();
    static LinkedList<String> list2 = new LinkedList<>();
    static LinkedList<String> list3 = new LinkedList<>();
    static long startTime, endTime;

    public static void main(String[] args){

        // populate the lists, each with 1 hundred thousand item!
        for(int i =0 ;i<100000; i++){
            list1.add(String.valueOf(i));
            list2.add(String.valueOf(i));
            list3.add(String.valueOf(i));
        }

        // create temporary list
        LinkedList<String> temp = new LinkedList<>();

        startTime = System.currentTimeMillis();
        // run for loop to add the items from list1 to temp in reverse order
        for(int i=9999; i>=0; i--){
            temp.add(list1.get(i));
        }
        // clear list1 then add temp
        list1.clear();
        list1.addAll(temp);
        endTime = System.currentTimeMillis();

        System.out.println("Using For Loop and clearing old list: " + (endTime-startTime) + " Millisecond");


        // re-initialize temp and populate it again in reverse order
        temp = new LinkedList<>();

        startTime = System.currentTimeMillis();
        for(int i=9999; i>=0; i--){
            temp.add(list2.get(i));
        }

        // re-initialize list2 and add temp using the constructor option
        list2 = new LinkedList<>(temp); 
        endTime = System.currentTimeMillis();
        System.out.println("Using For Loop and reconstruct the old list: " + (endTime-startTime) + " Millisecond");

        startTime = System.currentTimeMillis();
        // use the reverse static method provided by Java Collections Class
        Collections.reverse(list3);
        endTime = System.currentTimeMillis();
        System.out.println("Using Collection.reverse(): " + (endTime-startTime) + " Millisecond");

    }
}

结果

Using For Loop and clearing old list: 875 Millisecond
Using For Loop and reconstruct the old list: 859 Millisecond
Using Collection.reverse(): 31 Millisecond

如您所见，Collection.reverse()仍然是其中最快的。因此，我相信 Java 在性能和内存方面提供了最好的反转或排序方法。但我仍然愿意接受纠正。