ที่นี่เราจะเห็นโครงสร้างข้อมูลหนึ่งโครงสร้างที่มีองค์ประกอบ n รายการและการดำเนินการ O(1) ดังนั้นการดำเนินการจะใช้เวลาคงที่ในการดำเนินการ
โครงสร้างข้อมูลจะเก็บ n องค์ประกอบ (จาก 0 ถึง n-1) ข้อมูลสามารถอยู่ในลำดับใดก็ได้ การแทรก การลบ และการค้นหาจะใช้เวลา O(1)
เพื่อแก้ปัญหานี้ เราจะใช้อาร์เรย์บูลีนหนึ่งอาร์เรย์ สิ่งนี้จะระบุว่ารายการนั้นมีอยู่หรือไม่อยู่ที่ตำแหน่ง i หากมีรายการอยู่ จะถือ 1 มิฉะนั้น 0
อัลกอริทึม
การเริ่มต้น(n)
begin fill all elements of the Boolean array as 0 end
insert(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]; }