テクノロジ
環状リストとは
読み方：かんじょうリスト
ひとことで言うと：末尾の次が先頭を指し、要素が輪状につながった連結リスト。
意味をわかりやすく解説
環状リストは、末尾ノードの次が先頭ノードを指し、ノード列が輪になっている連結リストです。終端を示すnullがありません。
任意のノードから順番にたどり続けられるため、処理対象を循環させる用途に向きます。一方、走査では開始位置へ戻ったことを終了条件にしないと無限ループになります。
具体例
A→B→C→A のようにつなぎ、CPU時間をプロセスへ順番に割り当てるラウンドロビン処理に利用できます。
似た用語との違い
線形リスト
線形リストは末尾で終了します。環状リストは末尾から先頭へ戻ります。
キュー
キューの実装で固定長配列を環状に使うリングバッファも、循環という考え方を利用します。
覚え方
末尾の次が先頭。輪になっているので「nullで終わらない」。
基本情報技術者試験の試験ポイント
終了条件と、ラウンドロビンやリングバッファとの関連を押さえます。
CHECK QUESTION
環状リストを先頭から走査するとき、null判定だけでは終了できないのはなぜですか。
答えを見る
末尾ノードがnullではなく先頭を指すためです。開始位置へ戻ったことなどを終了条件にします。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。