Removing the first cell from a linked list

[John O' Meara]

 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 separate condition in removeNthM(int i). Help in this would be great. Thanks very much. I am studying this by myself without a debugger.

 

[MisterX]

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.

 

[rcgldr]

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.

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).

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?

 

[John O' Meara]

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.

 

[rcgldr]

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.

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

  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():

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).

 

[John O' Meara]

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.

 

[rcgldr]

I am looking at the next chapter which deals on recusion only in the book.

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 was going to look at how to get around using length() in the original program here.

I assume you realize my last code example already does this?

 

[John O' Meara]

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

 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

 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.

 

[rcgldr]

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

 theList->removeNthM(0)

from main(), and the list it returned with was 0, 3, 5, 7.

That should be

    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

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);
}

 

[John O' Meara]

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.

 

[rcgldr]

Thanks very much for all the help.

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.