連結リスト（導入）

配列は固定長で連続してメモリ上に並ぶ故に生じるデメリットである

• 途中でサイズを変更する事が難しい（動的配列なら可能）
• 配列の途中のインデックスに要素を追加する際、それ以降の要素を全てシフトさせなければならない などのデメリットがあります。これに対する解決策の一つとして連結リスト（Linked List）があります。

特徴

• 各要素（ ノード ）はメモリ上の任意の位置に配置され、次の要素へのポインタ（ リンク ）によって連結されます
• ノードはval（値）とnext（次の要素へのポインタ）の2つで構成されます
• 先頭の要素をhead、最後の要素をtailと表す事が多いです
• 任意の要素へのアクセスには、リストの先頭から始めて該当の要素に到達するまで各要素を順に辿らなければならないため、時間がかかることがあります（$\mathrm{O(N)}$の時間計算量）
• 新しい要素の追加や既存の要素の削除は、リンクを調整するだけで高速に行うことができます（$\mathrm{O(1)}$の時間計算量、ただし要素を挿入または削除する位置を探すためには、リスト内を走査する必要があるため、実際には$\mathrm{O(N)}$の時間がかかる場合があります）
• 連結リストのサイズは動的であり、新しい要素を追加したり既存の要素を削除したりすることで変更できます