Linked lists

[coolio2006]

Hi - i just needed some help. I'm constructing a circular linked list which means 1st node points to 2nd, and so on. The task i need to accomplish is that i need to remove one node (any node in the linked list). So lets say i have 8 nodes in my circular linked list and i want to remove the 4th node. We know that the 4th node points to the 5th node. Anyway, my current function has no problem with deleting any node except for the 2nd no. No matter what I try to do, I cannot delete the 2nd node. Here is my function: Im sorry if there isn't enough info here, but you can ask and i'll be happy to reply back. Thanks.

node* prev = current; // current is the head of the linked list – im making a pointer prev to 			//also point to head
node* cur; // just another pointer




 cur = prev;  // let cur also point to the head of the linked list

 for (int i=1; i <= size(); i++) // size is the size of the linked list

 {
 if (prev -> num == x ) // x is the node I want to delete – so if the first node contains the                  //data (num is the data field of the node) – then do the following
  {

  cur -> shortlink = prev -> shortlink ;
  delete cur;
  length--;
  }
  cur = prev;
  prev = prev -> shortlink;
  

 }

[michaels-r]

Just to be clear, when you say circular, do you mean that the last node points to the first?
I am not quite clear what you are trying to do with your code... do you manage the garbage collection yourself? i.e. if there is clear space in the list do you release it for reuse?

The obvious approach for deletion is to move to the element you want to delete. Make the next pointer of the previous element equal the next pointer of the element to be deleted and then make the previous pointer of the next element equal the previous pointer of the element to be deleted. Finally you need to clear up the element you are deleting (delete it or flag the memory as being available - we are back to garbage collection here).

Why not create a class that cleans itself up? Or, if this is for a real-world situation, rather than some kind of assignment, save youself a lot of trouble and use the STL and maybe avoid linking the list altogether? What are your aims?

[Cat]

1. A circular linked list has no head.
2. What happens in your code if the node pointed at by current is deleted? current then points to a node that is no longer within the linked list.
3. Why do you need to make your own linked list? C++ has a built in linked list type you can use, std::list.

[Ideswa]

3. Why do you need to make your own linked list? C++ has a built in linked list type you can use, std::list.

That's called: practice

Edit: or homework assignment

[iMalc]

Whilst it is true that the C++ std library does not provide a ring-list (one where you can never step off the end because you land back on the start), you can implement one using a std::list by overloading the ++ and -- operators to wrap back to begin or rbegin when you reach the end. You would also need to override begin and rbegin which would use a new member variable to remember where to start.
Granted, it wont quite be as efficient... but it'll be more useful and less buggy.

You'd certainly want to avoid passing it to function like for_each though, for example!