Remove entry and Insert Entry in Linked Lists func

Question

Good afternoon. I'm learning the C language from a book called Programming in C Third Edition by Stephen G. Kochan. I wrote some code that is supposed to insert and remove certain entries from a list, which it does, the problem is, it does not remove the right entry, and it does not quite insert the entry in the right spot. The code is below. Any help would be greatly appreciated!

//Insert and Remove entry functions using doubly linked lists
#include <stdio.h>

struct Entry
{
    int Value;
    struct Entry *Previous;
    struct Entry *Next;
};


int main()
{
    void InsertEntry (struct Entry *InsertPosition, struct Entry EntryToInsert);
    void RemoveEntry (struct Entry *EntryToRemove);
    struct Entry N1, N2, N3, N4, N5, Insert, *Start = &N1;

//set initial values
    N1.Value = 10;
    N2.Value = 20;
    N3.Value = 20;
    N4.Value = 30;
    N5.Value = 40;
    Insert.Value = 35;

//link the list

    N1.Next = &N2;
    N2.Next = &N3;
    N3.Next = &N4;
    N4.Next = &N5;
    N5.Next = (struct Entry *) 0;
//Link again

    N1.Previous = &N1;
    N2.Previous = &N1;
    N3.Previous = &N2;
    N4.Previous = &N3;
    N5.Previous = &N4;

    InsertEntry(&N4, Insert);
    RemoveEntry(&N2);

//Display the Lists
    while (Start->Next != (struct Entry *) 0)
    {
        printf("Previous: %i, Current: %i, Next: %i\n",         Start->Previous->Value, Start->Value, Start->Next->Value);
        Start = Start->Next;
    }

    return 0;
}

void InsertEntry (struct Entry *InsertPosition, struct Entry EntryToInsert)
{

    EntryToInsert.Previous = InsertPosition->Previous;
    EntryToInsert.Next = InsertPosition;
    InsertPosition->Previous->Next = &EntryToInsert;

}

void RemoveEntry (struct Entry *EntryToRemove)
{
    EntryToRemove->Previous->Next = EntryToRemove->Next;
}

Answer 1

There are a couple of problems with your InsertEntry function.

First, you need to pass in pointers to both the InsertPosition and the EntryToInsert. The reason for this is because in C, everything is pass by value. That means when you pass a value into a function, that function will see a copy of that value, not the original value. Once that function completes - the copy is gone forever. So if you want to modify something inside a function, and have that modification be visible once the function completes, you have to pass a pointer to that something. A pointer in C points to a location in memory - so even if the function gets a copy of that pointer, the location it points to is the same.

This means that the first step is defining the function as:

void InsertEntry (struct Entry *InsertPosition*, struct Entry *EntryToInsert)

Second, the order in which you insert EntryToInsert is wrong for what you want to accomplish - you want to insert this value after InsertPosition, not before it. Here's the corrected function with comments:

void InsertEntry (struct Entry *InsertPosition, struct Entry *EntryToInsert)
{
    //Goal is to insert EntryToInsert *before* InsertPosition
    //  so that it will look like:
    //  ??? --> EntryToInsert --> InsertPosition
    //Step 1: ??? <-- EntryToInsert
    EntryToInsert->Prev = InsertPosition->Prev;
    //Step 2: EntryToInsert --> InsertPosition
    EntryToInsert->Next = InsertPosition;
    //Step 3: ??? --> EntryToInsert
    EntryToInsert->Prev->Next = EntryToInsert;
    //Step 4: EntryToInsert <-- InsertPosition
    InsertPosition->Prev = EntryToInsert;
}

Finally - the function declarations that you currently have inside of the main function usually go outside (before) the function.

Fixing this should fix any problems you have with your RemoveEntry function - again, I see no problems with that.

Answer 2

There are several problems in the code.

Move the declarations for InsertEntry and RemoveEntry to before the main().

When initializing Previous fields, head of the list needs to have Previous = NULL.

When printing out list, need to avoid printing out Previous->Value and Next->Value for head and tail of list, respectively.

In InsertEntry() function, code is passing EntryToInsert struct by value which inserts a copy into the list. I am guessing you intended to pass by pointer which would insert the original stucture into the list.

In InsertEntry() function, need to also set InsertPosition->Next->Previous.

In InsertEntry() function before setting InsertPosition->Previous->Next and InsertPosition->Next->Previous, need to check that you are not at head and tail of list, respectively.

In RemoveEntry() function, need to also set EntryToRemove->Next->Previous.

In RemoveEntry() function before setting EntryToRemove->Previous->Next and EntryToRemove->Next->Previous, need to check that you are not at head and tail of list, respectively.

In RemoveEntry() function, need to also set EntryToRemove->Previous = NULL and EntryToRemove->Next = NULL.

I would suggest you attempt to fix each of the above mentioned issues on your own. If you run into problems fixing a given issue, I have included the complete code with my suggested fixes for you to look at.

struct Entry
{
    int Value;
    struct Entry *Previous;
    struct Entry *Next;
};

void InsertEntry(struct Entry *InsertPosition, struct Entry *EntryToInsert);
void RemoveEntry(struct Entry *EntryToRemove);

int main()
{
    struct Entry N1, N2, N3, N4, N5, Insert, *Start = &N1;

    //set initial values
    N1.Value = 10;
    N2.Value = 20;
    N3.Value = 20;
    N4.Value = 30;
    N5.Value = 40;
    Insert.Value = 35;

    //link the list

    N1.Next = &N2;
    N2.Next = &N3;
    N3.Next = &N4;
    N4.Next = &N5;
    N5.Next = NULL;
    //Link again

    N1.Previous = NULL;
    N2.Previous = &N1;
    N3.Previous = &N2;
    N4.Previous = &N3;
    N5.Previous = &N4;

    InsertEntry(&N4, &Insert);
    RemoveEntry(&N2);

    //Display the Lists
    while (Start != (struct Entry *) 0)
    {
        printf("Previous: ");
        if (Start->Previous != NULL)
        {
            printf("%i", Start->Previous->Value);
        }
        else
        {
            printf("NULL");
        }
        printf(", Current: %i, Next: ", Start->Value);
        if (Start->Next != NULL)
        {
            printf("%i", Start->Next->Value);
        }
        else
        {
            printf("NULL");
        }
        printf("\n");
        Start = Start->Next;
    }

    return 0;
}

void InsertEntry(struct Entry *InsertPosition, struct Entry *EntryToInsert)
{
    EntryToInsert->Previous = InsertPosition->Previous;
    EntryToInsert->Next = InsertPosition;
    if (InsertPosition->Previous != NULL)
    {
        InsertPosition->Previous->Next = EntryToInsert;
    }
    InsertPosition->Previous = EntryToInsert;

}

void RemoveEntry(struct Entry *EntryToRemove)
{
    if (EntryToRemove->Previous != NULL)
    {
        EntryToRemove->Previous->Next = EntryToRemove->Next;
    }
    if (EntryToRemove->Next != NULL)
    {
        EntryToRemove->Next->Previous = EntryToRemove->Previous;
    }
    EntryToRemove->Previous = NULL;
    EntryToRemove->Next = NULL;
}