Week 8 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;

}