基于链表的java有序集

Question

我正在使用java，我需要使用SortedSet接口实现一个基于链表的有序集。在这种情况下，如何实现SortedSet中的方法

Answer 1

据我所知，您需要使用Set功能从LinkedList中删除重复项，并使用SortedSet对其进行排序

所以，如果你有一个链表，最简单的方法就是这样做。在本例中，我使用了LinkedList，其中将填充随机数：

public class Main {
public static void main(String[] args){
    //Declare the LinkedList of Integers
    LinkedList<Integer> linkedList = new LinkedList<Integer>();
    //use special method to fill List with 10 numbers which are less than 100
    linkedListRandomFill(linkedList, 10, 100);

    //After you pass the LinkedList to the following constructor
    //  the list is sorted automatically
    SortedSet<Integer> sortedSet = new TreeSet<Integer>(linkedList);

    //After that you can recreate your linked list,
    //  just pass the SortedSet to LinkedList constructor
    linkedList = new LinkedList<Integer>(sortedSet);
    System.out.println(linkedList);
}

public static void linkedListRandomFill(
        LinkedList<Integer> linkedList,
        int size,
        int limit){
    Random rnd = new Random();
    for(int i = 0; i < size; i++){
        linkedList.add(rnd.nextInt(limit));
    }
}

我们还可以重构：

public class Main {
    public static void main(String[] args){
        LinkedList<Integer> linkedList = new LinkedList<Integer>();
        linkedListRandomFill(linkedList, 10, 100);
        linkedList = getSortedListOfUniqueValues(linkedList);
        System.out.println(linkedList);
    }

    public static void linkedListRandomFill(
            LinkedList<Integer> linkedList,
            int size,
            int limit){
        Random rnd = new Random();
        for(int i = 0; i < size; i++){
            linkedList.add(rnd.nextInt(limit));
        }
    }

    public static LinkedList<Integer> getSortedListOfUniqueValues(LinkedList<Integer> list){
        SortedSet<Integer> sortedSet = new TreeSet<Integer>(list);
        return new LinkedList<Integer>(sortedSet);
    }
}

Answer 2

因为这显然是一个家庭作业（或类似的学习练习），所以给你代码是不合适的。因此，这里有一些提示可以帮助您开始

1. 您需要始终保持链表元素的有序性

2. 如果链表是一个包装的LinkedList，那么可以将许多SortedSet方法委托给链表

可选地，考虑使用^ {CD3>}作为集合的基类。

（你需要检查作业要求的措辞，以确定你是否被允许使用LinkedList或AbstractList。）