자기 조직화 리스트(Self-Organizing List)는 마지막으로 검색된 항목을 기준으로 리스트의 순서를 스스로 갱신하는 자료구조입니다. 이 방식에서는 기본적으로 순차 탐색(Sequential Search)이 사용되며, 자주 검색되는 중요한 데이터를 리스트의 맨 앞으로 이동시켜 이후의 탐색 속도를 높입니다. 이 탐색 기법의 시간 복잡도는 O(n)입니다.
동작 원리
자기 조직화 리스트의 검색 알고리즘은 다음과 같이 동작합니다.
Begin
Function SearchItem(head, item).
헤드 노드의 값이 찾는 항목과 일치하는지 확인합니다.
일치하면 "헤드 노드에서 발견" 메시지를 출력하고 리스트를 그대로 반환합니다.
일치하지 않으면 리스트를 따라가며 다음 노드의 값과 비교합니다.
항목을 찾으면 해당 노드를 리스트의 맨 앞으로 이동시킵니다.
끝까지 탐색했는데도 항목이 없으면 "항목을 찾을 수 없음" 메시지를 출력합니다.
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 != NULL) {
cout<<"->"<<temp->d;
temp = temp->next;
}
}
node* SearchItem(node *head, int item) {
int flag = 0;
node *temp = head;
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;
}
// 찾은 노드를 리스트의 맨 앞으로 이동
node *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
코드 설명
- CreateNode(): 새로운 노드를 생성하고 초기화합니다.
- InsertIntoList(): 리스트의 끝에 새 데이터를 추가합니다.
- Display(): 현재 리스트의 상태를 출력합니다.
- SearchItem(): 항목을 순차적으로 탐색하며, 찾은 경우 해당 노드를 리스트의 맨 앞으로 재배치합니다. 이것이 바로 '자기 조직화'의 핵심 동작입니다.
실행 결과를 보면 값 7을 검색한 후 리스트의 상태가 ->7->1->2...로 변경된 것을 확인할 수 있습니다. 검색된 노드가 맨 앞으로 이동했기 때문입니다. 만약 다음에 다시 7을 검색하면 헤드 노드에서 즉시 발견되어 탐색 시간이 크게 단축됩니다.