Programming Fundamentals

Tutorial Overview:

Reminder: Assignment 2 released

If you have any questions about Assignment 2, feel free to ask them now.

Reminder: Lab Exam

This week is the lab exam meaning that in the first hour of the lab you will sit a exam. The purpose of the exam is to provide practice for exam hurdle style questions and get them familiar with the exam servers. This exam can only be sat in person and there is no online offering. If you cannot attend an in-person class this week please email the course at cs1511@unsw.edu.au. Please do not apply for special considerations for this activity.

Part 1: Malloc and free (15 mins)

In this section we'll visit malloc and free.

Group activity

Using your knowledge of malloc() and sizeof(), write up code to malloc the following:

struct my_struct {
    int number;
    char letter;
    double another_number;
}

Part 2: Diagramming Linked Lists (10 mins)

In this activity we will run through the following instructions and build a diagram.

malloc memory for a new node called node1

node1 data = 3
node1 next = NULL

make the head pointer points to node1

malloc memory for a new node called node2

node2 data = 9
node2 next = NULL

add node2 to the tail of the list, making node1 next point to node2

malloc memory for a new node called node3

node3 data = 5
node3 next = NULL

add node3 to the head of the list, making node3 next point to the current head of the list
make the head point to node3

Part 3: Programming linked lists (30 mins)

Given the starter code:

we will implement functions to create a node, insert a node at the tail of a linked list, insert a node at the head of a linked list and find the length of a linked list.

linked_lists.h
// linked_lists.h
// This program was written by Sofia De Bellis (z5418801), on March 2024
// Header file for simple linked lists functions

struct node {
    // The data stored in the node
    int data;
    // Pointer to the next node in the linked list
    struct node *next;
};

// Creates a new node
//
// Parameters:
//      data: The data to be stored in the new node
//
// Returns:
//      A pointer to the new node
struct node *create_node(int data);

// Inserts a new node at the head of a linked list
//
// Parameters:
//      head: A pointer to the head of the linked list
//      data: The data to be stored in the new node
//
// Returns:
//      A pointer to the new head of the linked list
struct node *insert_head(struct node *head, int data);

// Inserts a new node at the tail of a linked list
//
// Parameters:
//      head: A pointer to the head of the linked list
//      data: The data to be stored in the new node
//
// Returns:
//      A pointer to the head of the linked list
struct node *insert_tail(struct node *head, int data);

// Traverses a linked list and prints the data in each node
//
// Parameters:
//      head: A pointer to the head of the linked list
//
// Returns:
//      None
void print_list(struct node *head);

// Finds the number of nodes in a linked list
//
// Parameters:
//      head: A pointer to the head of the linked list
//
// Returns:
//      The number of nodes in the linked list
int list_length(struct node *head);
linked_lists.c
// linked_list.c
// This program was written by YOUR-NAME (zID)
// Implementation for simple linked lists functions

#include <stdio.h>
#include <stdlib.h>

#include "linked_lists.h"

struct node *create_node(int data) {
    // TODO
    exit(1);
}

struct node *insert_head(struct node *head, int data) {
    // TODO
    exit(1);
}

struct node *insert_tail(struct node *head, int data) {
    // TODO
    exit(1);
}

void print_list(struct node *head) {
    // Set current to be the first node in the list
    struct node *current = head;
    
    // Traverse the linked list and print each node 
    // until we reach the end of the list
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("X\n");
}

int list_length(struct node *head) {
    // TODO
    exit(1);
}
main.c
// main.c
// This program was written by YOUR-NAME (zID)
// // Program to test linked lists functions

#include <stdio.h>
#include <stdlib.h>

#include "linked_lists.h"

int main(void) {

    // Create a pointer to the head of the linked list
    struct node *head = NULL;

    // Insert a node at the beginning of the linked list
    head = insert_head(head, 10);

    // Insert a node at the beginning of the linked list
    head = insert_head(head, 5);

    // Insert a node at the end of the linked list
    head = insert_tail(head, 15);

    // Insert a node at the end of the linked list
    head = insert_tail(head, 20);

    // Print the linked list
    print_list(head);

    // Calculate and print the length of the linked list
    int length = list_length(head);
    printf("There are %d nodes in the list\n", length);

    return 0;
}