If you haven’t done linked lists before… who was your 445 instructor???

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.

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.)