Demo 1

Below you will find a crude implementation of a social network in C. It doesn't work though. Why? (From Lecture Notes)

#include #include struct contact { char name[20]; int age; }; typedef struct contact Contact; struct profile { char name[20]; int age; char hobbies[100]; struct contact friends[10]; }; typedef struct profile Profile; int main() { Profile p; Contact p2,p3; strcpy(p.name,"John"); p.age = 20; strcpy(p2.name,"Chandra"); p2.age = 19; strcpy(p3.name,"Jingyi"); p3.age = 25; p.friends[0] = p2; p.friends[1] = p3; p3.age = 26; printf("First friend of %s: %s, age %d ",p.name,p.friends[0].name,p.friends[0].age); printf("Second friend of %s: %s, age %d ",p.name,p.friends[1].name,p.friends[1].age); }

Demo 2

This is an incomplete implementation of a linked list. Your instructor will walk you through the code step by step

#include #include // <--- remember this typedef struct node { int data; // just generic, meaningless data! struct node *next; } Node; Node* insert(Node* listHead, int dataToInsert) { // we need to return a new head of linkedlist because // the head may change after insertion if (listHead == NULL) { // list is emtpy, let's insert our first element! printf("inserting first element with data %d ",dataToInsert); Node *newNode = malloc(sizeof(Node)); newNode->data = dataToInsert; newNode->next = NULL; return newNode; } else { // list is not empty, let's insert at the end printf("inserting element with data %d ",dataToInsert); Node *current = listHead; // CAUTION! while (current != NULL) { if (current->next == NULL) { // if it's end of list... Node *newNode = malloc(sizeof(Node)); newNode->data = dataToInsert; newNode->next = NULL; current->next = newNode; return listHead; } else { // otherwise... current = current->next; } } } } void printList(Node* listHead) { printf("printing list: "); Node *current = listHead; while (current != NULL) { printf("%d ",current->data); current = current->next; } printf(" "); }

void printCount(Node* listHead) {

printf("printing count: ");

// TODO: implement

}

Node* deleteFirst(Node* listHead) { printf("deleting first element from list: "); // TODO: implement return listHead; }

Node* deleteLast(Node* listHead) { printf("deleting last element from list: "); // TODO: implement

return listHead; } Node* deleteSpecific(Node *listHead, int dataValue) { // assume data to delete always exists and is always unique in // this exercise printf("deleting %d from list ", dataValue); // TODO: implement! return listHead; } void printBackwardsFromZero(Node* listHead) { printf("printing list in backwards from the first 0 element (or end of list): "); // TODO: implement.. printf(" "); } int main() { Node *myHead = NULL; // head of the linked list, not really MY HEAD! myHead = insert(myHead, 2000); myHead = insert(myHead, 2018); printList(myHead); myHead = insert(myHead, 2001); myHead = insert(myHead, 1998); myHead = insert(myHead, 0); myHead = insert(myHead, 1999); myHead = insert(myHead, 2021); myHead = insert(myHead, 2020); printList(myHead); printCount(myHead);

myHead = deleteFirst(myHead); printList(myHead); myHead = deleteLast(myHead); printList(myHead); myHead = deleteSpecific(myHead, 1998); printList(myHead); myHead = deleteSpecific(myHead, 2018); printList(myHead); printBackwardsFromZero(myHead); return 0; }

In the above example, we have a partial implementation of linked list in C. Don't be scared of the pointers!

The main function is not fully working as some code is not implemented yet. However, we can see that the insert and print functions are working properly.

Notice that:

1. As mentioned, we reference a linked list by the list's first Node ("head")
2. Please notice the various use of pointers in the example; do you recall the 3 rules of using pointers? (Please refer to lecture notes if not)
3. There are two insertion cases - if the list is empty, we need to create a new Node as the head; otherwise, we will append the Node in the end in this example
4. We NEED to return a pointer to Node in insert because the list head pointer may change! We need to do the same for every operation that may change the list head

Problem 3

Please try to implement the second unimplemented function deleteLast that deletes last element in the list. It will be slightly harder than deleteFirst.

Hint: If a node's next pointer points to NULL, it's the last node

Hint 2: To delete the last node, we will point the second last element's next pointer to NULL

If successful, you will see that when we call that in main, it will delete the last element and have the following output

inserting first element with data 2000 inserting element with data 2018 printing list: 2000 2018 inserting element with data 2001 inserting element with data 1998 inserting element with data 0 inserting element with data 1999 inserting element with data 2021 inserting element with data 2020 printing list: 2000 2018 2001 1998 0 1999 2021 2020 printing count: 8 deleting first element from list: printing list: 2018 2001 1998 0 1999 2021 2020 deleting last element from list: printing list: 2018 2001 1998 0 1999 2021

...

Please paste the finished function below. It will be great if it can handle empty list or list with only one element.