Dynamic Data Structures
- We used
malloc()and other functions to dynamically allocate storage for arrays - Now we want to do the same for data structures
- Built using self-referential structures
i.e. structs that contain pointers to other structs - Memory for each part is allocated/deallocated separately and linked together via pointers
Stack (FILO)
- A stack is an example of a simple dynamic data structure
- Maintains a simple list of items by adding new items and removing existing items from head of the list
- This is known as First-In-Last-Out (FILO) data structure
typedef struct _s {
int value;
struct _s *next;
} STACKITEM;
STACKITEM *stack = NULL; // Empty stackAdding Items to the Stack
- As program’s execution progresses, → need to add/remove items
- Push items onto the stack and pop existing items from the stack
Push (add):
void push_item(int newvalue) {
STACKITEM *new = malloc(sizeof(STACKITEM));
new->value = newvalue;
new->next = stack;
stack = new;
}Pop (remove):
int pop_item(void) {
STACKITEM *old = stack;
int value = old->value;
stack = old->next;
free(old);
return value;
}We need to consider what happens if the stack is empty
- Use a NULL pointer → represent condition of the stack being empty
There are many other examples of dynamic data structures in the slides