9

私は以下のコードを持っていますが、新しい整数をintのソートされたLinkedListに挿入していますが、次の値へのポインターを持つ単一のリンクリストと二重のリンクリストがあることを知っているので、それが「正しい」方法だとは思いません次および前の値へのポインター。Nodes を使用して以下のケースを実装しようとしましたが、Java はこのインポート org.w3c.dom.Node (ドキュメント オブジェクト モデル) をインポートしているため、行き詰まりました。

挿入例

  1. 空の配列に挿入
  2. 挿入する値がすべてより少ない場合は、先頭に挿入します。
  3. 挿入する値がすべてより大きい場合は、最後に挿入します。

  4. 値が LL の特定の値よりも小さい/大きい場合は、その間にある可能性があります。

    import java.util.*;

public class MainLinkedList {
public static void main(String[] args) {
LinkedList<Integer> llist = new LinkedList<Integer>();

llist.add(10);
llist.add(30);
llist.add(50);
llist.add(60);
llist.add(90);
llist.add(1000);
System.out.println("Old LinkedList " + llist);

//WHat if you want to insert 70 in a sorted LinkedList
LinkedList<Integer> newllist = insertSortedLL(llist, 70);
System.out.println("New LinkedList " + newllist);
}

public static LinkedList<Integer> insertSortedLL(LinkedList<Integer> llist, int value){

    llist.add(value);
    Collections.sort(llist);
    return llist;

}

    }

4

7 に答える 7

11

これはあなたの目的を完全に果たすかもしれません：

次のコードを使用します。

import java.util.*;

public class MainLinkedList {
    private static LinkedList<Integer> llist;

    public static void main(String[] args) {
        llist = new LinkedList<Integer>();

        addValue(60);
        addValue(30);
        addValue(10);
        addValue(-5);
        addValue(1000);
        addValue(50);
        addValue(60);
        addValue(90);
        addValue(1000);
        addValue(0);
        addValue(100);
        addValue(-1000);
        System.out.println("Linked List is: " + llist);

    }

    private static void addValue(int val) {

        if (llist.size() == 0) {
            llist.add(val);
        } else if (llist.get(0) > val) {
            llist.add(0, val);
        } else if (llist.get(llist.size() - 1) < val) {
            llist.add(llist.size(), val);
        } else {
            int i = 0;
            while (llist.get(i) < val) {
                i++;
            }
            llist.add(i, val);
        }

    }

}

この1つのメソッドは、使用せずに並べ替えられた方法でリストへの挿入を管理しますCollections.sort(list)

于 2013-08-09T15:53:45.023 に答える
1

com.google.common.collect.TreeMultisetをご覧ください。

これは事実上、同じ値の複数のインスタンスを許可するソートされたセットです。

これは、あなたがやろうとしていることに対する素晴らしい妥協です。挿入は ArrayList よりも安価ですが、バイナリ/ツリー検索の利点は引き続き得られます。

于 2016-10-25T14:52:48.407 に答える
0

順序基準を知って、データを挿入する場所を見つける必要があります。

簡単な方法は、挿入位置を総当たり検索することです（リストをたどる、バイナリ検索...）。

もう 1 つの方法は、データの性質がわかっている場合は、挿入位置を推定してチェックの数を減らすことです。たとえば、「Zorro」を挿入し、リストがアルファベット順に並べられている場合、リストの最後から開始する必要があります... または、文字がどこにあるかを推定します (おそらく最後に向かって)。これは、数値がどこから来て、どのように分布しているかがわかっている場合にも機能します。これは補間検索と呼ばれます: http://en.wikipedia.org/wiki/Interpolation_search

バッチ挿入についても考えてください。大量のデータをすばやく挿入する場合は、一度に多くの挿入を行い、その後は 1 回だけ並べ替えることを検討してください。

于 2013-08-09T10:43:02.927 に答える
0

リンクされたリストは、SortedList のより良い実装ではありません

また、新しい要素を追加するたびにすべてのリストを並べ替えるのは効率的ではありません。最善の方法は、要素をあるべき場所 (正しい位置) に直接挿入することです。このために、すべての位置をループしてこの番号が属する場所を見つけてから挿入するか、 Collections.binarySearch を使用してこの高度に最適化された検索アルゴリズムにこの仕事を任せることができます。

BinarySearch は、オブジェクトがリストにある場合 (必要に応じてここで重複をチェックできます)、オブジェクトのインデックスを返します。または、オブジェクトがリストにまだ存在しない場合 (および挿入ポイントが順序を維持するためにオブジェクトを配置する必要があるインデックス)

于 2013-08-09T10:46:57.057 に答える