※この記事に限ってLinkedList 連結リストの事を「単方向連結リスト」という前提で話しています。双方向連結リストの話は一切してないのでご注意ください。
参考記事１：Pythonのデータ構造と内部実装 〜List編〜
参考記事２：Javaでの配列のしくみ(図解)
参考記事３：Pythonユーザーなら知っておきたいのリストの仕組み
前回のあらすじ（前回とは？）
競プロ(AtCoder）のABC335 C問題において、insertしたらTLE（制限時間オーバー）し、appendしたらAC（通過）した。
心底納得いかない！！！！！というのが本音だった。
- append … Pythonのlist型が持つ、要素を末尾に追加するメソッド。
- insert … Pythonのlist型が持つ、要素を指定箇所に挿入するメソッド。（0指定で先頭に挿入する）
何が納得いかないのか
大学でデータ構造について学んでおり、配列とリスト（連結リスト）は構造が異なる。
そのため、PythonのListは連結リストで実装されているであろうという思い込みによって今回のような疑問が生まれてしまった。
参考記事１の図が分かりやすいが、配列は連続した領域を確保して、データが隙間を開けず連続して入るような構造をしている。
対して、リスト（単方向連結リスト）は、1つのノードに1つの要素と次の要素へのポインタ（次要素のアドレス番地）を所持するような構造になっている。
とても絵が雑ですね。ｗ
例えば、「1と2の間に９を入れたい」という処理をしようとする。それを実現するとこうなる。
配列の場合、値を追加するには、102の場所に9を入れてそれ以降のデータを全てズラしていく必要がある上に、固定長のため既に限界まで埋まっていたら要素数＋１の新しい配列を作ってそっちに移動させる必要がある。
連結リストの場合、適当なアドレスを確保してノードを1つ新しく作って、挿入位置の前のノードのポインタを新しいノードに指しなおして、新しいノードが持つポインタを前もって居たノードのアドレスにすれば、挿入が完了となる。
つまり
配列で要素を追加する場合、大抵配列を新しく作り直して全てfor文でコピーしていくみたいな処理が必要で、時間がかかる。
対して、連結リストはノード作ってポインタちょい変えれば終わり。
オーダー表記なら前者はO(n)、連結リストはO(1)なのかな
但し、データを拾ってくる場合は配列の方が添え字（インデックス）で直接指定して持ってくることができて高速である。（先頭アドレスに添え字を追加した値の番地からデータを取るだけなのでO(1)）
連結リストの場合、先頭から添え字の回数だけ次のノードをたどっていかないといけないのでO(n)かかる。
つまりつまり
LinkedListならappendして要素追加してもinsertで要素挿入してもO(1)で高速なハズやん！！！！
↑ここが納得いかなかった。
しかし、色々と調べてみると思い込みが発覚した。「PythonのListってLinkedListで実装されていない！？」
Pythonのリストは動的配列（リストじゃない）
参考資料３の記事で解説されているが、Pythonのリストとは実は動的配列(Dynamic Array)であり、データ構造的にはリストではなかったのである。
動的配列とは「要素数に応じて領域を確保する」配列の事である。
growth factorみたいな単語が資料1とかでも出てきたけど、growth factorという値は言語によって定められており、要素数が増えてきて現在の容量が圧迫されてくるとgrowth factorの値に応じて自動的にメモリ領域を再割り当てする、その時どれくらいの容量を確保するかみたいな値らしい。（のかな）
appendとinsert
要素を追加する場合、連結リストならノードを1個増やす、配列なら新しく全てを作り直す必要があると説明したが、今回競プロの問題で「insertをappendにしたら制限時間オーバーせずに通過した」というのは、まさにこれでgrowth factorによって領域を動的に増やしたり減らしたり、調整しているためappendで要素を追加する場合に限っては計算量が抑えられるからである。(と思われる）
これがただのJavaの配列（静的な配列）であれば、appendするにも配列を新しく領域を用意してコピーして・・・・という手順が必要になるためappendでも計算量はかなりかかる。(というかそういう使い方をJavaでするならArrayListを使えと言う話だが）
結局領域を可変長で確保するってだけなので、間に要素を挟むときはそれ以降の要素全てをズラす必要がある（O(n)？）ため、insertよりappendの方が計算量が抑えられるという話だった。
まとめ
Pythonのリストは配列。
動的配列だから要素を追加するときに限っては計算量少ないけど、配列を扱うつもりで書いてねということ。
ちなみに
Pythonのリストが連結リストではなく動的配列というのはChatGPTさまさまによって知ることができた。「なんか配列みたいな扱い方してるな、今日もGPT使えないか？」とか疑った自分恥ずい。
蛇足
Pythonのgrowth factorは1.125とかしかないらしい(Cは2あるのに)、だけどデータが大きくなっていくにつれて指数関数的に伸びていくわけだし、そこらへんのも割と考えられているのかも。
