# Linked List using C Assignment Solution

## Node and Linked List assignment

PS3.0: Node and List

Before you can work on the list operations, you'll need to write a c assignment that creates both a node and a list. The node should be responsible for node-y things, and the list for list-y things, in other words, they won't know much about each other. The list will accept a filled-in node and add it to the list.

The node should be a struct, and it looks about the same as the one we've seen in lectures:

typedef struct node { int value; node* next;

}

Here are the signatures for both node's and list's functions. Note that this is just the starting set of functions; each problem will require you to (possibly) add new functions to one or both of list and node.

For nodes:

node* createNode(int value); //Create a new node with a given value

For lists:

bool addNode(node* node); //Add a node to the list node* findNode(int value); //Find a node in the list bool deleteNode (node* node); //Delete a node in the list

void printList(void); //Print the values in the list

The returned boolean values should indicate the success or failure of the operation.

PS3.1 Add a set of nodes (in main. c)

Create a singly linked list from this array:

[89, 39, 18, 96, 71, 25, 2, 55, 60, -8, 9, 42, 69, 96, 24]

Read each value in turn and call created, then addNode. Nodes must be dynamically allocated using malloc().

Print the list.

PS3.2 Delete the largest nodes

From main, ask the list to delete all of the nodes that contain the largest value in the list.

The signature for this function will be similar to void deleteLargest(void);

On the listing side, deleteLargest should call an internal list function to find *all* nodes that contain the same largest value (there should be more than one), and then call the internal deleteNode function to delete all of the nodes found. Hint: You can use an array to collect the largest nodes as you find them.

Print the list.

PS3.3 Count the nodes in the list

From the main, ask the list to return the number of nodes in the list, and print the value.

PS3.4 Sort the list

From main, ask the list to sort itself. Use a bubble-sort algorithm:

• Starting from the top of the list, compare the value in the first node with the value in the second node
• If the value in the second node is smaller, swap the two nodes, otherwise leave them in place
• Move to the second node and compare its value with the third node, swapping them if necessary
• Repeat this until you've reached the end of the list
• Next, go back to the top and do it all over again
• The list is sorted when you walk the entire list from top to bottom and do not perform any swaps

The list should be sorted in place. In other words, don't use a second list. Print the list

Solution:

List:

```#include < stdio.h> #include < stdlib.h> #include "list.h" node *head = NULL; //Add a node to the list bool addNode(node *new_node) { if (head == NULL) { // This is add node to empty list. Just assign head to new node head = new_node; } else { // This is list with elment. Try to add new node to end of list node *current_node = head; while (current_node->next != NULL) { current_node = current_node->next; } // Now we are in end of list. Just add next to current node current_node->next = new_node; } return true; } //Find a node in the list node* findNode(int value) { node *current_node = head; while (current_node != NULL) { if (current_node->value == value) { // If this node contain value is the same. Just return it return current_node; } // Go the next node for next check current_node = current_node->next; } // Go to end of node. And we can not found anything. Just return null. return NULL; } //Delete a node in the list bool deleteNode(node *del_node) { if (head == NULL) { // Current list is empty. We can not delete any more return false; } else if (head->value == del_node->value) { // If this is delete the head node. node *tmp = head->next; free(head); head = tmp; return true; } else { // If this is delete the middle node node *current_node = head; node *prev_node = NULL; while (current_node != NULL) { if (current_node->value == del_node->value) { // Find the node to be delete. prev_node->next = current_node->next; free(current_node); return true; } // If this is not a node delete. Just move to next node for checking. prev_node = current_node; current_node = current_node->next; } } // Can not found any node in list for remove. return false; } //Print the values in the list void printList(void) { node *current_node = head; while (current_node) { printf("%d ", current_node->value); current_node = current_node->next; } printf("\n"); } void deleteLargest(void) { // First step is find the largest node int largest_value = head->value; node *current_node = head->next; while (current_node) { if (current_node->value > largest_value) { // If found new node largest. Just keep track it. largest_value = current_node->value; } // Move to next node for check current_node = current_node->next; } // Now try to delete all node largest node. node *del_node = malloc(sizeof(node)); del_node->value = largest_value; del_node->next = NULL; // Loop until no more largest value in node. while (findNode(largest_value) != NULL) { deleteNode(del_node); } free(del_node); } int count(void) { int cnt = 0; node* current_node = head; while(current_node) { cnt++; current_node = current_node->next; } return cnt; } void sort(void) { if(head == NULL) { // Don't need to sort the empty list return; } else { node* current_node = head; node* compare_node = NULL; while(current_node) { compare_node = current_node->next; while(compare_node) { if(compare_node->value < current_node->value) { // We need to swap 2 node int tmp_value = current_node->value; current_node->value = compare_node->value; compare_node->value = tmp_value; } compare_node = compare_node->next; } current_node = current_node->next; } } } ```

Node:

``` #include < stdio.h> #include < stdlib.h> #include "node.h" //Create a new node with a given value node* createNode(int value) { // Allocate a new node node *new_node = (node*) malloc(sizeof(node)); if (new_node) { // Check the allocated is successfull new_node->value = value; new_node->next = NULL; } return new_node; } ```

Main:

``` #include < stdio.h> #include < stdlib.h> #include "node.h" #include "list.h" int main(int argc, char** argv) { // PS3.1 - Add a set of nodes. // Create a signly linked list from this array. [89, 39, 18, 96, 71, 25, 2, 55, 60, -8, 9, 42, 69, 96, 24] int array = {89, 39, 18, 96, 71, 25, 2, 55, 60, -8, 9, 42, 69, 96, 24}; for(int i = 0; i < 15; i++) { node* new_node = createNode(array[i]); addNode(new_node); } // Print list printf("PS3.1 - List after add: "); printList(); printf("===========================================\n"); // PS3.2 Delete the largest nodes printf("PS3.2 - Try to delete the largest node.\n"); deleteLargest(); printf("List after delete: "); printList(); printf("===========================================\n"); // PS3.3 - Count the nodes in the list printf("PS3.3 - Count the nodes in the list\n"); int list_size = count(); printf("Count nodes in list: %d\n", list_size); printf("===========================================\n"); // PS3.4 - Sort the list printf("PS3.4 - List after sort: "); sort(); printList(); // j o h n n y t u o t - g m a i l - c o m return 0; } ```