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

This is a discussion on Re-post: Finding a node in a linked list... within the C++ Programming forums, part of the General Programming Boards category; Hello, Here is a re-post of my previous message with the "code" tags. Sorry. 8) I'm attempting to use a ...

  1. #1
    Registered User
    Join Date
    Jan 2002
    Posts
    14

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

    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:

    Code:
    bool SortedType::RetrieveItem(student& item) 
    { 
    if (FindNode (item)) // if item has been found (true) 
    { 
    item = current->info; 
    return true; 
    } 
    
    return false; 
    }
    Code:
    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; 
    }
    Code:
    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

  2. #2
    Registered User Natase's Avatar
    Join Date
    Aug 2001
    Posts
    123
    Code:
    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...

  3. #3
    Registered User
    Join Date
    Jan 2002
    Posts
    14

    Talking Thanks...

    Hello,

    In the FindNode function, I attempt to find a record using the ".Key" field the first part:
    Code:
      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:
    Code:
      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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 04:05 PM
  2. Memory Leak
    By jtullo in forum C Programming
    Replies: 7
    Last Post: 12-11-2006, 11:45 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 10:16 AM
  5. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21