Description
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:
-
Node*
create_node(int value)-
it will
malloc
aNode
, set its value tovalue
, set its next toNULL
, and return it.-
to
malloc
an instanceNode
, you need to allocatesizeof(Node)
bytes. -
you can directly assign the result of
malloc
into aNode*
variable.
-
-
-
void
list_print(Node* head)-
head
points to the head of a linked list. -
it will print the values of all the items in the list in this format:
5
-> 8 -> 2 -> 1
-
-
Node*
list_append(Node* head, int value)-
head
points to the head of a linked list. -
it will go to the end of the linked list, use
create_node(value)
, and put that new node at the end of the linked list. -
then it will return that new node.
-
-
Node*
list_prepend(Node* head, int value)-
head
points to the head of a linked list. -
it will use
create_node(value)
, make that node point tohead
, and return that new node. -
important: this function should return the new head of the list, not the old one.
-
-
void
list_free(Node* head)-
head
points to the head of a linked list, or NULL. -
if
head
is NULL, do nothing. -
otherwise, free all the nodes in the list.
-
do not free a node before you get its
next
field.
-
-
-
Node*
list_remove(Node* head, int value)-
head
points to the head of a linked list. -
it will search for a node whose value
== value
.-
if it finds that node, it will remove it from the list and
free
it.-
there are special cases for removing the head and tail!
-
-
if it doesn’t find that node, nothing happens.
-
-
it will return the head of the list (which may have changed or become NULL!)
-
Hints:
Read these. It’s not “cheating”, it’s important information.
-
Don’t write everything at once and then test it. Write one function, test that, and repeat.
-
for
loops fit together with linked lists very nicely. -
Write
list_print
as soon as you can, so you can test your code easier. -
Don’t worry about
head == NULL
for anything other thanlist_free
. -
For
list_remove
, when you are iterating over the list, don’t move your pointer too far ahead…-
(You have to know the previous node to remove a node.)
-
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:
-
“Invalid read/write of size n”
-
you are trying to access an invalid pointer.
-
keep reading: it will tell you where the read/write happens. Like, the file and line!
-
-
“LEAK SUMMARY”
-
you have a memory leak.
-
basically, the problem is in
list_free
.-
it says “Rerun with –leak-check=full to see details of leaked memory” but if you do that, it just shows where the memory was allocated, which isn’t too useful for you.
-
-
-
“Invalid free() / delete / delete[] / realloc()”
-
you are trying to call
free()
on something that you aren’t allowed to. -
like something that you already freed.
-
or a pointer that doesn’t point to the heap.
-
keep reading the error!!!
-