1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Removing the first cell from a linked list

  1. Mar 10, 2012 #1
    Code (Text):
     class intList {
      int value;
      intList *nextEntry;
      intList *reverseM(intList *prev);
    public:
      intList(int v, intList *next) : value(v), nextEntry(next) {}
      intList *reverseM();
      intList *removeNthM(int i); // remove the ith element from the list
      int length();
    };

    intList *intList::removeNthM(int i)
    {
      intList *prevEntry = NULL;

     if (i >= length()) return this;
      else if(nextEntry == NULL) {  // if if the last entry is ith in a multi-cell list
        delete this;
        return NULL;
      }
      else if (i == 0 && nextEntry != NULL) {
        prevEntry = nextEntry;
        delete this;
        return prevEntry;
      }
      else {
        nextEntry = nextEntry->removeNthM(i-1);
        return this;
      }
      }
    The above code is suppose to remove the ith cell in a linked list of ints. And it appears to do except for the first/head cell in the list. Where it seems to replace the head cell with zero, instead of using the second cell as the new head of the linked list in that case. So I was wondering if anyone has an idea as how to phrase the condition to remove the head cell when i = 0 as a seperate condition in removeNthM(int i). Help in this would be great. Thanks very much. I am studying this by myself without a debugger.
     
  2. jcsd
  3. Mar 10, 2012 #2
    You seem to be trying to implement a singly-linked list. Your recursive method for removing elements is problematic. When it would get to the i-th element, it would have no way to access the previous element, in order to to connect the previous element to the next element. This is because, due the the list being singly linked, there is no way to access the previous element. One way you could resolve this would be to have the next element be removed when i == 1.

    There are other issues here. The recursive function could result in a stack that grows to a size proportional to the initial "i" value. This is a bad use of memory.

    Also, "delete this" is not right, because nextEntry would be set to a value "next" passed via the constructor. There would be no guarantee that the the memory pointed to by "next" was allocated with the new operator. Thus it would not be appropriate to use delete.
     
  4. Mar 10, 2012 #3

    rcgldr

    User Avatar
    Homework Helper

    Why do you think it replaces the head cell with zero?

    Do you want removeNthM() to return a pointer to the front of the list? If so, then you'll need to rethink how you will update nextEntry.

    You don't need to call length(). If you reach the end of the list before i == 0, then you should probably not delete anything.

    If the list only has a single element, and main calls removeNthM(0), there will be a problem. See if you can figure out why.

    What will removeNthM() return if the first cell on the list is the one removed, which is the problem you mentioned?

    Hint: note that the reverseM() function was overridden so that the private call had an additional parameter. This same technique would be useful for removeNthM(), the public function could call the private function with additional parameter(s).

    Code (Text):

    class intList {
      intList *removeNthM(int i, ???, ???);
    public:
      intList *removeNthM(int i); // remove the ith element from the list
    };
    intList *intList::removeNthM(int i) {return removeNthM(int i, ???, ???);}

    intList *intList::removeNthM(int i, ???, ???){ ... }
     
    Is it required that you implement removeNthM() via recursion instead of using a loop as part of your schooling?
     
    Last edited: Mar 10, 2012
  5. Mar 11, 2012 #4
    Thanks very, very much for the replies from both of you. A problem for me is that I study on my own and the book I am using uses recursive functions in this section of the current chapter but only introduces recursion in the next chapter: ' How to write recursive functions'.
    So, what I might do is skip onto the next chapter now, and then come back to this chapter straight away. Even though I like to read a book chapter by chapter. Thanks for the hint of writing an overloaded removeNthM(), rcgldr.
     
  6. Mar 11, 2012 #5

    rcgldr

    User Avatar
    Homework Helper

    Looking at the code again, it appears that it should work. There is a redundant check for nextEntry != NULL in the statement

    Code (Text):

      else if (i == 0 && nextEntry != NULL) {
     
    since it just checked for nextEntry == NULL in the previous else if. Alternate version that doesn't use length():
    Code (Text):

    intList *intList::removeNthM(int i)
    {
    intList *saveEntry;               // used to save nextEntry

        if(i == 0){                       // if this is node to delete
            saveEntry = nextEntry; // save ptr to next node
            delete this;                 // delete this node
            return saveEntry;         // return ptr to next node (or NULL)
        }

        if(nextEntry == NULL){      // if end list, nothing to delete
            return this;                 //  so just return
        }
                                            // else advance to next node
                                            // and update nextEntry when
                                            // removeNthM() returns
        nextEntry = nextEntry->removeNthM(i-1);
        return this;
    }
     
    Note that nextEntry isn't getting changed except in the case where i == 1, and the next call returns a pointer to a node that the deleted node used to point to. Likewise, the return from the initial instance of removeNthM() (for example, a call from main()) will return "this" except if it is called with i == 0, in which case it will return a pointer to a node that the deleted node used to point to (which may be NULL).
     
    Last edited: Mar 12, 2012
  7. Mar 12, 2012 #6
    Thank you very much, rcgldr for this reply, I am looking at the next chapter which deals on recusion only in the book. I was going to look at how to get around using length() in the original program here.Thanks again.
     
  8. Mar 12, 2012 #7

    rcgldr

    User Avatar
    Homework Helper

    I think the reason the book used recursion for these examples was to give you an idea of how the "this" pointer changes with each recursive call. It will help if you start using a source level debugger and step through these example programs to see what's going on.

    If you have windows, microsoft's visual c++ express is free and includes a good source level debugger. The biggest part of the learning curve will be to create a project. I usually create a folder and put the initial source file into that folder (usually a source file I copy from another project and rename). Then I run visual c++, and create a project with that folder name, click next and click on "empty project" (otherwise it adds a lot of stuff to your project that you won't want). Once into the project window, I click on "project", "add existing item", and click on the name of the source file, then click on the source file name in the project list to open up the source file. To turn off unicode, right click on project, properties, configuration = "all configurations", then character set = "not set". Then click on file and click on save all. The project defaults to debug mode, which includes the source level debugger. You would do a build, and then right click on the first line of the program and then click on "run to cursor". Then use F10 or F11 to step through the program.

    I assume you realize my last code example already does this?
     
    Last edited: Mar 12, 2012
  9. Mar 13, 2012 #8
    Hi, I tried running your last piece of code you gave me for the list with elements 2, 3, 5, 7; in that order. Then I tried to get it to remove the 1st element using
    Code (Text):
     theList->removeNthM(0)
    from main(), and the list it returned with was 0, 3, 5, 7. When it should be 3, 5, 7. So getting the head is a bit tricky. Then I wrote the following code:
    intList *intList::removeNthM(int i, int j){ which contains your code }, and which I made private in the class intList; the j is not used, and then I overloaded it with
    Code (Text):
     intList *intList::removeNthM(int i) {
      intList saveEntry;

      if (i == 0) {
        saveEntry = nextEntry;
        delete this;
        return saveEntry;
    }
    else
      return removeNthM(i, 0);
    }
    And when I ran it I got again 0, 3, 5, 7. Instead of 3, 5, 7. Otherwise your code worked ok with the tests I carried out on it.
    As regards getting a debugger, I was thinking of maybe Borlands command line version of C++, which I think is also free. Then I would have to know how to access the dos command line. Thank you for all your input.
     
  10. Mar 13, 2012 #9

    rcgldr

    User Avatar
    Homework Helper

    That should be

    Code (Text):
        theList = theList->removeNthM(0);
    It's working with the test code below. Here is the output:

    0 1 2 3 4 5 6 7
    1 2 3 5 6

    Code (Text):

    int main(){
    using namespace std;
    intList *theList = NULL;
    intList *tmpList;
    int i;

        for(i = 0; i < 8; i++)               // initialize list {7..0}
            theList = new intList(i, theList);

        theList = theList->reverseM(); // reverse list {0..7}

        tmpList = theList;                  // display list
        while(tmpList != NULL){
            i = tmpList->getValue();
            cout << i << ' ';
            tmpList = tmpList->getNextEntry();
        }
        cout << endl;

        theList = theList->removeNthM(8);   // attempt to remove node 8
                                                         // (there isn't a node 8)
        theList = theList->removeNthM(7);   // remove last node
        theList = theList->removeNthM(0);   // remove first node
        theList = theList->removeNthM(3);   // remove middle node

        tmpList = theList;                  // display list
        while(tmpList != NULL){
            i = tmpList->getValue();
            cout << i << ' ';
            tmpList = tmpList->getNextEntry();
        }
        cout << endl;

        while(theList != NULL){           // delete list
            tmpList = theList;
            theList = theList->getNextEntry();
            delete tmpList;
        }

        return(0);
    }
     
     
    Last edited: Mar 14, 2012
  11. Mar 14, 2012 #10
    Thanks very much for all the help. Not asigning theList as in theList = theList->removeNthM(0); was a silly mistake on my part. Thanks again.
     
  12. Mar 14, 2012 #11

    rcgldr

    User Avatar
    Homework Helper

    You're welcome. I haven't done much with classes or the "this" pointer before, so seeing it used with recursion was a learning experience for me as well.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Removing the first cell from a linked list
Loading...