Thread: 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

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 .

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...