Copied from stack overflow due to feedback
So I want to teach someone how to do dynamic memory allocation using the block padding model. What that means is every memory block is prefixed and postfixed with 4 bytes holding the length of the block in bytes along with a bit (held in the leftmost bit as that one should never get used) to denote whether the block is free or allocated.
Everything in the dynamic memory allocation involves the manipulation of the padding of the blocks which I tend to think of as nodes in a doubly linked list. It's technically not quite the same but it is enough to make a fairly decent comparison in mentality and the operations used.
I'm going to be working on a project with a much younger high school kid with basic programming knowledge in C++ and Java (based on what he claims, anyway). Basically his teacher knows his next year teacher and they are letting him do some kind of programming over the summer with anyone the student chooses (I got the honor of being chosen).
Anyways, the solution i determined to accomplish something in a pretty clunky programming language (Game Maker and that's because it's something we can do gamedev in) with a broken object/pointer interface is to simply implement structs by using an array and acting as if it were the heap space. So hence, we're implementing the DMA algorithms to act on array indices. This isn't really hard for me to do and I probably have half-decent code somewhere in my files that would suit our interests.
However, I want to try to give the other guy a chance to do it, since it is one of the pivotal subsystems for the program. So that leads to the final question:
How does one explain the concept of dynamic memory allocation and how to code the functions to do it without relying upon pointers and linked lists as concepts to make comparisons to?
I was thinking of maybe making some problem sets with answers and steps to demonstrate the allocator's actions on an array but I think that might be overkill considering we should get working right away and not waste too much time. Are they any good ways to describe block padding and stuff that even a laymen might understand?
If it helps with context, I'm a third year undergrad computer science major. Hence, I have no real experience teaching.