Re-post: Finding a node in a linked list...

[ronkane]

Hello,

Here is a re-post of my previous message with the "code" tags. Sorry. 8) I'm attempting to use a FindNode function for both a Retrieve and Delete. Here are the function codes:

bool SortedType::RetrieveItem(student& item) 
{ 
if (FindNode (item)) // if item has been found (true) 
{ 
item = current->info; 
return true; 
} 

return false; 
}

bool SortedType::FindNode(student item) 
{ 
current = head; // start both pointers at front of list 
new_pointer = head; 
if (head->info.Key > item.Key) // not in list 
return false; 
if (head->info.Key == item.Key) // found and first in list 
return true; 

while ((current->next != NULL) && 
(current->next->info.Key <= item.Key)) 
current = current->next; // set current to point at next item 

new_pointer = current->next; // point new_pointer to next item 

if ((current == NULL) || (current->next->info.Key != item.Key)) 
return false; 

return true; 
}

bool SortedType:eleteItem(student& item) 
{ 
if (FindNode (item)); // if item has been found (true) 
{ 
if (new_pointer == head) // if item at front of list 
head = current->next; // point head where link points to 
else // else not first item in list 
current->next = new_pointer->next; 

delete new_pointer; // release this space 

if (new_pointer == tail) // if deleting last node 
tail = current; // set tail to previous node 

return true; // item is deleted from the list 
} 

return false; // item is not in the list 
}

Basically what I'm noticing is when I attempt to do a delete it will only allow me to delete the first record and no others. Plus I notice that it "appears" to delete records that aren't there. When I start the program and immediately choose delete, it says,
"record 1000 has been deleted" when I never entered any records yet.

My Retrieve function appears to work in that it will not pull up any records as long as my list is empty but it too will not work with more than one record. I can easily retrieve the first record but any record afterwards it say "record 1000 could not be retrieved".

Somewhere my true/false values must somehow be screwing up. Can someone help me with my logic?

Thanks!

Ron

[Natase]

Node *prev;
// if (FindNode (item)); 
while (current != NULL) {
   if ((current->col == col) && (current->row == row)) {
      break;
   }
   prev = current;
   current = current->next;
}
if (current != NULL) {
   if (current == head) {
      head = current->next;
   } else {
      prev->next = current->next;
   }
}

I think you need to keep track of the previous node as you traverse the list so you can ensure the pointer before the one you are deleting points to the one after the one you are deleting.
My code probably isn't quite right, but it's worth a shot.

I don't know how your FindNode() works, but I assume it leaves the function with 'current' pointing at the node you're looking for. Might need to add a variable to keep track of the previous node inside this function if my solution works for you...

[ronkane]

Hello,

In the FindNode function, I attempt to find a record using the ".Key" field the first part:

  current = head;                               // start all 3 pointers at front of list
  previous = current;
  new_pointer = head; 
  if (head->info.Key > item.Key)                // not in list
    return  false;
  if (head->info.Key == item.Key)               // found and first in list
    return  true;

...sets all pointers to the beginning of the list and checks to see if the ".Key" field is not there at all or the first record. This list is an ordered list so if I looked for a ".Key" field valued at 1000 and the first record had a ".Key" field valued at 34193, then 1000 should not be in the list at all and false is returned, otherwise if it's 34193 I'm trying to find then it will find it as the first node and return a true.

I believe this portion is working. I'm not certain about THIS portion:

  while ((current->next != NULL) &&  
    (current->next->info.Key < item.Key))      
      current = current->next;                  // set current to point at next item

My initial guess has been that SOMEHOW it was never going to this loop at all and returning a true because for some reason, I can not delete a record unless I delete the first one. If I had 3 records with ".Key" fields 1000, 2000 and 3000 in them, I can not delete 2000 or 3000, just 1000. Then when I delete 1000, I can only delete 2000, and then when I delete 2000, just 3000. So it APPEARS to delete the first record fine. Just nothing else.

Does that help with the logic? Let me know.

Thanks!

Ron