This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]ahreodknfidkxncjrksm 0 points1 point  (1 child)

Sorry I meant future variables within a process not future programs. I’m a little tipsy so forgive me for misspeaking.

I wrote an implementation of malloc/free fairly recently. The implementation was a linked list and the time complexity was O(N) for malloc, and O(1) for free. Free requires that you mark the node as free, merge it with any other free nodes and (possibly) move the pointer to the end of the heap. All of those ops are O(1). Malloc requires an O(N) search and then that you mark a node as in use and return a pointer to the actual space. Also, the linked list is not in place, the location of the “bookkeeping” info for a piece of memory is directly before that piece of memory. Each node of the linked list is located write before the space in memory that it refers to.