Lab 10: Linked Lists

Due by the end of class

Introduction

In this lab you will use what you have learned about structs and dynamic memory allocation to implement a singly linked list. The implementation will be very similar to what we have done in class.

Lab Exercise

Your program should display a menu with the following options.

  1. Add new element
    The program should read an int value from the user and add it at to the head of the linked list.

  2. Delete element
    The program should read an int value from the user and delete the first occurrence of that integer from the linked list. The memory should be freed when the node is deleted. Do nothing if the int value is not found in the list.

  3. Print list
    Traverse the entire linked list and print each value separated by a space.

  4. Exit
    Free all the memory in the linked list and exit the program.

To implement these choices, it's recommended that you complete functions with the following signatures, whose operations are described in comments. 

// Adds value to the head of the list
// Returns new head
LinkNode* add(LinkNode* head, int value);

// Delete first occurrence of value from the list
// Returns new head
LinkNode* delete(LinkNode* head, int value);

// Print all the values in the list
void print(LinkNode* head);

// Free all the memory in the list
void empty(LinkNode* head);

Other Details

Each node of the linked data structure will be represented by a struct (called LinkNode). The struct should have two fields, a pointer to the next node and an integer for the data stored at the node. You should use malloc() to allocate space for each new node as you add it to the list. Be sure to free any allocated memory when it is no longer needed.

You may use either the readInt() function from earlier labs or scanf() to read int values.

Make sure you include stdlib.h and stdio.h.

Call your executable list and create a makefile which generates it.

Sample Output

Below is sample output for execution of the program. User input is given in green.

1. Add new element
2. Delete element
3. Print list
4. Exit
3

1. Add new element
2. Delete element
3. Print list
4. Exit
1
57
1. Add new element
2. Delete element
3. Print list
4. Exit
3
57
1. Add new element
2. Delete element
3. Print list
4. Exit
2
57
1. Add new element
2. Delete element
3. Print list
4. Exit
3

1. Add new element
2. Delete element
3. Print list
4. Exit
1
3
1. Add new element
2. Delete element
3. Print list
4. Exit
1
5
1. Add new element
2. Delete element
3. Print list
4. Exit
1
7
1. Add new element
2. Delete element
3. Print list
4. Exit
1
5
1. Add new element
2. Delete element
3. Print list
4. Exit
3
5 7 5 3
1. Add new element
2. Delete element
3. Print list
4. Exit
1
9
1. Add new element
2. Delete element
3. Print list
4. Exit
3
9 5 7 5 3
1. Add new element
2. Delete element
3. Print list
4. Exit
2
5
1. Add new element
2. Delete element
3. Print list
4. Exit
3
9 7 5 3
1. Add new element
2. Delete element
3. Print list
4. Exit
4

Turn In

Zip the contents of your lab directory, including the makefile and the source C file. Upload this zip file to Brightspace. Do not include any object files or executables. Running the make command must compile the required C source code file and generate an executable named list.

All work must be done individually. Never look at someone else's code. Please refer to the course policies if you have any questions about academic integrity. If you have trouble with the assignment, I am always available for assistance.