だから私は明日アルゴリズム分析試験のために勉強していて、インストラクターのメモと例を読んでいます。私が理解していないことが1つだけあり、それはこの質問です。
質問：配列ベースのリスト（カーソル実装）の特定の要素の後に要素を挿入するには、最悪の場合の時間が必要です。
回答：O（1）
個人的には、カーソルがリストの先頭にあるという最悪のケースがあります。したがって、新しい要素を挿入する前に、配列内のN-1個のアイテムを次の位置にコピーする必要があります。したがって、これはO（N）です。最悪の場合の操作。
しかし、これがタイプミスかどうか尋ねられたとき、インストラクターはそうではなかったと述べました。
この背後にある理由は何ですか？今後ともよろしくお願い申し上げます。
要素'a'を挿入する必要があるとしましょう。それは、要素が与えられたと言っているので、それを「b」と呼びましょう。つまり、次の要素が何であるかを知っているということです。それを「c」と呼びましょう。したがって、あなたがしなければならないのは、「a」の「次の」要素を「c」に等しく設定することです。次に、「b」の次の要素を「a」に等しく設定します。この手順は、すべての要素に有効です。したがって、操作は一定時間です。
配列内の各要素に次の要素のインデックスへのポインタが含まれている配列を使用して、本質的にリンクリストであるものを実装できます。
struct Element
{
string item;
int next;
}
要素Aが与えられると、一定時間内にAの後に新しい要素Bを挿入できます。
int indexOfA = ..
int indexOfB = (next free index)
B.next = A.next;
A.next = indexOfB;