Một cấu trúc dữ liệu cho n phần tử và các phép toán O (1)?

Ở đây chúng ta sẽ thấy một cấu trúc dữ liệu với n phần tử và các phép toán O (1). Vì vậy, các hoạt động sẽ mất khoảng thời gian không đổi để thực hiện.

Cấu trúc dữ liệu sẽ chứa n phần tử (từ 0 đến n-1). Dữ liệu có thể theo bất kỳ thứ tự nào. Việc chèn, xóa và tìm kiếm sẽ mất O (1) khoảng thời gian.

Để giải quyết vấn đề này, chúng ta sẽ sử dụng một mảng Boolean. Điều này sẽ cho biết rằng mặt hàng có hay không ở vị trí thứ i. Nếu mặt hàng hiện diện, nó sẽ chứa 1, ngược lại là 0.

Thuật toán

khởi tạo (n)

begin
   fill all elements of the Boolean array as 0
end

insert (i)

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

xóa (i)

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

tìm kiếm (i)

begin
   return item at position i
end

Ví dụ

//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];
}