LinkedListの中にJavaを挿入する

要素{A、B、C、D、E、F}を挿入すると、これらの操作は,（1）になります最後のLinkedListが{G、H、I、A、B、C、D、E、F}のようになるように{G、H、I}を追加します。LinkedListの中にJavaを挿入する

私はlist.add(index, content)を使用してこれを行うことが、しかしこれは、各操作はO（N）になりますので、非常に非効率的です。後で私はテールで追加を続けたいと思います。私はこれらのすべての操作をO（1）時間で行う方法があると確信しています。自分のリンクリストを作成せずに、私はちょうどどうしたらいいか分かりません。

編集：Javaにある種のイテレータ/ポインタがあるかどうかを実際に知りたいのですが、そこから挿入できるのはどこですか？O：（1）、i = 3 {A、B、C、 H、I、D、E、F}のように見えるようにするためには、{D、E、F} list.addAllが動作しますが、最初にリストを作成する必要があります。そのような方法が存在するならば、私はそれを知らずに続行したくない。

最後に私はこのUvaの裁判官を解決するためにこの質問をしていますproblem私はそれを解決する方法を知っていますが、他のシナリオを一般化できない場合、私は何も学んでいません。

出典

2016-07-24 Yumario

最初に追加するのに 'list.addFirst（）'を使い、末尾に追加する 'list.addLast（）'と 'list.add（index、data）' –

'add（int index、 O（list.size（））ではなくO（インデックス）です。 –

Javadocによると：

リストとのDequeインタフェースの二重リンクリストの実装です。

二重リンクされたリストで期待されるように、すべての操作が実行されます。リストにインデックスを付けるオペレーションは、指定されたインデックスに近いほうから、リストの先頭または末尾を走査します。あなたの懸念について

：各操作はO（N）になるので、私は（インデックス、コンテンツ）をlist.add使用してこれを行うことができます

は、しかし、これは非常に非効率的です。後で私はテールで追加を続けたいと思います。

これは当てはまりません。リストの先頭または最後に要素を挿入すると、O（1）の実行時間が設定されます。したがって、心配することはありません。

編集：UVa問題の説明を読んだ後、上記の私の答えはまだ立っています。さらに、問題を解決する良い方法は、一度に1文字ずつではなく、文字列全体を一度に追加することです。 2つのホーム/エンドキーの間のすべての文字は、単一の破られない文字列として扱う必要があります。次に、これらの文字列をLinkedList<String>の先頭または末尾に追加します（LinkedList<Character>ではなく）。真ん中に挿入することについて心配する必要はまだなく、想像上の挿入イテレータを持つ必要もありません。

出典

2016-07-24 06:26:46 Nayuki

addFirstはO（1）ですが、list.addはO（インデックス）ですが、addFirstは{G、H 、I}リストは、{I、H、G .....}がもっと重要なことに、インデックスiとインデックスi + 1に挿入したいと想像したいと思います。私は値を挿入するたびにi + sに向かうことはしません。 – Yumario

@Yumario ['addAll（int index、Collection c）']（https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html#addAll-int）を使用していない場合-java.util.Collection-）。 'List list = new LinkedList <>（Arrays.asList（" A "、" B "、" C "、" D "、" E "、" F "））のように。 list [A、B、C、G、H、I、D、E、F] 'を作成するlist.addAll（3、Arrays.asList（" G "、" H "、" I "））;インデックス3を一度検索するだけでした。 – Andreas

ありがとうございます。ちょうど、javaには 'place'を挿入するためのIteratorがありません。 – Yumario

LinkedListの中にJavaを挿入する

答えて

関連する問題