"Foydasiz" data structure haqida eshitganmisiz? Ya'ni struktura saqlanadi, lekin hech qanday foydali ma'lumot saqlanmaydi. Masalan, klassik singly linked list nodeda value va keyingi nodega pointer saqlanadi. Endi tasavvur qiling, shu yerdan valueni olib tashlab, faqat next pointerni qoldirsak nima bo'ladi? Haliyam linked list, lekin foydali biror narsaga ishlatish qiyin, sababi unda ma'lumot saqlashning iloji yo'q.

Aniqrog'i, shunday deb o'ylardim. Bugun qiziq bir narsa ko'rib qoldim. Ko'pchilik zamonaviy OSlarda free memory linked list va/yoki bitmap sifatida saqlanadi. Linked list sifatida saqlanganda har bir free blockning boshida node joylashib, block haqida metadata (masalan, block uzunligi) va keyingi free block'ka pointer saqlaydi. Lekin metadata saqlashga hojat bo'lmasachi? Masalan, virtual memoryda free pagelarning uzunligini metadata sifatida saqlash shart emas, sababi bu hamma uchun bir xil va o'zgarmaydi. Shunda hech qanday ortiqcha metadatasiz shunchaki page boshlanish joyining addressini bilish yetarli bo'ladi. Shunday holatlarda tepada aytilgandek "foydasiz" strukturalarning ham foydasi tegib qolar ekan.