したがって、私の comp sci クラスのトピックの 1 つは、時間の複雑さに関するものであり、特定の操作を比較するための良い方法として配列とリンクされたリストを使用し、どのコンテナーがそれを行うのに適しているか、適切なデータ構造を選択できるようにすることです。ほとんどの操作の背後にある理由は理解していますが、配列への挿入と追加についてはわかりません。
これらの両方の最悪のシナリオは O(n) です。挿入が O(n) である理由を理解していると思います。最悪の場合、前に挿入するとすべての要素が右にシフトするため、線形であり、配列内の要素の数に依存します。追加については、スペースがある場合、最後に要素を追加するのにサイズに関係なく1回の操作が必要なため、なぜO(1)ではないのか興味がありました。
十分なスペースがない場合、最悪のシナリオのために配列をより大きなものにコピーする必要がありますか?
[...] 十分なスペースがない場合、最悪のシナリオのために配列をより大きな配列にコピーする必要がありますか?
ビンゴ。
典型的な配列は、コンパイル時または実行時に決定される一定のサイズを持つ連続したメモリのチャンクです。要素を削除したり、配列に挿入したりするようなことはありませんが、既に割り当てられているメモリに書き込むだけです。
リンク リストは、メモリ チャンクの不連続なコレクションであり、アドレスによって接続されています。リンクされたリストに要素を削除して挿入するようなことがあります。
リンクされたリストに対する配列の利点は、トラバーサルが容易でコンパクトであることです (次の [または前の] 要素のアドレスを格納するための余分なメモリは不要です)。ただし、リンクされたリストとは異なり、これは簡単に拡張できません。
それにもかかわらず、データ構造に固有のアルゴリズムの時間の複雑さについてより正確に話すためには、まずデータ構造を定義する必要があります。
二重連結リスト? 最初と最後の要素 (キューなど) のアドレスを保存しますか? 二分木 (連結リストの一種)?