Thread: have i finally understood this or is it another fluke

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    662

    have i finally understood this or is it another fluke

    i have this code
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node
    {
        int age;
        struct Node *next;
    }Node;
    
    typedef struct LinkedList
    {
        struct Node *head;
        struct Node *tail;
    }LinkedList;
    
    enum Flag {FALSE = 0, TRUE = 1};
    
    void initalize_list(LinkedList *list);
    struct Node *create_head(void);
    struct Node *get_memory(void);
    int get_age(void);
    void print_list(const LinkedList list);
    void delete_list(LinkedList *list);
    void append_to_list(LinkedList *list);
    void prepend_to_list(LinkedList *list);
    void delete_node(LinkedList *list);
    int find_node(int age, Node *current, Node *previous);
    
    int main()
    {
        //declare my list
        LinkedList list;
    
        //list.head = create_head();
        initalize_list(&list);
        append_to_list(&list);
        append_to_list(&list);
        prepend_to_list(&list);
        prepend_to_list(&list);
        print_list(list);
        delete_node(&list);
        print_list(list);
        delete_list(&list);
    
        return 0;
    }
    
    void initalize_list(LinkedList *list)
    {
        list->head = NULL;
        list->tail = NULL;
    
        list->head = create_head();
        list->head->next = NULL;
        list->tail = list->head;
    
        list->head->age = get_age();
    }
    
    struct Node *create_head(void)
    {
        Node *head_tmp;
    
        head_tmp = get_memory();
        if (!head_tmp)
        {
            fprintf(stderr, "error allocating memory\n");
            exit(EXIT_FAILURE);// if it cant allocate memory for the head node at startup somthing really wrong so bug out
        }
    
        return head_tmp;
    }
    
    struct Node *get_memory(void)
    {
        return malloc(sizeof(Node));
    }
    
    int get_age(void)
    {
        int age;
    
        printf("PLease enter an age: ");
        scanf(" %d", &age);
    
        return age;
    }
    
    void print_list(const LinkedList list)
    {
        int count = 1;
        Node *tmp = list.head;
    
        while (tmp)
        {
            printf("person%d's age is %d\n", count, tmp->age);
            count++;
            tmp = tmp->next;
        }
    }
    
    void delete_list(LinkedList *list)
    {
        int count = 1;
        Node *tmp;
    
        printf("freeing memory.....\n");
        while (list->head)
        {
            tmp = list->head->next;
            printf("freeing element %d\n", count);
            free(list->head);
            list->head = tmp;
            count++;
        }
        printf("memory freed\n");
    }
    
    void append_to_list(LinkedList *list)
    {
        Node *tmp_node = NULL;
    
        tmp_node = get_memory();
    
        if(!tmp_node)
        {
            fprintf(stderr, "Unable to get memory for node to append\n");
            return;
        }
    
        tmp_node->age = get_age();
        list->tail->next = tmp_node; //set the tail's next pointer to point at the new node
        list->tail = tmp_node; //set tail to the new node;
    
        // if its the second node in the list list->head->next will be NULL so set the next pointer to point at tmp_node as well
        if (!list->head->next)
        {
            list->head->next = tmp_node;
        }
    }
    
    void prepend_to_list(LinkedList *list)
    {
        Node *tmp_node = NULL;
    
        tmp_node = get_memory();
    
        if(!tmp_node)
        {
            fprintf(stderr, "Unable to get memory for node to prepend\n");
            return;
        }
    
        tmp_node->age = get_age();
        tmp_node->next = list->head; //set tmp_node's next pointer to point at the current head pointer
        list->head = tmp_node; //set head to point to the new head/node
    }
    
    void delete_node(LinkedList *list)
    {
        int age;
        Node *current = list->head, *previous = NULL;
    
        printf("Please enter the age you wish to delete: ");
        scanf(" %d", &age);
    
        if (find_node(age, current, previous))
        {
            if (!previous) // current is pointing at the head
            {
                list->head = current->next;
                printf("freeing head node...\n");
                free(current);
                printf("head node freed\n");
            }
            else if(!current->next) // current is pointing at the tail (the last node)
            {
                list->tail = previous;
                previous->next = NULL;
                printf("freeing tail node...\n");
                free(current);
                printf("tail node freed\n");
            }
            else //its somewhere in the middle of the list
            {
                previous->next = current->next;
                printf("freeing a node in the middle...\n");
                free(current);
                printf("middle node freed\n");
            }
        }
        else
        {
            printf("Invalid age as no node found!\n");
        }
    }
    
    int find_node(int age, Node *current, Node *previous)
    {
        while (current)
        {
            if (current->age == age)
            {
                return TRUE;
            }
            previous = current;
            current = current->next;
        }
        return FALSE;
    }
    find node doesn't update the current and previous pointers in delete_node.
    It dawned on me that again i was passing a pointer to something that was expecting an address not a pointer therefore i realised that i needed a double pointer (a pointer to a pointer) I made the followng changes
    Code:
    void delete_node(LinkedList *list)
    {
        int age;
        Node *current = list->head, *previous = NULL;
    
        printf("Please enter the age you wish to delete: ");
        scanf(" %d", &age);
    
        if (find_node(age, &current, &previous))
        {
            if (!previous) // current is pointing at the head
            {
                list->head = current->next;
                printf("freeing head node...\n");
                free(current);
                printf("head node freed\n");
            }
            else if(!current->next) // current is pointing at the tail (the last node)
            {
                list->tail = previous;
                list->tail->next = NULL;
                printf("freeing tail node...\n");
                free(current);
                printf("tail node freed\n");
            }
            else //its somewhere in the middle of the list
            {
                previous->next = current->next;
                printf("freeing a node in the middle...\n");
                free(current);
                printf("middle node freed\n");
            }
        }
        else
        {
            printf("Invalid age as no node found!\n");
        }
    }
    
    int find_node(int age, Node **current, Node **previous)
    {
        while (*current)
        {
            if ((*current)->age == age)
            {
                return TRUE;
            }
            *previous = *current;
            *current = (*current)->next;
        }
        return FALSE;
    }
    and hey presto it works!!(as far as i can test it)
    coop
    Last edited by cooper1200; 05-26-2019 at 07:46 AM.

  2. #2
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ok there appears to be an issue with my if else if else statement. if i have the following in main
    Code:
    int main()
    {
        //declare my list
        LinkedList list;
    
        //list.head = create_head();
        initalize_list(&list);
        append_to_list(&list);
        append_to_list(&list);
        //prepend_to_list(&list);
        //prepend_to_list(&list);
        print_list(list);
        delete_node(&list);
        print_list(list);
        append_to_list(&list);
        //prepend_to_list(&list);
        print_list(list);
        delete_list(&list);
    
        return 0;
    }
    if i delete a middle node or the head node i get an infinite loop when i print the list again however i don't if i delete the tail node.

    however if i run this version of main (append commented out and prepend uncommented)
    Code:
    int main()
    {
        //declare my list
        LinkedList list;
    
        //list.head = create_head();
        initalize_list(&list);
        append_to_list(&list);
        append_to_list(&list);
        //prepend_to_list(&list);
        //prepend_to_list(&list);
        print_list(list);
        delete_node(&list);
        print_list(list);
        //append_to_list(&list);
        prepend_to_list(&list);
        print_list(list);
        delete_list(&list);
    
        return 0;
    }
    everything works fine. also if i remove the delete node call everything works fine with both prepend and append after the print list call .
    Last edited by cooper1200; 05-26-2019 at 07:44 AM.

  3. #3
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ok i have fixed the issue here is the working function
    Code:
    void delete_node(LinkedList *list)
    {
        int age;
        Node *current = list->head, *previous = NULL;
    
        printf("Please enter the age you wish to delete: ");
        scanf(" %d", &age);
    
        if (find_node(age, &current, &previous))
        {
            if (!previous) // current is pointing at the head
            {
                list->head = current->next;
                current->next = NULL;
                printf("freeing head node...\n");
                free(current);
                printf("head node freed\n");
            }
            else if(!current->next) // current is pointing at the tail (the last node)
            {
                list->tail = previous;
                list->tail->next = NULL;
                printf("freeing tail node...\n");
                free(current);
                printf("tail node freed\n");
            }
            else //its somewhere in the middle of the list
            {
                previous->next = current->next;
                current->next = NULL;
                printf("freeing a node in the middle...\n");
                free(current);
                printf("middle node freed\n");
            }
        }
        else
        {
            printf("Invalid age as no node found!\n");
        }
    }
    however im a little confused as to why
    taking the case of deleting the head node as an example
    line 174 i have list->head = current->next; ie i am saying the head pointer should point at the node current->next is pointing at. so head is now pointing at the new head node therefore the list is complete it has a new head node and the tail node and intermediate nodes are untouched. so why do i need line 175????? and why does not having line 175 only affect appending to the list especially when we haven't touched that end of the list

    coop

  4. #4
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    You need to remember where the list starts.

    list->head is the start of the list. Whenever we look at the list we start here.

    Deleting the list->head element is very similar to a line of people buying tickets and having the person at the front of the line saying, "Actually, I need to visit my Mum that day" and leaving the line. The second person in the line becomes the new start.

    i.e. - In the event that you wish to delete "list->head"
    1st => "list->head" or "current" (from the top of the function)
    2nd => "current->next"

    You then make "list->head" = "current->next"
    So...
    1st => "current"
    2nd => "current->next" or "list->head"

    "current" is deleted, so you now have...
    1st => "current->next" or "list->head"

    And then the function exits...
    Fact - Beethoven wrote his first symphony in C

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. I thought I understood this.
    By somekid413 in forum C Programming
    Replies: 2
    Last Post: 01-11-2010, 08:32 PM
  2. Have I understood the atoi funtion right?
    By austra in forum C Programming
    Replies: 5
    Last Post: 11-13-2009, 09:15 AM
  3. Functions are Still Not Understood.
    By errigour in forum C Programming
    Replies: 6
    Last Post: 04-09-2009, 02:54 PM
  4. did i understood right this explantion of realloc..
    By transgalactic2 in forum C Programming
    Replies: 3
    Last Post: 10-24-2008, 07:26 AM
  5. HELP... LabVIEW Fluke 45 Serial Comms VI
    By studentsaj in forum Windows Programming
    Replies: 0
    Last Post: 03-08-2002, 11:17 AM

Tags for this Thread