Week 8 Code Examples

linked_lists/linked_list_deletion.c

// Week 8 Tuesday Lecture
// Delete the first node in the linked list
// Delete all nodes in a linked list
// Search and delete in a linked list

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

struct node *create_node(int data, struct node *next);
void print_list(struct node *head);
struct node *insert_at_tail(struct node *head, int data);  

//Deletion related functions
struct node *delete_first(struct node *head); 
void delete_all(struct node *head);
struct node *search_and_delete(struct node *head, int value);
struct node *search_and_delete_all(struct node *head, int value);


int main(void) {
    //create a node with data value i using function
    //add node to tail/end of list  
    struct node *head = NULL;
    print_list(head);

    printf("Search and delete from empty list\n");
    head = search_and_delete(head, 99);
    print_list(head);

    for (int i = 0; i < 10; i++) {
        head = insert_at_tail(head, i);
    }
    
    print_list(head); 

    // Between nodes
    printf("Search and delete 4\n");
    head = search_and_delete(head, 4);
    print_list(head);

    //Not in list
    printf("Search and delete 99\n");
    head = search_and_delete(head,99);
    print_list(head);

    //Last element in the list
    printf("Search and delete 9\n");
    head = search_and_delete(head,9);
    print_list(head);

    //First element in list
    printf("Search and delete 0\n");
    head = search_and_delete(head, 0);
    print_list(head);



    // printf("Delete first element\n");
    // for(int i = 0; i <= 10; i++) {
    //     head = delete_first(head);
    //     print_list(head);
    // }
    delete_all(head);
    // check for memory leaks
    return 0;
}

struct node *create_node(int data, struct node *next) {
    struct node *new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
        return NULL;
    }
    new_node->data = data;
    new_node->next = next;
    return new_node;
}

void print_list(struct node *head) {
    printf("list:\n");
    struct node *curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

struct node *insert_at_tail(struct node *head, int data) {
    struct node *new_node = create_node(data, NULL);
    struct node *current = head;

    // Case for when the list is empty
    if (head == NULL) {
        head = new_node;
    } else {
        // Find the last node in the list
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_node;
    }
    return head;
}

// Deletes and frees the memory of the first node in the list
// returns the head of the list
struct node *delete_first(struct node *head) {
    if (head != NULL) {
        struct node *tmp = head;
        head = head->next;
        free(tmp);
    }
    return head;
}

// frees memory of all nodes in the given list
void delete_all(struct node *head) {
     struct node *current = head;
     while (current != NULL) {
        head = head->next;
        free(current);
        current = head;
     }
}

// searches for a value in the list, deletes it and frees
// the memory.
// returns the head of the list
// Only deletes the first occurrence of a value in the list
struct node *search_and_delete(struct node *head, int value) {
    struct node *prev = NULL;
    struct node *curr = head;

    // Find node to delete
    while (curr != NULL && curr->data != value) {
        prev = curr;
        curr = curr->next;
    }

    // Make sure curr is not NULL (ie make sure we found a node to delete)
    if (curr != NULL) {
        if (prev == NULL) {
            head = head->next;
        } else {
            prev->next = curr->next;
        }
        free(curr);
    }

    return head;
}

linked_lists/linked_list_insertion.c

// Week 8 Monday Lecture
// Create a list with nodes by adding nodes with data 0..9 to the 
// tail of an empty list
// Use a loop to insert nodes at the tail of a new list
// We will leave the function to free nodes until later
// For now we will have a memory leak in this program



#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

struct node *create_node(int data, struct node *next);
void print_list(struct node *head);
struct node *insert_at_tail(struct node *head, int data);  
int list_length(struct node *head);

struct node *insert_at_middle(struct node *head, int data);  

int main(void) {
    // A temporary variable we will use
    // when creating new nodes
    struct node *new_node = NULL;

    // Declare and initialise our list
    // Right now this is an empty list but we will add nodes to it
    printf("List 1: 0..9 inserted at start:\n");
    struct node *head = NULL;  
    print_list(head);
    for (int i = 0; i < 10; i++) {
        new_node = create_node(i, head);
        head = new_node;
        print_list(head);
    }

    
    //create a node with data value i using function
    //add node to tail/end of list
    printf("\nList 2: 0..9 inserted at end:\n");
    struct node *head2 = NULL;
    printf("Len %d\n", list_length(head2));
    print_list(head2);
    for (int i = 0; i < 10; i++) {
        head2 = insert_at_tail(head2, i);
        printf("Len %d\n", list_length(head2));
        print_list(head2); 

    }

    head2 = insert_at_middle(head2, 99);
    printf("Len %d\n", list_length(head2));
    print_list(head2); 

    struct node *head3 = NULL;
    head3 = insert_at_middle(head3, 42);
    printf("Len %d\n", list_length(head3));
    print_list(head3); 

    return 0;
}

struct node *create_node(int data, struct node *next) {
    struct node *new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
        printf("Out of memory...\n");
        exit(1);
    }
    new_node->data = data;
    new_node->next = next;
    return new_node;
}

