Javaのリンクリストをソートするメソッド

Question

大丈夫ですので、すべての情報がリンクリストにオブジェクトとして送信されているこの問題があります。リンクリストは別のクラスから初期化され、この他のクラスにはLinkedListのすべてのメソッドが含まれます。リンクされたリスト内のオブジェクトを数値に基づいてソートする方法はありますか？各要素がこのように見える（「800110 Jane Hey you are there」）。 int型が順番にアレントが、私はそれらを注文する必要があると私はソートイマイチ許さ方法とコレクションの知らない

 //if the command is to RecieveMessage 
     SinglyLinkedList <String> Jane= new SinglyLinkedList <String>(); 
     int Time; 
     String Name; 
     String Message 
     Time=in.nextInt(); 
     Name=" "+in.next(); 
     Message=in.nextLine(); 
     if(Name.equals(" Jane")) { 
      //sends message to Janeand increases the number of 
      //unread messages and notifies Jane 
     Jane.addLast(Time+Name+Message); 

：に行く前に、彼らはint型、文字列、文字列として設定されています。私を助けてもらえますか？ .addlastは標準のLinked List関数から来ます。私は他の4人のユーザーを同じ方法で並べ替えなければならないので、もしそれらのすべてをタイムスタンプで並べ替えるのであれば、それは素晴らしいだろう。

public static int extractTime(String Sentence) { 
     int length = Sentence.length(); 
     String result = ""; 
     for (int i = 0; i < length; i++) { 
      Character character = Sentence.charAt(i); 
      if (Character.isDigit(character)) { 
       result += character; 
      } 
     } 
     return Integer.parseInt(result); 
} 

文字列の文がforループを使用して特定のノードでの要素である：また、時間を抽出するために、このメソッドを使用してイム

for(int i=0; i < Jane.size();i++) { 
       UnreadMessage=Jane.first().toString(); 
       int returnTime= extractTime(UnreadMessage); 
       } 

助けてください、これはそんなに私を助けます。

Answer 1

コンパレータ<>インタフェースを実装する内部クラスTimeCompを書きます。あなたはノードが一度にリンクリスト1に挿入する取得している場合は、使用でき

class Person{ 

    int time; 
    String name; 
    String message; 
    //Write get and set methods for all member variables 

    class TimeComp implements Comparator<Person>{ 
     @Override 
     public int compare(Person p1, Person p2) { 
     if(p1.getTime() < p2.getTime()){ 
      return 1; 
     } else { 
      return -1; 
     } 
    } 
    } 
} 

List<Person> persons = new LinkedList<Person>(); 
Collections.sort(persons, TimeComp); 

Answer 2

：あり、私たちは、Personオブジェクトをソートする戦略を指定し、Collections.sort（）メソッドに渡しますソートされたリストを保持するためにリンクリストの小さな配列（25〜32）を使用するボトムアップマージソートのバリエーションです。ここで、array [i]はnullまたは2^iのリンクリストへの参照です電源i）ノード。各ノードは一度にアレイ1にマージされ、マージ操作がアレイを更新するために使用されます。最後のノードが追加されると、配列は1つのソートされたリストを形成するためにマージされます。ウィキは、擬似コードの例があります。この場合のマージソートをボトムアップ使用

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

は、時間複雑性Oを有するであろう（N）（ログ）、O（N^2）に対する方法のような挿入ソートのために。