アルゴリズム - 循環リストと二重リンクリスト

循環リストとは

リストの最後のノードでは、リンク フィールドには、終了を示す値である null が入ります。循環リストは、リスト内の最初のノードを指すことで構成されます。これは、オープンまたは線形 succ(tail)=head であると言われます。

ポインターによる循環リストの定義

ポインタ駆動 の円形リスト

1)リストを閲覧する

プロシージャーパス(L: ptr , p : ptr)
var pp:ptr
start
    pp := p
    repeat
         process (*pp.val)
         pp := *pp.link
    to (pp=p)
end

2)挿入

頭に挿入

先頭 に挿入

リード外での統合

上以外の部分を挿入

リンク リストに項目を挿入する。

3) 削除

参照: リンクリストからの項目の削除

長所と短所

• コースには特別なケースはありません。
• 挿入用の3つのケース:
• 一番上(空のリスト)にあります。
•  一番上 (空でないリスト)。
• リード以外の 場所で。
• 削除のケースは 3 件です。
•  一番上 (1 項目一覧)。
• 上部 (複数の項目を含むリスト)。
• リード以外の 場所

リンクによる循環リストの定義

• ルートは、歩哨である現在のリンクから作成されます。
• 統合には特別なケースはありません。
• 排除するリンクがセンチネルではないことを確認する必要があります。