実際には、リンクリスト追加O（N）またはO（1）ですか？

Question

リンクリストの追加と削除は一定時間、すなわちO（1）で起こるが、要素のアクセスはリストのサイズ、すなわちO（N）に比例して起こると言われている。私の質問は、最初にそれをトラバースすることなく要素を削除または追加する方法です。その場合、O（N）の順序も追加または削除されませんか？いくつかのいずれかが、この操作は一定の時間で起こることができるか、stamps.remove（k）を行いときに

    LinkedList stamps = new LinkedList(); 

    stamps.add(new Stamp("Brazil")); 
    stamps.add(new Stamp("Spain")); 
    --- 
    ---- 
    stamps.add(new Stamp("UnitedStates"); //say this is kth element in the list 
    ---- 
    stamps.add(new Stamp("India"); 

：私たちは、このようにAPIを使用する場合

のJavaを例に取ると、何が起こりますか？

Answer 1

リンクされたリストからアイテムを削除することは、リスト上の実際のノードへのポインタがある場合にのみ、一定時間内に動作します。あなたが持っている唯一のものが、 "n"番目のノードを削除したいという情報であれば、そのノードがどれであるかを知る方法がありません。その場合、まずリストをたどる必要があります。 （n）。

追加は、リストに既に含まれている要素の数には決して接続されていないため、常に一定時間で機能します。提供されている例では、add（）の呼び出しはすべてO（1）であり、Stampクラスのコンストラクタを呼び出すコストは含まれていません。リンクされたリストに追加することは、別の要素をその最後に付加することです。これは、もちろん、リンクされたリストの実装が、どのノードが現在リストの終わりにあるかを知っていることを前提としています。それがわからない場合は、もちろん、リスト全体のトラバーサルが必要です。