C - deleting node in doubly linked list

Question

When I try to delete every other element in the list using the deleteinst method the method does nothing to the linked list and there are no errors. I'm really not sure why it's not working I've seen the same deleteinst method used in a different program. Maybe it has something to do with the pointers. If I run deleteInst(track.prev, &head); without the while loop the list still remains unchanged.

Please let me know if you have any idea or need more info. Thank you for your time.

int main()
{
node *head;
node *track;
head = ReadNodeList(stdin);

track = LastNode(head); //goes to last node.

while(track != NULL){ 
    int i=0;
            //delete every other node
    if(i%2 == 1){
        deleteInst(track, &head);
    }
i++;
track = track->prev;
    }
}

void deleteInst(Instruction *victim, Instruction **head){

  if(*head == NULL || victim == NULL)
    return;

  if(*head == victim)
    *head = victim->next;

  if(victim->next != NULL)
    victim->next->prev = victim->prev;

  if(victim->prev != NULL)
    victim->prev->next = victim->next;     

  free(victim);
  return;
}

I don't have time to invest in a full answer, but delete is a keyword (in c++, not c), but still using this as a variable name is a bad idea and misleading and messing up stack overflow syntax highlighting!!! Paxdiablo's point is also valid. — MobA11y
– MobA11y, Commented Mar 10, 2014 at 4:03

paxdiablo · Accepted Answer · 2014-03-10 04:42:35Z

2

One immediately obvious glaring problem: you really don't want to do this:

 deleteInst(track, &head);
 track = track->prev;

The instant you free that node, you lose the right to access its members. Save it first then recover after the delete:

 node *save_prev = track->prev;
 deleteInst(track, &head);
 track = save_prev;

Another thing I'd check is that the list structure is correct, with something like (only during debug):

static void checkList (node *curr) {
    int count = 0;

    // PreCon: head->prev must be null.

    if (curr != NULL) {
        if (curr->prev != NULL) {
            puts ("Linked list structure error A!");
            exit (1);
        }
    }

    // Check all nodes.

    while (curr != NULL) {
        // PreCon: curr->prev->next must be curr.

        if (curr->prev != NULL) {
            if (curr->prev->next != curr) {
                puts ("Linked list structure error B!");
                exit (1);
            }
        }

        // PreCon: curr->next->prev must be curr.

        if (curr->next != NULL) {
            if (curr->next->prev != curr) {
                puts ("Linked list structure error C!");
                exit (1);
            }
        }

        // Move to next and keep count.
        curr = curr->next;
        count++;
    }

    // All okay, output success message with size.

    printf ("Linked list structure okay, size = %d\n", count);
}

Calling that with checkList (head) will validate that your linked list meets all the validity preconditions, on the off-chance that you may have buggy code elsewhere, such as when creating the list in ReadNodeList().

Beyond that, I suggest single stepping the code in your IDE or debugger after ReadNodeList() to see what it's actually doing. And, if you don't have an IDE/debugger, pepper your source code with lots of lines like:

printf ("DEBUG %d: track = %p\n", __LINE__, track);

and then examine the output of the debug statements to analyse the flow through your program.

Now, if you were to actually do that debugging exercise, it may surprise you to find out that deleteInst never appears to be called, because i seems to be always set to 0.

And the fault of that little problem lies here:

while (track != NULL) { 
    int i = 0; // <<<<<<<

    //delete every other node

    if (i%2 == 1) {
        deleteInst (track, &head);
    }
    i++;
    track = track->prev;
}

Yes, that's right, you are setting i to 0 every single time through the loop, hence i % 2 will never be equal to 1. You need to initialise i before the loop (and with the undefined behaviour of accessing freed memory removed as well):

int i = 0;
while (track != NULL) { 
    node *save_prev = track->prev;

    //delete every other node

    if (i%2 == 1)
        deleteInst (track, &head);
    i++;
    track = save_prev;
}

edited Mar 10, 2014 at 4:42

answered Mar 10, 2014 at 3:59

paxdiablo

889k243 gold badges1.6k silver badges2k bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

paxdiablo Over a year ago

@Philip, I've added some other suggestions which will make it much easier for you to debug your code.

Philip Rego Over a year ago

It ran through checkList without error. What might that indicate? thank you @Schigh no nodes are being deleted from the list.

paxdiablo Over a year ago

@Phillip, you should have done the single-step/debug-print, the problem would have been immediately obvious :-) See the update.

Philip Rego Over a year ago

When I try that nothing changes and the printf doesn't print either. I'm going to try putting printfs earlier.

Philip Rego Over a year ago

printf doesn't even work in the first line of main maybe it has to do with that I'm running with a command line. I'm going to try to install a debugger.

user3386109 · Accepted Answer · 2014-03-10 04:58:15Z

Doubly linked lists are a whole lot easier to work with if you put a tail on the list during the list initialization. This eliminates most of the mind-numbing corner cases.

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

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

void ShowList( node *head );
void AppendNodeWithData( node *tail, int data );
void RemoveNode( node *item );

int main( void )
{
    int i;
    node *head, *tail, *item, *temp;

    // allocate and initialize the doubly linked list
    head = malloc( sizeof(node) );
    tail = malloc( sizeof(node) );
    if ( !head || !tail )
        exit( 1 );

    head->next = tail;
    head->prev = NULL;
    tail->next = NULL;
    tail->prev = head;

    // add some items to the list
    for ( i = 0; i < 20; i++ )
        AppendNodeWithData( tail, i );

    ShowList( head );

    // remove every other item
    for ( item = tail->prev; item != NULL && item->prev != NULL; item = temp )
    {
        temp = item->prev->prev;
        RemoveNode( item );
    }

    ShowList( head );
}

void ShowList( node *head )
{
    node *item;

    for ( item = head->next; item->next != NULL; item = item->next )
        printf( "  %d", item->data );
    printf( "\n" );
}

void AppendNodeWithData( node *tail, int data )
{
    node *item;

    if ( (item = malloc( sizeof(node) )) == NULL )
        exit( 1 );

    item->data = data;

    item->prev = tail->prev;
    item->next = tail;

    tail->prev->next = item;
    tail->prev = item;
}

void RemoveNode( node *item )
{
    item->next->prev = item->prev;
    item->prev->next = item->next;
    free( item );
}

Collectives™ on Stack Overflow

C - deleting node in doubly linked list

2 Answers 2

5 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related