Let's say I want to implement my simple version of free/malloc
Let's assume I got a huge chunk of memory where I manage my free/malloc there. and also I can only allocate fixed block size on each malloc (1 byte for example).
So in general I keep "free list" of free addresses of one byte, so whenever somebody do malloc, I just return the address in the head of list and take out the head .. (head=head->next) .
and when a user does free(ptr) I just add that address to the head of the list.
So both actions are $O(1)$.
Now, I see some implementation that puts "header" before each data to keep the next pointer there, and I don't understand why is it doing so? Because it's complicating things a bit, and I can't see where the advantage of doing that comparing to just use Linked list in different memory area.
free, you know already what size block it refers to (because there's only one size). If you support many sizes, you usually want there to be a header associated with the memory to tell you what size the block is. The headers also allow you to add more sophisticated logic to reduce memory fragmentation (e.g. you can check if a newly freed block is adjacent to other free memory or not, by checking the adjacent headers). $\endgroup$ – Blckknght Mar 28 '16 at 21:41