Linked Lists and what's pointing to what and when

[John O' Meara]

 class intList {
  int value;
  intList *nextEntry;
  intList *reverseM(intList *prev);
public:
  intList(int v, intList *next) : value(v), nextEntry(next){}
  int getValue() { return value; }
  intList *getNextEntry() { return nextEntry; }
  intList *reverseM();
};

intList *readFowardList()
{
   int inputval;
   intList *front = NULL;

  cout << "Enter number: " ; cin >> inputval;

  while(!cin.eof()) {
     front = new intList(inputval, front);
     cout << "Enter number: ";  cin >> inputval;
  }
  cout << '\n';
  return front->reverseM();
}


int main() {
  intList *theList;


  cout << theList;

  deleteList(theList);

  return 0;
}

See the 2nd page of the attachment for reverseM() definition please. If you look at the 1st page of the attachment; the top of that page shows the way I think how the function reverseM() is called; in the middle of that page I show the 'returns' of reverseM() as I think what is going on. where the list consists of just three cells, namely, 5 3 and 2, and we want reverseM() to reverse that list. According to my middle of the page diagram, the 'this' pointer is the first to return (with the new head of the list) after reverseM() is finished being called and then the local 'front' pointer then returns; why don't the the local pointers 'front' overwrite the local 'this' pointer and in conquence the new head of the reversed linked list be lost? Or is that middle diagram wrong, also are the upper diagrams wrong then? Time increases downward vertically on the 1st page of the attachment. I just don't see how it is possible not to overwrite the the 'this' pointer which returns the address of the value 2 as the head of the reversed list. So if anyone can draw/write out the sequence of events in this three cell linked list, I would be grateful. Thanks in advance.

 

[Mark44]

Why not attach your code as a text file instead of a PDF?

 

[John O' Meara]

I didn't think that hand drawn sketches could be stored as a .txt file.

 

[Mark44]

No they can't, other than very rudimentary sorts of things. I didn't realize that you had something other than code in the pdf (which I didn't open).

 

[rcgldr]

If you have a source level debugger, you could follow the code to see what is happening.

Here is a summary: reverseM() calls itself until it reaches the end of the list. The public call to reverseM() is overridden so it the initial call passes a parameter of NULL for "prev". For each instance of reverseM(), its "this" pointer will be a pointer to the instance of intList used to make the call to reverseM(), while "prev" will be a parameter passed to reverseM(). "front" doesn't get set until the end of the list is reached, and then it's just returned back up the call chain without ever getting modified.

Using your pdf document, initially theList points to "5" (the element with a 5). On the initial call to reverseM(), "this" will point to "5", and prev will be set to NULL (due to the override declaration). Then reverseM() will call itself using the nextEntry pointer to "3" and passing the pointer to 5, and that instance of reverseM()'s "this" will point to "3", and "prev" will point to "5". In the next instance, "this" points to "2", and "prev" points to "3", and since this->nextEntry = NULL, it sets this->nextEntry to "3", sets front to "2", and returns front. The prior instance of reverseM() will set "3"->nextEntry to "5", and return front still = "2". The next prior instance of reverseM() will set "5"->nextEntry to the NULL passed from the initial call, and return front still = "2", returning back to main.

You might want to replace main with something like this if you use a source level debugger to avoid having to key in numbers:

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

    for(i = 0; i < 8; i++)
        theList = new intList(i, theList);

    theList = theList->reverseM();
    
    while(theList != NULL){
        i = theList->getValue();
        cout << i << endl;
        delList = theList;
        theList = theList->getNextEntry();
        delete delList;
    }

    return(0);
}

 

[John O' Meara]

I use a port of gcc for my operating system called RISC OS, but they don't seem to have the gdb debugger ported. Thank you very much for your time in answering my thread and for the code. I have included another pdf document that shows now my understanding of what happens when reverseM() is called and then returns.

 

[rcgldr]

I have included another pdf document that shows now my understanding of what happens when reverseM() is called and then returns.

Here's a list starting at time = zero

this   prev nextentry front   

   5    null             3      x   values at entry to reverseM()
   3       5             2      x
   2       3          null      x
 -------------------------
   2       3            3       2   values at exit from reverseM()
   3       5            5       2
   5    null         null       2