Week 9 Code Examples

#include <stdio.h>
#include <stdlib.h> // this is where malloc lives!
#include "ll.h"


/*// What does a single node of a linked list have in it?
struct node {
    int data;
    struct node *next;
};*/

// To create a new node, we really need to do three things
// 1. Malloc some memory for the node! 
// 2. Initialise the node with some data
// 3. Initialise the node with our next pointer... 
// INPUT: data, pointer next, 
// OUTPUT: pointer to this node that you have just created 
struct node *create_node(int data, struct node *next) {
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = next;
    
    return new_node;
}


// Function to print out the list 
// Input: head of the list (pointer to the first node)
// Output: nothing ebcuase I am printing the function
void print_list(struct node *head) {
    // CURRENT Variable that stores the address of a sturct node, 
    // but it is not a node itself 
    struct node *current = head;
    // current != NULL is the traversal that moves you through
    // the whole list! 
    while (current != NULL) {
        printf("%d\n", current->data); // (*current).data
        current = current->next; 
    }
}

// Function to insert at the end of a list
// Input: head of the list that I am inserting into, 
// value that I want inserted) 
// Output: head 
// To insert at the end of the list: 
// 1. Create the node that I want to insert!
// 2. Traverse to the end of the list 
// 3. Insert node at the end... 
// For example, append_node(6, head)
struct node *append_node(int data, struct node *head) {
    //1. Create the node
    struct node *new_node = create_node(data, NULL);

    // CHECK IF THE LINKED LIST IS EMPTY! 
    if (head == NULL) {
        return new_node;
    } else {
        struct node *current = head;
        // current->next != NULL - this stops at the last node, but 
        // doesn't go past it 
        while(current->next != NULL) {

            current = current->next;
        }
    current->next = new_node;
    }

    return head;

}

struct node *insert_at(int data, int position, struct node *head) {

    struct node *new_node = create_node(data, NULL);
    // When I insert a node into a linked list: 
    // 1. Insert at the head of the list (the head will change!)
    // 2. Insert into an empty list! (head will change)
    // Position is out of bounds? For the time being
    // let's assume this is always valid
    if (head == NULL || position == 0) {
        new_node->next = head;
        head = new_node;
    } else {
        int counter = 0;
        struct node *current = head;

        while (current->next != NULL && counter != position) {
            counter++;
            current = current->next;
        }    
        // Exit out of while loop, I am standing at the very last node (maybe)!
        new_node->next = current->next;
        current->next = new_node;
    }

    return head;
}

struct node *delete_value(int value, struct node *head) {
    struct node *current = head;
    struct node *previous = NULL;

    // Loop until I find the value that I want to delete
    // And in the loop, I am going to update both my 
    // current and my previous nodes! 
    // Need to also check that you are not going past the end
    // of hte list current != NULL
    while (current != NULL && current->data != value) {
        previous = current;
        current = current->next; 
    }
    // Exit of the loop 
    // Either 
    // 1. You have gone through the whole list (you are now at NULL)
    // 2. current->data is what you want deleted!
    if (current != NULL) {
        if (previous == NULL) {
            head = head->next;
        } else {
            previous->next = current->next;    
        }
        free(current);
    }

    return head;

}

struct node *delete_first_value(struct node *head) {

    // Check if the list is empty 
    // If it is empty, return NULL back 
    if (head == NULL) {
        return NULL;
    }

    struct node *current = head;
    head = head->next;
    free(current);

    return head;

}

void delete_all(struct node *head) {
    struct node *current = head;

    while (current != NULL) {
        head = head->next;
        free(current);
        current = head;
    }
}

struct node *delete_largest(struct node *head) {
    // Check if the list is empty
    if (head == NULL) {
        return NULL;
    }

    struct node *current = head;
    int largest = current->data;
    // Traverse the list and find the largest value
    while (current != NULL) {
        if (current->data > largest) {
            largest = current->data;
        }
        current = current->next;
    }
// Exit out of the while loop I know what the largest 
// value is! 
    head = delete_value(largest, head);
    return head;

}

struct node *insert_42_after_odd(struct node *head){
    struct node *current = head;
    
    if (current == NULL) {
        struct node *new_node = malloc(sizeof(struct node));
        new_node->data = 42;
        new_node->next = NULL;
        return new_node;
    }
    
    
    while (current != NULL) {
        if (current->data % 2 != 0) {
            struct node *new_node = malloc(sizeof(struct node));
            new_node->data = 42;
            new_node->next = current->next;
            current->next = new_node;
        }
            current = current->next;
    }
    return head;

}

struct node *move_head_to_tail(struct node *head){

    //Empty list
    
    //List with one item

    struct node *old_head = head;
    head = head->next; 

    struct node *current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = old_head->next;
    old_head->next = NULL;
    

    return head;

}