Using an array of pointers-to-pointers to manipulate the pointers it points to (C++)

Question

I've been doing this as an exercise on my own to get better at C++ (messing around with a linked list I wrote). What I want to do is to reverse the list by twisting the pointers around, rather than just 'printing' the data out in reverse (which is relatively straightforward).

I have an array of pointers-to-pointers, each pointing to a node in a linked list. But this is less a question about linked-list dynamics (which I understand), and more about pointer magick.

A node looks like this,

template<class T>
struct node {
    T data;
    node *next;

    node(T value) : data(value), next(nullptr) {}
};

And the code in question,

  node<T> **reverseArr[listLength];
  node<T> *parser = root;

  for (auto i : reverseArr) {
      i = &parser;
      parser = parser->next;
  }   

  root = *(reverseArr[listLength - 1]);   
  for (int ppi = listLength - 1; ppi >= 0; --ppi) {
        if (ppi == 0) {
            (*reverseArr[ppi])->next = nullptr;
            //std::cout << "ppi is zero!" << "\t";
        }
        else {
            (*reverseArr[ppi])->next = (*reverseArr[ppi - 1]);
            //std::cout << "ppi, 'tis not zero!" << "\t";
        }
  }

My logic:

The new root is the last element of the list,
Iterate through the array in reverse,
Set the current node's next pointer to the previous one by setting the current node's nextNode to the next node in the loop.

What's happening:

If I leave the debug print statements commented, nothing. The function's called but the linked list remains unchanged (not reversed)
If I uncomment the debug prints, the program seg-faults (which doesn't make a whole lot of sense to me but seems to indicate a flaw in my code)

I suspect there's something I'm missing that a fresh pair of eyes might catch. Am I, perhaps, mishandling the array (not accounting for the decay to a pointer or something)?

Welcome to Stack Overflow. Please take the time to read The Tour and refer to the material from the Help Center what and how you can ask here. — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Jun 6, 2017 at 2:44
The right tool to solve such problems is your debugger. You should step through your code line-by-line before asking on Stack Overflow. For more help, please read How to debug small programs (by Eric Lippert). At a minimum, you should edit your question to include a Minimal, Complete, and Verifiable example that reproduces your problem, along with the observations you made in the debugger. — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Jun 6, 2017 at 2:44
Thanks for the feedback. I'll try to edit the question (to better reflect the guidelines) as soon as I can. — Zaeche
– Zaeche, Commented Jun 6, 2017 at 2:53

paddy · Accepted Answer · 2017-06-06 04:00:54Z

0

You're overthinking the problem. The correct way to reverse a single-linked list is much simpler than you think, and does not involve arrays at all.

All you need to do is walk through the list setting each node's next pointer to the head of the list, then set the head of the list to that node. Essentially, you are unlinking each node and inserting it at the start of the list. Once you reach the end, your list is reversed.

It just requires a bit of care, because the order that you do things is important. Something like this should do it:

template <class T>
node<T> * reverse( node<T> * head )
{
    node<T> *current = head;
    head = NULL;

    while( current != NULL )
    {
        // store remainder of list
        node<T> *remain = current->next;

        // re-link current node at the head
        current->next = head;
        head = current;

        // continue iterating remainder of list
        current = remain;
    }

    return head;
}

The operation has a linear time complexity. You would invoke it by passing your list's head node as follows:

root = reverse( root );

It should go without saying that it would be a bad idea to call this function with any node that is not the head of a list, or to pass in a list that contains cycles.

answered Jun 6, 2017 at 4:00

paddy

63.7k7 gold badges68 silver badges109 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Zaeche Over a year ago

Coming back to it, it's unfortunate but the question I asked was far too vague for a proper answer (and I feel trimming it/adding debug wouldn't improve it by much). Paddy's answer is correct when talking about linked lists and how to reverse their pointers (I've already done something similar a while ago using recursion). My original intention had been to deliberately try to use pointers-to-pointers and their relationships to achieve the same goal (or at least see how far I could go with it). Would it be fine to accept this answer? I believe it answers the question as it was asked.

Collectives™ on Stack Overflow

Using an array of pointers-to-pointers to manipulate the pointers it points to (C++)

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related