Assignment $3$: Recursion and Linked Lists in C

The purpose of this assignment is to work with recursion and linked lists in the C programming language. You will be required to implement various functions using iteration as well as recursion to manipulate linked lists.

Instructions:

$1.$ Implement the following functions:

a$)$ int listLength $($Node$*$ head$)$: This function should take the head pointer of a linked list as input and return the length Leing iteration.

b$)$int listLength$\_$recursive $($Node$*$ head$)$: This function should take the head pointer of a linked list as input and return the length recursively.

c$)$ int listSum $($Node$*$ head$)$: This function should take the head pointer of a linked list containing integer values and return the sum of all elements in the list using iteration.

d$)$ int listSum

$\_$recursive$($Node$*$ head$)$: This function should take the head pointer of a

linked list containing integer values and return the sum of all elements in the list recursively.

e$)$ void printList $($Node$*$ head$)$: This function should take the head pointer of a linked list and print the elements using iteration.

f$)$ void printList$\_$ recursive $($Node$*$ head$)$: This function should take the head pointer of a linked list and print the elements using recursion.

g$)$ void printListReverse $($Node$*$ head$)$: This function should take the head pointer of a linked list and print the elements in reverse order using iteration.

h$)$ void printListReverse$\_$recursive $($Node$*$ head$)$: This function should take the head pointer of a linked list and print the elements in reverse order using recursion.

$2.$ Define the structure Node for a singly$$linked$$list:typedef struct Node $\{$

int data;

struct Node$*$ next;

$\}$ Node;

$3.$ Implement a function Node$*$ createNode $($int data$)$ that creates a new node with the given data and returns its pointer.

$4.$ Implement a function Node$*$ insertNode $($Node$*$ head, int data$)$ that inserts a new node with the given data at the beginning of the linked list and returns the updated head pointer.

$5.$ Write a main $()$ function to test your implemented functions. Create a linked list by inserting nodes using the insertNode$()$ function and perform the following operations:

a$)$ Insert at least five nodes with integer values of your choice.

b$)$ Print the linked list using printList $()$ and printList$\_$recursive$()$

c$)$ Call the listLength$()$ and listLength$\_$recursive $()$ functions and display the length$$of$$the$$list$.$d$)$ Call the listSum$()$ and listSum$\_$recursive$()$ functions and display the sum of all elements in the list.

e$)$ Call the printListReverse$()$ and printListReverse$\_$recursive $()$ functions and print the elements of the linked list in reverse order.

$6.$ Perform a Big O analysis of all the functions, except the main $()$ function. Explain clearly and precisely how you calculated the Big O$.$

Submission:

$1.$ Write well$-$commented and organized code. Clearly explain your algorithm, logic and purpose of each function in multi$-$line comments above each function.

$2.$ Include necessary header files and function prototypes.

$3.$ Test your program with different scenarios and edge cases to ensure its correctness.

$4.$ Proper memory management is required, if necessary.

$5.$ Include a text file or a document explaining your approach and any challenges you encountered during the implementation.

$6.$ Submit a zip folder containing a single C source file named assignment. c as well as a big$-$o$-$analysis.pdf$$document$.$