The limited exposure to linked lists in 445 is a shame.

In this lab, you’ll write a simple linked list. You’ll have to use malloc and free to make it.

Project 2 is gonna involve linked lists, so this lab is a way for you to refresh yourself. Please make sure you understand this stuff thoroughly.


Crash course on malloc and free

We’ll learn about the heap in detail on Wednesday/Thursday. But you can get started on the lab now. Right? :)

malloc is like C’s new. It allocates space on the heap, and gives you a pointer to that space.

But C has no garbage collection, so every piece of memory you malloc, you must ultimately free.

Using malloc is straightforward: you tell it how many bytes you need, and it returns a pointer to a brand new piece of memory that is at least that big:

// one int is sizeof(int).
// multiply that by 10, and you have room for an array of 10 ints.
int* array = malloc(sizeof(int) * 10);

When you’re done with a piece of memory, just pass the pointer to free:

free(array);

The lab

Here is the Node struct that you will be using:

typedef struct Node {
	int value;
	struct Node* next;
} Node;

Here are the functions you will implement:

Hints:

Read these. It’s not “cheating”, it’s important information.


main

Here’s a small driver I wrote. (You can put all your code in one lab3.c file.) Feel free to comment stuff out, add more stuff etc. to test your code more thoroughly.

int main() {
	// The comments at the ends of the lines show what list_print should output.
	Node* head = create_node(1);
	list_print(head);                  // 1
	Node* end = list_append(head, 2);
	list_print(head);                  // 1 -> 2
	end->next = create_node(3);
	list_print(head);                  // 1 -> 2 -> 3
	head = list_prepend(head, 0);
	list_print(head);                  // 0 -> 1 -> 2 -> 3
	list_append(head, 4);
	list_print(head);                  // 0 -> 1 -> 2 -> 3 -> 4
	list_append(head, 5);
	list_print(head);                  // 0 -> 1 -> 2 -> 3 -> 4 -> 5

	head = list_remove(head, 5);
	list_print(head);                  // 0 -> 1 -> 2 -> 3 -> 4
	head = list_remove(head, 3);
	list_print(head);                  // 0 -> 1 -> 2 -> 4
	head = list_remove(head, 0);
	list_print(head);                  // 1 -> 2 -> 4

	list_free(head);

	return 0;
}

valgrind

valgrind is a helpful tool. It can analyze your program’s memory accesses, heap allocations, frees etc. at runtime to make sure you’re not doing anything weird. It can help you find memory leaks, array-out-of-bounds errors, buffer overflows, double-frees, using freed heap memory etc…

To use it, you just put valgrind before the program you want to run:

valgrind ./lab3

It will print lines that look like ==12345== that will point out issues with your program as it runs.

Common issues:


Submission

You get the idea by now. (But replace lab1 with lab3.)