Task $1-$ Friending :) $$

Implement the FbFriend$()$ function in Fb$.$c$,$ which takes the names of two people, and friends them if they are not already friends. The function should return true if the people were not friends and were successfully friended, and false if the two people were already friends.

You should implement your function so that the adjacency lists are kept in ascending order. For example, in the example in the Background section, since Harry $(0)$ is friends with Ron $(1)$ and Hermione $(2),1$ should appear before $2$ in Harry's adjacency list.

You can assume that the two people exist and are not the same person.

We have provided a function newAdjNode which creates a new adjacency list node.

Is inserting into an adjacency list similar to a problem that you have solved in a previous lab exercise?

Once you think you've got the function working, test it by recompiling with make and running the runFb program. You can test whether your function works using the $+($add person$),$ f $($friend$)$ and s $($friendship status$)$ commands. For example:

$./$runFb

Friendbook v$1\mathrm{.}0$

Enter $?$ to see the list of commands.

$>+$ Harry

Harry was successfully added to Friendbook!

$>+$ Ron

Ron was successfully added to Friendbook!

$>+$ Hermione

Hermione was successfully added to Friendbook!

$>$ s Ron Hermione

Ron and Hermione are not friends.

$>$ f Ron Hermione

Successfully friended Ron and Hermione!

$>$ s Ron Hermione

Ron and Hermione are friends.

$>$ s Harry Ron

Harry and Ron are not friends.

$>$ f Harry Ron

Successfully friended Harry and Ron!

$>$ s Harry Ron

Harry and Ron are friends.

$>$ s Ron Hermione

Ron and Hermione are friends.

$>$ s Harry Hermione

Harry and Hermione are not friends.

You can run the above test case with the following command:

$./$runFb $-$e $<$ tests$/$friend$-1.$txt

This command runs the $./$runFb program and causes it to read Friendbook commands from the file tests$/$friend$-1.$txt$.$ The $-$e option $($which stands for "echo"$)$ causes the program to print out the commands to the terminal as they are being run, which makes it easy to see which operations are being performed.

When you're certain that the function works correctly, determine its worst case time complexity and write in analysis.txt along with an explanation. The time complexity should be in terms of

n

$,$ where

n

is the total number of people.