3 ms·
Pool allocators don't walk the list or search anything though. All interactions are only at the list head and O(1), as all free nodes are just that, free and eq
by JJOmeo 2y ago
Pool allocators don't walk the list or search anything though. All interactions are only at the list head and O(1), as all free nodes are just that, free and equal.
- ceving 2y agoThen it might be a misnomber. Calling it "stack" instead of "list" might be better.
- alextingle 2y agoThat is a fair comment.
- cb321 2y agoWhile the most precise naming might be "a singly linked list representation of a stack", "free list" (https://en.wikipedia.org/wiki/Free_list https://en.wikipedia.org/wiki/Free_list) is an ancient term of art for this problem.. so much so that wikipedia (at least the version today) even suggests "freelist" all one word as a spelling. The initial linking together of all free space (also cache friendly, btw) is often called "threading the free list", although this terminology is less standard than "free list" itself.