Programming Fundamentals

Tutorial Overview:

• Part 1: Removing nodes from linked lists
• Part 2: Kahoot
• Part 3: Linked List Exercises

Check in week

Reminder: This week is a check-in week, so please make sure to stay around in the lab time for your one-on-one with one of your Tutors.

Part 0: Assignment 2 (5 mins)

In this section, we will briefly discuss how assignment 2 is going.

Part 1: Removing nodes from linked lists (20 mins)

Freeing memory is an important part of using C, and of writing linked lists. In this section we will explore the use of free when working with linked lists by creating a remove_head and remove_tail function. We will also revise how to and why we use the --leak-check option when compiling our programs.

To do this we will continue working off of last weeks tutorial code and write an implementation for the following function:

// Removes the head of a linked list
//
// Parameters:
//      head: A pointer to the head of the linked list
//
// Returns:
//      A pointer to the head of the linked list
struct node *remove_head(struct node *head) {
    return NULL;
}

// Removes the tail of a linked list
//
// Parameters:
//      head: A pointer to the head of the linked list
//
// Returns:
//      A pointer to the head of the linked list
struct node *remove_tail(struct node *head) {
    return NULL;
}

Part 2: Kahoot (10 mins)

Join the class kahoot here. This kahoot will revisit some of the things we have seen while working with linked lists.

Part 3: Linked List Exercises (25 mins)

In groups write psuedocode the following functions:

List evens

int list_evens(struct node *head1, struct node *head2)

Given two linked lists:

• return 0, if neither list contains even numbers.
• return 1, if one list contains even numbers, but the other does not.
• return -1, if both lists contain even numbers.

List ordered insert

struct node *list_ordered_insert(struct node *head, int data)

Given a linked list that is ordered in acending order and a value to insert, insert the value into the list that will allow the list to remain in acending order.

List delete smallest

struct node *list_delete_smallest(struct node *head)

Given a linked list, remove the node with the smallest value from the linked list and return the new head of the list.

List copy

struct node *list_copy(struct node *head1)

Given a linked list, make a copy of the list and free the old list and return the new head of the list.

List append

struct node *list_append(struct node *head1, struct node *head2)

Given two linked lists, append list2 to list1.

List reverse

struct node *list_reverse(struct node *head)

Given a linked list, reverse the list and return the new head of the list.

Find intersection

struct node *list_find_intersection(struct node *head1, struct node *head2)

Given two linked lists, return a new list that is constructed of nodes containing any values that appear in both lists.

Count occurences

int list_count_occurrences(struct node *head, int data)

Given a linked list and a value, count the number of times that value appears in the linked list.