分野 ：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：データ構造

線形リストとは、線形で表現されるリスト構造の総称で、一般的には隣接するデータ同士をポインタで連結して表現します。

• 木構造の説明です。線形リストではデータ同士に親子関係はありません。
• 線形リストは隣接する要素同士がポインタで接続されているため、データを先頭から順に探索していく線形探索に適しています。2分探索を行うのに適したデータ構造は要素が値の大小で整列されている2分探索木です。
• ポインタとは次の要素が格納されているメモリアドレスの情報です。次の要素を得るにはポインタが指し示すメモリ上のデータを読み込みます。
• 正しい。単方向リストの場合は新たな要素の追加は以下の手順で行われます。
  1. ポインタで指定された要素(以降、元要素)を取得する
  2. 元要素のポインタを新要素のポインタに付け替える
  3. 元要素のポインタが新要素を指し示すようにする
  元要素の取得後、その要素の後ろに新たな要素を追加する計算量は、リストの要素の個数や追加する位置によらず一定です。一方、配列の場合は追加する位置以後の要素を1つずつ後ろにシフトしなければなりません。