n개의 요소와 O(1) 연산에 대한 데이터 구조?

여기에서 n개의 요소와 O(1) 연산이 있는 하나의 데이터 구조를 볼 수 있습니다. 따라서 작업을 실행하는 데 일정한 시간이 걸립니다.

데이터 구조는 n개의 요소(0에서 n-1까지)를 보유합니다. 데이터는 임의의 순서가 될 수 있습니다. 삽입, 삭제 및 검색에 O(1) 시간이 걸립니다.

이 문제를 해결하기 위해 하나의 부울 배열을 사용합니다. 이것은 항목이 위치 i에 있는지 여부를 나타냅니다. 항목이 있으면 1을 유지하고 그렇지 않으면 0을 유지합니다.

알고리즘

초기화(n)

begin
   fill all elements of the Boolean array as 0
end

삽입(i)

begin
   set element at index i as 1(true)
end

삭제(i)

begin
set element at index i as 0(false)
end

검색(i)

begin
   return item at position i
end

예시

//initialization
void init(int n) {
   bool dataStructure[n];
   for (int i = 0; i<n; i++)
      dataStructure[i] = 0;
}
//Insertion
void insert(unsigned i) {
   dataStructure[i] = 1;
}
//Deletion
void delete(unsigned i) {
   dataStructure[i] = 0;
}
//Search
bool search(unsigned i) {
   return dataStructure[i];
}