Deleting node from linked list in C - help!

[SadisticToaster]

Hey : with the help of some online tutorials , have managed to knock together the following code which looks , to me , like it should work - but when I run it , the program goes to a blank screen after less then a second. Any ideas? Been stuck on this one for several days now

void deleteshot(node *&root,int counter)
{
node *current;
node *tempnode = new node;
current=root;
int counter2 = counter;
counter=0;
for (int temp=0;temp<counter2-2;temp++)
{
counter++;
current=current->next;
}
}

if (current->next->next !=NULL)
{
current = current->next;
tempnode = current->next;
free(current);
current=tempnode;
}
}

Many thanks for any help

[dreadster]

At first glance I see three problems.

1) You're new-ing up a node and storing the pointer in tempnode but never deleting the node. That will leak memory on every call.

2) You're allocating with new but deleting with free, which is not guaranteed to work. Also, deleting with free will not call destructors.

3) The check (current->next->next !=NULL) will dereference a null pointer if current->next is null.

[[Feeblez]]

I've known so called game programmers that can't code a linked list, it's a common cause of memory leaks and random crashes, but needn't be.

A good exercise would to be to create a link list template with built in asserts and error checking, and then test it thoroughly. In most cases this is all you will ever need, or use STL.

[Glyndwr]

Isn't there an extra brace in the middle somewhere?

[fred_zen]

I don't get why you do this "copy counter to counter2, then zero out counter, then increment counter in the loop" thing, I think you can just drop that.

Code: Select all

