リンクリスト

この文章はBaking Dogアルゴリズムの基礎復習です.
リンクリストとは、以下の資料位置に格納される資料構造を指す.
それぞれの場合の時間の複雑さは次のとおりです.
任意の位置で元素O(N)を検査/変換する
任意の場所で要素Oを削除する(1)
タイプには、単一のリンクリスト、二重リンクリスト、円形リンクリストが含まれます.
個々のリンクリストには、次のリソースが格納されている場所のみが格納されます.
ダブルリンクリストには、各格納場所の前後のデータ位置が格納されます.
最後に、円形リンクリストは、終了資料が最初に保存された場所を保存します.
従来の配列やリンクリストは線形資料構造であり,今後学習する木やハッシュなどは非線形資料構造といえる.
以下に示すように、ストレージスペースは2つの方法で実現できます.
1号方式

struct NODE{
	struct NODE *prev, *next;
    int data;
}

2ウェイ

const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;
fill(pre, pre+MX, -1);
fill(nxt, nxt+MX, -1);

1号はこの程度、2号は購入していますが、実現できればベストです.
通常はSTL list実装を用い,直接実装すると次のコードに示す.
ループ関数は、次のように各要素を出力します.

void traverse(){
  int cur = nxt[0];
  while(cur != -1){
    cout << dat[cur] << ' ';
    cur = nxt[cur];
  }
  cout << "\n\n";
}

INSERT関数は要素を生成した後、前のリンクリストと後のリンクリストにアドレスを関連付けます.

void insert(int addr, int num){
    dat[addr] = num;
    pre[unused]=addr;
    nxt[unused]=nxt[addr];
    if(nxt[addr]!=-1){pre[nxt[addr]] = unused;}
    nxt[addr] = unused;
    unused++;
}

eraseは要素を消去し、後続の要素を前の要素に接続します.

void erase(int addr){
    nxt[pre[addr]] = nxt[addr];
    if(nxt[addr] != -1){pre[nxt[addr]]=pre[addr];}
}