Section 10 Dynamic Memory and ADTs

Heap: (Slides 2-4)
- Describe the heap.
- What are the consequence of the fact that the heap is finite?

Malloc: (Slides 5-11)
- Use malloc to allocate memory.  
- Why should we always use sizeof with malloc?
- How do we check whether a call to malloc is successful?
- What are the initial values in a memory block returned by malloc?
- What is the running time of malloc?

Free and memory leaks: (Slides 12-15)
- Use free to free allocated memory.
- Why is it good style to set a pointer to NULL after freeing the memory block?
- What is a memory leak?
- Describe scenarios in which memory leaks occur.
- Describe ways of preventing memory leaks.
- What does garbage collection mean?  Does C have a built-in garbage collector?

An example of using malloc and free: Merge sort (Slides 16-18)

An example of returning a pointer: building an array and strdup (Slides 19-20)

Resizable arrays in the heap: (Slides 21-27)
- Use realloc to allocate memory of a different size.
- After realloc, describe which pointer is valid and which point is invalid.
- What is the runtime of realloc?
- Create and manipulate resizable arrays in the heap.
- An example: reading in a string of unknown size (avoiding buffer overrun)

The doubling strategy: (Slides 28-30)
- What is the doubling strategy?
- What is the advantage of using the doubling strategy versus increasing the size of the array by one at each iteration?
- With the doubling strategy, what is the total runtime and the average runtime for each iteration?  Why?

Structs in the heap:
- Completing the stopwatch module (Slides 31-33)
- Document side effects relating to dynamic memory.
- A better version of the stack ADT (Slides 34-38)