Week 01 Tutorial Answers

Revision of Pointers and Linked Lists

Introductions
- Introduce yourself to the other people in the tutorial class
- Discuss what you learned from COMP1511
- Discuss what parts you're still unsure of
Answer:

No answers are available for this question.

Pointers Revision

In these questions, you can use this template to draw your own diagrams. Click on the pencil icon under the diagram to edit it.

Using a diagram, show how the state of memory changes after each line of code is executed.

int main(void) {
	int a = 5;
	int b = 123;

	int *pa = &a;
	int *pb = &b;

	*pa = 6;
	*pb = 234;

	int c = *pa;
	*pa = *pb;
	*pb = c;

	pa = pb;
	*pa = 345;
}

Answer:

The state of memory after line 6:

The state of memory after line 9 (*pa = 6, *pb = 234):

The state of memory after line 11 (int c = *pa):

The state of memory after line 12 (*pa = *pb):

The state of memory after line 13 (*pb = c):

The state of memory after line 15 (pa = pb):

The state of memory after line 16 (*pa = 345):

Explain why the swap() function here does not work as intended:
```
int main(void) {
	int a = 5;
	int b = 7;
	swap(a, b);
	printf("a = %d, b = %d\n", a, b);
}

void swap(int a, int b) {
	int tmp = a;
	a = b;
	b = tmp;
}
```
Modify the code so that it works as intended. Show how the new version works using a diagram.
Answer:
The swap() function is intended to swap the values of a and b in the main function so that the program prints out:
```
a = 7, b = 5
```
The function doesn't work because in C, all values (except arrays) are passed by copy into functions. The swap function receives a copy of the integers so changing the integers in the swap function doesn't change the integers in the main function.

To fix the program, the swap function should be modified so that we can pass in pointers to the integers rather than the integers themselves.
1 2 3 4 5 6 7 8 9 10 11 12
int main(void) { int a = 5; int b = 7; swap(&a, &b); printf("a = %d, b = %d\n", a, b); } void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; }
The state of memory at the beginning of the swap function:

The state of memory after line 9 (int tmp = *a):

The state of memory after line 10 (*a = *b):

The state of memory after line 11 (*b = tmp):

Malloc Revision

In these questions, you can use this template to visualise the code execution. Click on the pencil icon under the diagram to edit it.

What does malloc do?
Answer:
malloc is a function that a program can use to allocate (i.e., reserve) memory on the heap.

What is the heap? The memory used by a running program is divided into several sections:
- Code: This is where the machine code of the program is located.
- Data: This is where global and static variables are located.
- Heap: This is where dynamically allocated memory (i.e., memory allocated by malloc) is located.
- Stack: This is where functions and local variables (i.e., variables declared inside functions) are located.
The difference between memory allocated on the stack and memory allocated on the heap is that:
- Memory on the stack is automatically allocated and de-allocated:
  - When a function is called and when it returns
  - When a variable is declared and when the end of the block in which it was declared is reached
- Memory on the heap is allocated by malloc and is only de-allocated when the program frees it using the free function.
Therefore, malloc is useful when a function allocates some memory that still needs to be used after the function has returned. An example of this is when a function needs to create and return an array - if the array was not allocated using malloc, then it would be automatically de-allocated once the function returns.

malloc is also useful when the amount of memory that needs to be allocated is not known in advance, for example, when you don't know how big of an array you'll need, or you don't know how many linked list nodes you'll need to create. This is because variables you declare in functions, such as int a or int arr[10], have a fixed size, so they are not suitable if you don't know how much memory you will need.
Explain how these two pieces of code differ:
int main(void) { stackInt(); } void stackInt(void) { int a = 5; }
int main(void) { heapInt(); } void heapInt(void) { int *a = malloc(sizeof(int)); *a = 5; }
Answer:

The stackInt function allocates an int on the stack, which is automatically de-allocated once the function returns. Meanwhile, the heapInt function allocates an int on the heap, which remains on the heap once the function returns.

stackInt

The state of memory at the end of the stackInt function:

The state of memory after the stackInt function has returned:

heapInt

The state of memory at the end of the heapInt function:

The state of memory after the heapInt function has returned:
Modify the code below so that it allocates the struct on the heap, instead of the stack.
```
struct node {
	int value;
	struct node *next;
};

int main(void) {
	struct node n;
	n.value = 42;
	n.next = NULL;
}
```
Answer:
Remember that to access struct fields through a pointer, you need to use the arrow operator (->).
```
int main(void) {
	struct node *n = malloc(sizeof(struct node));
	n->value = 42;
	n->next = NULL;
}
```
This is what allocating the node struct on the stack looks like:

