© Thomas Kunz 2000
SCE 574
220
Heap
List
- malloc
would return
the first free block that
can satisfy the request, and
remove it from the list
- free would
return the block to the list
Heap
äHeap:
äPre-allocated area
of memory partitioned into blocks
äLinked list of
blocks of various sizes
äCould even start
with a single large block
äOperations: malloc
or new and free or delete
äTime complexity for operations depends on the choice of data structure
äCould have a single
list, multiple lists, doubly linked lists
äList(s) may be
sorted, or not
äMay split blocks if
they are large compared to request sizes
äCan lead to
fragmentation: all blocks become small
äMay have to merge
blocks if none are large enough to satisfy a
request
64
bytes
64
bytes
128
bytes
4096
bytes