void deleteshot(node *&root,int counter)
{
  node *current;
  node *tempnode = new node;
  current=root;

  for (int temp=0;temp<counter-2;temp++)
    {
      current=current->next;
    }

By the way that's c++, not c.

Also, you don't need to allocate a new node to tempnode, you never actually do anything with that one (you just overwrite the pointer with current->next)

Also, you may have noticed that root is a reference to a node pointer, not just a node pointer. That's a giveaway that you will need to change it in some cases, but you don't for the moment (hint: make current a node*& instead of a node* [edited to add:]oops, that won't work, you can do it with a node** though)

[defsdoor]

Make it a doubly linked list and just join prev and next together and free the one inbetween.

[SadisticToaster]

fred_zen : I can't see what it does either - though I remember putting it in early on when the code was still part of the main program. However , if I delete it , the aliens stop firing any bullets for some reason I can't quite figure out.

It's one I think I'm going to have to take a good look at.

Thanks to all for your suggestions : have rebuilt the function and now works fine . . . mostly.

'free(tempnode);' - or 'delete tempnode;' , which I saw on a few sites and though was worth a try - still causes the screen to go black , and the program to die. ( Spookly enough , the line causing all the problems is line number 666 )


dreadster : if deleting with free does not call destructors , what does?

[fred_zen]

dreadster : if deleting with free does not call destructors , what does?

delete. The pairs are malloc-free and new-delete.

How about this?

Code: Select all

void deleteshot(node *&root, int pos) {
    node **current = &root;
    while(*current && pos-->0)
      current=&((*current)->next);
    if (*current) {
      node *tempnode = *current;
      *current = (*current)->next;
      delete tempnode;
    }
}

[SadisticToaster]

Hmm. Works ish. Deletes target node , but also deletes other nodes at random. From the position of the shots which are deleted , it looks like it could be the node before / after the target one.

Even if I cut it down slightly : to the following : it still deletes ( well , not deletes exactly , but you know what I mean ) nodes at random.

while(*current && counter-->1) // ( slightly different to yours : 0 would make it the one before the targeted one )
current=&((*current)->next);
if (*current)
{

*current = (*current)->next;

}

However , if I alter it to :

while(*current && counter-->1) // ( slightly different to yours : 0 would make it the one before the targeted one )
current=&((*current)->next);
if (*current)
{

(*current)->y--;

}

it will only target the correct node ( the bullet appears to stop moving , and 'hang' in the air ). Very odd.


Spent the last week experimenting , but no luck yet. Going to try double-linked lists next : does this have any speed effects on the end program?

[defsdoor]

Doubly linked lists take up more space (an extra pointer), but there are time savings in deletes as you can quickly refer to the previous node -

thisobject->prev->next=thisobject->next;
thisobject->next->prev=thisobject->prev;
free(thisobject);

If you are deleting and adding a lot though instead of freeing, append the object to be freed to a deleted objects list instead - then you can quickly pull it off there and reuse it.

[piku]

Doubly linked lists take up more space (an extra pointer)

The horrors! One extra pointer!

Linked lists are one of those things that after having to rewrite one for every game you make, become second nature. Unfortunately they also become a right pain to have to rewrite for every game.

Which is why I now use C++ and the STL. vector<enemy *> enemyList; is just 100%* easier to do.

The thing with a linked list is to not just blindly copy someone's code and hope it works. You need to understand how it works. I find drawing little boxes on a sheet of paper helps with the understanding.

I tended to store a pointer to the first and last elements in my lists. This made adding new ones a doddle.

Deleting is a bit more involved...

Code: Select all

Input parameter - onetobedeleted;
Output parameter - nothing (or return 1/0 depending on whether it worked)

temp = head;
previous = NULL;

// First deal with removal of the head as it's quite easy
if (onetobedeleted == head)
  // Is there more than one item in the list?
  if (head->next)            // yes
    head = head->next;
    free (temp);
  else                           // no
    free(head);
    head = NULL;

// Find the one to remove, but also store a pointer to the one before it
while (temp != onetobedeleted)
  previous = temp;
  temp = temp->next;

// Now "previous" contains the one before what we want to delete
// and "temp" contains the item to be removed
// temp->next contains either the next item in the list, or NULL if this is the end

// First stitch up the hole
if (temp->next != NULL)
  previous->next = temp->next;
else
  previous->next = NULL;
  tail = previous;

// Now remove the item
free (temp);

(this pseudocode written in a new language called "Cython" that I just invented. All the syntax of C, but the indentation of Python )

Disclaimer: I bet there's a bug somewhere... Like I said, this was the main reason for using C++ and the STL.

* When compared to writing your own.

[KlaxonCow]

Doubly linked lists take up more space (an extra pointer)

The horrors! One extra pointer!

Linked lists are one of those things that after having to rewrite one for every game you make, become second nature. Unfortunately they also become a right pain to have to rewrite for every game.

Which is why I now use C++ and the STL. vector<enemy *> enemyList; is just 100%* easier to do.

How about this "radical" alternative approach?

Write your own and then stuff it into a code library. Thereby simultaneously gaining the advantages of both approaches at the same time.

Create a library - "MyLib" - and then include it into each project. Then "roll your own" routines and anything you write that's got some useful "code reuse" to it that you might need it again, add it to the library.

Next time you need that linked list, just include it from your code library.

As you go from game to game, the library builds up and becomes a comprehensive "game library" of useful routines. Eventualy, even a sort of "game engine".

But it's all your own code and you can make it work in whatever way you want it to work. You can dive in and add more and refine it at any time.

It'll end up just as handy as the STL but a lot more "game specific" - as there's no reason why you can't throw in, say, generic "physics" routine into the code library (well, the laws of physics don't change very often, do they? Certainly "reuse value" there) or a "pixel shatter" routine or "sprite" routines or whatever else you fancy throwing in there - and, also, where the STL might not favour performance too much (they usually aren't written or designed with the high performance requirements of games in mind), your own library can be happily written with a "need for speed" attitude.

I call it "the Tony Crowther approach" (in honour of the fastest programmer in the West, who reportedly managed such uncanny speeds because he just gutted out the innards of his last game and transplanted them into the next all the time).

Conceivably, though this approach is slow starting, once a comprehensive little library is created, you should actually start accelerating up all the time until using the STL seems like the slow, stupid approach.

Another neat idea in the composition of your "game library" is to actually create it in two flavours - "debug" and "release" - where, basically, the only difference is that you wrap debugging code and asserts and what-not in "'#ifdef" constructs, according to some "debug" define. Compile once with and once without to get the two flavours. Develop with the "debug" version and test the code to destruction. If it passes the test then compile it against the "release" instead (which omits all the debugging code and unnecessary "checks" for improved performance. Logically, if your game passes the "debug" test bug-free then it'll run just as bug-free with the "release" but a little faster because it doesn't bother with all the debugging tests and "checks", which the game has already proved it has passed with the "debug" version).

All the advantages and routines of any STL (and, likely, a lot more besides) while all of it is your own code - written how you like it - and perfectly available for adding to, refining and reusing as much as you like.

Basically, every time you invent a wheel, store it away in the library. Then there's no need for you to ever "reinvent the wheel" again. Just go get it from the library.

But every wheel in there you invented, so it's all put together in exactly the way you like it and perfectly open to amend, refinement and anything else you might fancy doing (e.g. need one of your "physics" routines but the gravity code isn't necessary for this game as it's all in space? Fine, grab the routine, strip out the gravity code and then add it back into the library as additional "PhysicsWithoutGravity" functions. Let's see an STL do that kind of thing, eh? ).

All you need do is start your next project with an empty library - "MyLib" - and then keep moving that library from game to game, as you write more games. When you need something you've already done in the previous game, just include it from the library. When you write something new that would be useful in other games, don't pop it into your game code directly but put it into the library and then include it back out of the library (and then it's sitting there in the library to be "reused" the next time around).

It's just a little extra bit of maintenance - but not a big deal, really, in the grand scheme of things - and as you write more games, you'll soon end up with a pretty kick arse library of game routines that should allow you to put together games at an incredible pace (making the use of the STL seem like the bad idea in comparison).

Programmers do tend to often have this thing of reinventing the wheel all the time. But that's why libraries were invented.

All the STL is, after all, is exactly just the same kind of code library but someone else put it together for you (but it's very generic and not at all "game specific").

There's no real reason why you can't just do that yourself.