void print_list(struct node *head) {
    struct node *curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

struct node *insert_at_tail(struct node *head, int data) {
    struct node *current = head;
    struct node *new_node = create_node(data, NULL);
    if (current == NULL) {
        head = new_node;
    } else {
        // Finding the last node
        while (current->next != NULL) {
            current = current->next;
        }
        
        current->next = new_node;
    }
    return head;
}

int list_length(struct node *head) {
    int counter = 0;
    struct node *current = head;
    while (current != NULL) {
        counter++;
        current = current->next;
    }   
    return counter;
}

struct node *insert_at_middle(struct node *head, int data) {
    struct node *current = head;
    struct node *new_node = create_node(data, NULL);
    
    if (head == NULL) {
        head = new_node;
    } else {
        int counter = 0;
        int size = list_length(head);
        // Finding the one before the middle
        while (counter < size/2 - 1) {
            counter++;
            current = current->next;
        }
        
        new_node->next = current->next;
        current->next = new_node;
    }
    return head;
}

linked_lists/linked_list_insertion_at_pos.c

// Week 8 Tuesday Lecture
// Insert nodes at specified positions in the list
// We will leave the function to free nodes until later
// For now we will have a memory leak in this program



#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

struct node *create_node(int data, struct node *next);
void print_list(struct node *head);
struct node *insert_at_tail(struct node *head, int data);  
struct node *insert_at_position(struct node *head, int data, int pos);


int main(void) {
    // A temporary variable we will use
    // when creating new nodes
    struct node *head = NULL;
    print_list(head);

    // Test inserting into empty list
    printf("Inserting into empty list 9 at pos 0\n");
    head = insert_at_position(head, 9, 0);
    print_list(head);

    //Inserting at pos 0 (at the beginning)  
    printf("Inserting 88 at pos 0 (beginning)\n");
    head = insert_at_position(head, 88, 0);
    print_list(head);

    //Inserting at the end
    printf("Inserting 72 at pos 2 (end)\n");
    head = insert_at_position(head, 72, 2);
    print_list(head);

    //Inserting somewhere in between 2 nodes
    printf("Inserting 3 at pos 2 (between 2 nodes)\n");
    head = insert_at_position(head, 3, 2);
    print_list(head);

    //invalid position too small
    printf("Inserting 10 at pos -3 invalid position\n");
    head = insert_at_position(head, 10, -3);
    print_list(head);

    //invalid position too big
    printf("Inserting 5 at pos 200 invalid position\n");
    head = insert_at_position(head, 5, 200);
    print_list(head);
    

    return 0;
}

struct node *create_node(int data, struct node *next) {
    struct node *new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
        printf("Out of memory...\n");
        exit(1);
    }
    new_node->data = data;
    new_node->next = next;
    return new_node;
}

void print_list(struct node *head) {
    struct node *curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}
  

//TODO
struct node *insert_at_position(struct node *head, int data, int pos) { 
    struct node *current = head;
    struct node *new_node = create_node(data, NULL);
    
    if (head == NULL || pos <= 0) {
        new_node->next = head;
        head = new_node;
    } else {
        int counter = 0;
        // Finding the one before the pos
        while (current->next != NULL && counter < pos - 1) {
            counter++;
            current = current->next;
        }
        
        new_node->next = current->next;
        current->next = new_node;
    }
    return head;
}

linked_lists/linked_list_search.c

// Week 8 Tuesday Lecture
// Create a list with nodes by adding nodes with data 0..9 to the 
// tail of an empty list
// Search for values in the list
// We will leave the function to free nodes until later
// For now we will have a memory leak in this program

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

struct node *create_node(int data, struct node *next);
void print_list(struct node *head);
struct node * insert_at_tail(struct node *head, int data);  
int list_search(struct node *head, int value);

int main(void) {
    printf("List to search:\n");
    struct node *head = NULL;
    print_list(head);

    // Testing empty list
    if (list_search(head, 99) == 1) {
        printf("I found 99\n");
    } else {
        printf("I did not find 99\n");
    }

    // Add 1 node
    head = insert_at_tail(head, 13);
    print_list(head);

    // Testing empty list
    if (list_search(head, 99) == 1) {
        printf("I found 99\n");
    } else {
        printf("I did not find 99\n");
    }

    if (list_search(head, 13) == 1) {
        printf("I found 13\n");
    } else {
        printf("I did not find 13\n");
    }
    
    //Add some nodes to the list
    head = insert_at_tail(head, 17);
    head = insert_at_tail(head, 42);
    head = insert_at_tail(head, -7);
    head = insert_at_tail(head, 5);
    print_list(head);

     if (list_search(head, 99) == 1) {
        printf("I found 99\n");
    } else {
        printf("I did not find 99\n");
    }

    if (list_search(head, 5) == 1) {
        printf("I found 5\n");
    } else {
        printf("I did not find 5\n");
    }

    if (list_search(head, -7) == 1) {
        printf("I found -7\n");
    } else {
        printf("I did not find -7\n");
    }
     

   return 0;
}
    
struct node *create_node(int data, struct node *next) {
    struct node *new_node = malloc(sizeof(struct node));
    if (new_node == NULL) {
        return NULL;
    }
    new_node->data = data;
    new_node->next = next;
    return new_node;
}

void print_list(struct node *head) {
    printf("List: ");
    struct node *curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

//                
struct node *insert_at_tail(struct node *head, int data) {
    struct node *new_node = create_node(data, NULL);
    
    // The list is empty
    if (head == NULL) {
        head = new_node;
    } else {
        struct node *current = head; //NULL
        
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_node;
    }
    return head;
}

// return 1 if the value is found in the given list
// return 0 otherwise
int list_search(struct node *head, int value) {
    struct node *current = head;
    int found = 0;
    while (current != NULL && found == 0) {
        if (current->data == value) {
            found = 1;
        }
        current = current->next;
        
    }
    return found;
}