自己組織化リストを用いて検索を実行するC++プログラム

自己組織化リスト（Self-Organizing List）とは、直前に検索された要素をきっかけに、リスト内の要素の並び順を動的に入れ替えるデータ構造です。探索には逐次探索（線形探索）が用いられ、見つかった要素をリストの先頭へ移動させることで、頻繁に検索される重要なデータほど先頭付近に集まるようにします。この探索手法の計算量は O(n) です。

アルゴリズム

Begin
    関数 SearchItem() を呼び出す。
    目的の要素が先頭ノードと一致すれば、結果を出力して終了する。
    一致しなければ、リストを順にたどりながら各ノードの値と比較する。
    要素が見つかったら、そのノードを切り離してリストの先頭へ移動する（Move-to-Front 方式）。
    更新後のリストの状態を表示する。
    最後まで見つからなければ、「要素が見つからない」ことを出力する。
End

サンプルコード

#include<iostream>
using namespace std;
struct node {
    int d;
    node *next;
};
node* CreateNode(int d) {
    node *newnode = new node;
    newnode->d = d;
    newnode->next = NULL;
    return newnode;
}
node* InsertIntoList(node *head, int d) {
    node *temp = CreateNode(d);
    node *t = head;
    if(head == NULL) {
        head = temp;
        return head;
    } else {
        while(t->next != NULL)
            t = t->next;
        t->next = temp;
    }
    return head;
}
void Display(node *head) {
    node *temp = head;
    cout<<"\n The list state is :";
    while(temp->next != NULL) {
        cout<<"->"<<temp->d;
        temp = temp->next;
    }
}
node* SearchItem(node *head, int item) {
    int flag = 0;
    node *temp = head;
    node *t;
    if(temp->d == item) {
        cout<<"\nItem found at head node";
        flag = 5;
        Display(head);
        return head;
    } else {
        while((temp->next)->next != NULL) {
            if((temp->next)->d == item) {
                cout<<"\nItem found";
                flag = 5;
                break;
            }
            temp = temp->next;
        }
        t = (temp->next)->next;
        (temp->next)->next = head;
        head = temp->next;
        temp->next = t;
        if(flag == 5)
            Display(head);
        else
            cout<<"\nItem not found.";
    }
    return head;
}
int main() {
    int i, n;
    char ch;
    node *head = NULL;
    for(i = 1; i < 20; i++)
        head = InsertIntoList(head, i);
    Display(head);
up:
    cout<<"\nEnter the Element to be searched: ";
    cin>>n;
    head = SearchItem(head, n);
    cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
    cin>>ch;
    if(ch == 'y' || ch == 'Y')
        goto up;
    return 0;
}

実行結果

The list state is :->1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18
Enter the Element to be searched: 7
Item found
The list state is :->7->1->2->3->4->5->6->8->9->10->11->12->13->14->15->16->17->18
Do you want to search more...enter choice(y/n)?y
Enter the Element to be searched: 20
Item not found.
Do you want to search more...enter choice(y/n)?n

この実行例では、まず 1〜19 の整数が連結リストへ挿入されます。ここで「7」を検索すると要素が見つかり、同時に 7 がリストの先頭へ移動します。その結果、リストの状態は「7→1→2→3→4→5→6→8→…」と変化し、次回以降 7 を検索する際には先頭ノードとの一度の比較だけで見つけられるようになります。

一方、リストに存在しない「20」を検索した場合は「Item not found.」と表示され、探索は失敗に終わります。このように自己組織化リストでは、検索を繰り返すうちにアクセス頻度の高い要素が自然と先頭側に集まり、平均的な探索効率が向上する点が大きな特徴です。

なお、サンプルの Display() 関数はループ条件が「次のノードが NULL になるまで」となっているため、末尾のノードの値は表示されません。実行結果に 19 が現れていないのはこのためです。