C++ Recursive Function to Copy the Contents of a Linear Linked List into an Integer Array

[confundido]

Good Evening, I'm trying to write a function (or functions) that copies the contents of a linear linked list (with integer data members) into a dynamically allocated integer array, recursively, without excessive traversals.

I had a working example that counted the listed once, then dynamically allocated the array based on the count, and then filled it, but I was told to try to get it down a single go, and I can't really figure it out.

Here's what I have (we are supplied code that generates a randomly sized linear linked list, with random integer data members).

int copyToArray(node*src, int count)
{
   if(!src)
   {
      cout << "End of list, count is at: " << count << endl;
      return 0;
   }

   copyToArray(head->next, ++count)
   cout << "Adding " << src->data << " to array position " << count << endl;
   --count; //Decrement counter.

   return 1;
}

My issue is where to place the new integer declaration. If I put it in the base case, then the declaration is not defined for the lower half of the function. If it put it in the lower half of the function, it will get repeatedly created with each frame.

Anyone have any advice or suggestions?

[mbozzi]

Just fill the array as you go.
When you run out of space in the array, create a new one with 1.5 times the capacity and copy the old elements over.

[dhayden]

Here's the pseudo-code

// Copy the list to a dynamically allocated array. Return a pointer to the array.
int *copyToArray(node *src, int count=0)
{
    if (src == nullptr) {
         // allocate the array with exactly the right size.
         // return the allocated array
   } else {
        // 1. call copyToArray() recursively to allocate the array and copy the items
        // that follow src
        // 2. store src->value (or whatever it's called) in the array at the right position
        // 3. return the array
}

[jonnin]

you can do it in one go, sorta.
recursively..
if not end of list, add one to a static counter.
if end of list, allocate the static array to counter size, and insert the element. (base case)
popping back, insert the element only.
this is still, really, 2 iterations, one to recursively push and popping back out, still really O(2n) instead of pure O(n) (keeping constants to show the difference here).

if your list knew its size, it would be better: allocate to list.size() and then fill in one iteration. is that allowed? Having a size also lets you check isempty and similar things efficiently.

[mbozzi]

@jonnin, I like your idea of performing the insertion on the way back up the stack.

[dhayden]

Oh man, don't I get any credit? I posted pseudo-code of a working solution that's the same as jonnin's, complete with inserting on the way up. Sniff sniff... nobody loves me. :) :) :)

[jonnin]

Not sure yours was there when I started mine. But great minds think alike and all that :)

[mbozzi]

Sniff sniff... nobody loves me.

We love you @dhayden. Just didn't see your post. :-D

[confundido]

Thank you all for your assistance! Sorry I didn't respond sooner.