This is what allocating the node struct on the heap looks like:
The following code creates an array of 5 integers on the stack and uses it to store some values. How can you allocate the array on the heap instead?
```
int main(void) {
	int a[5];
	for (int i = 0; i < 5; i++) {
		a[i] = 42;
	}
}
```
Answer:
We need to specify that we want to allocate space for 5 ints by multiplying sizeof(int) by 5. Notice that we index into an array the same way regardless of how the array was allocated.
```
int main(void) {
	int *a = malloc(5 * sizeof(int));
	for (int i = 0; i < 5; i++) {
		a[i] = 42;
	}
}
```
This is what allocating an array on the stack looks like:

This is what allocating an array on the heap looks like:

Linked List Revision

Consider the following two linked list representations:

// Representation 1
struct node {
    int value;
    struct node *next;
};





int listLength(struct node *list);

// Representation 2
struct node {
    int value;
    struct node *next;
};

struct list {
    struct node *head;
};

int listLength(struct list *list);

Compare the two representations diagramatically.
How is an empty list represented in each case?
What are the advantages of having a separate list struct as in Representation 2?

Answer:

Representation 1:
Representation 2:
Representation 1: An empty list is simply represented by a NULL pointer.
Representation 2: An empty list is represented by a pointer to a struct list that contains a NULL pointer in its head field.
Some advantages:
- Functions that modify the list don't need to return the updated list.
- The list struct can be used to store additional information about the list (metadata), which can improve performance. For example, if the list struct contained a field for the length of the list, a function that gets the length of the list could simply return this value instead of iterating through the entire list. If the list struct contained a pointer to the last node of the list (usually called last or tail), then this pointer can be used to easily insert items at the end of the list. The tradeoff is that these fields need to be constantly updated to be consistent with the list.

Consider the following simple linked list representation:

struct node {
	int value;
	struct node *next;
};

Write a function to sum the values in the list. Implement it first using while and then using for.

Answer:

Version using while:

int sumList(struct node *list) {
	struct node *curr = list;
	int sum = 0;
	while (curr != NULL) {
		sum += curr->value;
		curr = curr->next;
	}
	return sum;
}

Version using for:

int sumList(struct node *list) {
	int sum = 0;
	for (struct node *curr = list; curr != NULL; curr = curr->next) {
		sum += curr->value;
	}
	return sum;
}

Implement a function to delete the first instance of a value from a list, if it exists. Use the following list representation and prototype:

struct node {
    int value;
    struct node *next;
};

struct node *listDelete(struct node *list, int value);

How would the implementation and prototype be different if the following list representation was used instead?

struct node {
    int value;
    struct node *next;
};

struct list {
	struct node *head;
};

Answer:

struct node *listDelete(struct node *list, int value) {
    // list is empty
    if (list == NULL) {
        return NULL;
    
    // deleting first value
    } else if (list->value == value) {
        struct node *newHead = list->next;
        free(list);
        return newHead;
    
    // deleting middle value
    } else {
        struct node *curr = list;
        while (curr->next != NULL) {
            if (curr->next->value == value) {
                struct node *toDelete = curr->next;
                curr->next = toDelete->next;
                free(toDelete);
                break;
            }
            curr = curr->next;
        }
        return list;
    }
}

If the linked list was represented by a struct containing a pointer to the first node (which we usually call a wrapper or container struct), instead of just a pointer to the first node, then our delete function no longer needs to return a pointer to the list, because if the first node of the list changes, we can simply change the pointer in the list struct.

void listDelete(struct list *list, int value) {
    // list is empty
    if (list->head == NULL) {
        return;
    
    // deleting first value
    } else if (list->head->value == value) {
        struct node *newHead = list->head->next;
        free(list->head);
        list->head = newHead;
    
    // deleting middle value
    } else {
        struct node *curr = list->head;
        while (curr->next != NULL) {
            if (curr->next->value == value) {
                struct node *toDelete = curr->next;
                curr->next = toDelete->next;
                free(toDelete);
                break;
            }
            curr = curr->next;
        }
    }
}

Before starting this week's lab, make sure you properly understand the following topics:

Structs (see videos on structs)
Pointers (see videos on pointers)
Malloc (see videos on malloc)
Linked Lists (see videos on linked lists)