In-place reversal of a singly linked list

Question

As suggested in The 2nd Monitor, I'd like a review of this in-place reversal of a singly linked-list:

#include <iostream>

struct node { 
    int data;
    node *next;
};

node *reverse(node *list) { 
    node *prev = NULL;
    node *next;

    while (list) {
        next = list->next;
        list->next = prev;
        prev = list;
        list = next;
    }
    return prev;
}

void show_list(node *list) {
    while (list != NULL) {
        std::cout << list->data << ", ";
        list = list->next;
    }
}

int main() {
    node *list = NULL;

    for (int i=0; i<10; i++) {
        node *n = new node;
        n->next = list;
        n->data = i;
        list = n;
    }

    std::cout << "As built: ";
    show_list(list);

    list = reverse(list);

    std::cout << "Reversed: ";
    show_list(list);
    return 0;
}

Answer 1

The code of actual reversal is fine, so like previous answers I only have a some suggestions on general style. As discussed by Corbin, raw memory management is very error prone, and you should avoid it at any cost. It is even more dangerous in the presence of exceptions; even if your code is bug-free, you can still have leaks. Without trying to change the logic too much, below are some minimal changes that will help you organize code better. Here's a live example.

---

Node data structure:

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

    explicit node(T&& d = T{}, node *n = nullptr) :
        data(std::move(d)), next(n) { }

    explicit node(const T& d, node *n = nullptr) :
        data(d), next(n) { }
};

A node is now a class template over the value type T. A couple of constructors make it easier and safer to construct a new node. In case T has move semantics, separate move and copy constructors will be more efficient. Use nullptr instead of NULL.

---

Actual reversal:

template<typename T, typename N = node<T> >
N *reverse(node<T> *list)
{
    N *prev = nullptr;

    while(list)
    {
        N *next = list->next;
        list->next = prev;
        prev = list;
        list = next;
    }

    return prev;
}

Use type aliases like N to make code more compact. A default template argument is maybe my personal style of saving lines of code. You will probably find this unclear, so use an explicit using N = node<T>; declaration instead. Keeping declarations at first use like N *next make code clearer. Don't worry about efficiency here, leave this to the optimizer.

---

Streaming:

template<typename S, typename T>
void show_node(S& s, node<T> *&list)
{
    s << list->data;
    list = list->next;
}

template<typename S, typename T>
S& operator<<(S& s, node<T> *list)
{
    if (list)
        show_node(s, list);

    while (list)
    {
        s << ", ";
        show_node(s, list);
    }

    return s;
}

Overload operator<< for streaming. Print separators only between elements, not at the end of the sequence. If this leads to code duplication, use an auxiliary function like show_node().

---

List management:

template<typename T, typename N = node<T> >
N *make_list(size_t L)
{
    N *list = nullptr;

    for (size_t i=0; i<L; ++i)
        list = new N{T(i), list};

    return list;
}

template<typename T, typename N = node<T> >
void delete_list(node<T> *list)
{
    while (list)
    {
        N *next = list->next;
        delete list;
        list = next;
    }
}

As a minimal protection against bugs, define individual functions to generate and to clear a list. See now how convenient is node's constructor (new N{T(i), list}). Note that T(i) assumes a size_t can be implicitly converted toT`. In more realistic example you should be careful about conversions.

---

Main:

int main()
{
    auto list = make_list<int>(10);
    std::cout << "As built: " << list << std::endl;

    list = reverse(list);
    std::cout << "Reversed: " << list << std::endl;

    delete_list(list);
}

Using list management functions and streaming operator, main() is now cleaned up. The very next step would be to make sure delete_list is automatically called at end of scope, but as I said I am not changing the logic too much here.

Answer 2

• You don't use delete after allocating nodes with new, resulting in a memory leak. As a general rule, delete should be used in the same way new was used.

  In this case, have an identical for loop and use delete on each node:

  for (int i=0; i<10; i++) {
      delete n;
  }
  

  With these two loops, you might as well have a constant to hold the number of nodes to use, so that you can make sure the same number is used.

• You don't need to have return 0 at the end of main(). Reaching the end implies successful completion, and the compiler will insert this return for you.

Answer 3

I think there are a few points worth mentioning that I haven't seen in any replies yet.

struct node { 
    int data;
    node *next;
};

As @Edward mentioned, this should almost certainly be a template. The next pointer should almost certainly be a unique_ptr instead of a raw pointer.

node *reverse(node *list) { 
    node *prev = NULL;
    node *next;

    while (list) {
        next = list->next;
        list->next = prev;
        prev = list;
        list = next;
    }
    return prev;
}

Although a couple of people mentioned exceptions, nobody mentioned the fact that this code isn't re-entrant. If an exception is thrown while the list is being reversed, the list will typically be left in a bad state--in particular, part of it may be orphaned. The reversal is done by traversing the list, and manipulating each node's pointer to point to the previous node instead of the next one. While this is being done, the list is basically broken into two pieces. An exception thrown in the middle of that process is likely to "lose" one of the pieces.

Likewise, making this thread safe (by almost any reasonable definition of the term) basically requires that the entire reversal process be treated as a single critical section. That is to say, no other thread can be allowed to read part of the list at any point in the reversal process. This is likely to be a serious problem if there is much contention for use of such a collection.

void show_list(node *list) {
    while (list != NULL) {
        std::cout << list->data << ", ";
        list = list->next;
    }
}

This displays a comma and space after the final item in the list. It would be better to provide access to the items in the list via iterators. With iterators, it would be trivial to use something like an infix_ostream_iterator to display the data more neatly.

node *list = NULL;

As @iavr showed, it's better to use nullptr instead of NULL. While NULL works perfectly well to produce a null pointer, it can also be used by accident in places that aren't related to pointers at all (because NULL is simply a macro for the value 0). By contrast, nullptr can be assigned to any pointer, but not to other types such as integers.

Overall, this code should clearly be avoided for almost anything except its originally intended use (in-place reversal of a linked list).

Since @David K mentioned the possibility of using std::list, and std::slist, I'll point out yet one more possibility. If you honestly need to a linked list (you probably don't) and need to traverse in both directions, and you really can't afford a doubly-linked list like std::list, there is one other possibility that may be worth considering: a doubly linked list that stores only one link per node.

Although thoroughly crufty in some ways, this structure is just clever enough to be worth mentioning in this context. To store both backward and forward links in only one link field, what we store in the node is actually the exclusive-or of the addresses of the previous and next nodes in the list. The parent linked-list typically stores a dummy node containing pointers to the first and last nodes in the list.

We can then use those pointers to recover the rest of the pointers. We have the address of node A, and the XOR of the addresses of node A and node B. Xoring those two together gives us the address of node B. That node, of course, contains the XOR of the addresses of node B and node C. Since we already have the address of node B, we can XOR it with the value from the node to get the address of node C (and so on for the remaining nodes in the list).

Conversely, if we start with the address of node Z and the XOR of the addresses of node Z and node Y, we can use exactly the same procedure to isolate the address of node Y. That, in turn, is enough to recover the address of node X, and so on through the list in reverse.

This obviously has its own set of strengths and weaknesses. The most obvious weakness is simple obscurity--virtually nobody will simply recognize this structure and understand how it works without at least a little study (and a few probably won't trust it even then). Less obviously, this technique is generally incompatible with automated (tracing-based) garbage collection. A garbage collector detects what memory is still accessible by traversing all accessible pointers. Without special knowledge about how to recover the actual pointers in the list, all but the first and last nodes of this list will appear inaccessible.

Nearly the sole real strength is what was stated up front: this lets you build a linked list that can be traversed in either direction while storing only (bits the same size as) one pointer per node. Since it can be traversed in either direction without modification, it avoids the reentrancy problems inherent in the original code.

Answer 4

While this a good example of a list reversal algorithm from a purely algorithmic point of view, the finer details with regards to the list and the reverse implementation are in need of some work.

---

The biggest problem here is that the proper tools haven't been used for abstraction and encapsulation of the list. In particular, you should have a list class that manages your sequence of nodes rather than managing the node's bare. This allows you much easier use, and it provides a much cleaner interface. Compare what you're doing to something as simple to use as:

list l;
l.add(3);
l.add(5);

This also gives the benefit of encapsulating memory management of the nodes. Raw memory management with new and delete is extremely error prone and has all kinds of non-obvious caveats (exception safety, flow jumps can cause leaks, etc). Manual memory management should only be used in low level containers. Everything else should hide it behind RAII by either having a container manage it (like list managing nodes) or through smart pointers (when a container doesn't make sense).

It should be noted that the higher level of abstraction does come at a cost to you, the developer. By alleviating the consumer's responsibility to manage the nodes, you must do it yourself behind the scenes of a few public methods. Also, in order to allow the consumer to examine the list, you would need to implement some form of iterator. Unfortunately, both of these things coupled together means that a list is going to be much more complicated than a set of nodes. If your goal was just to demonstrate a simple reversal algorithm, a list would be overkill. Then again, if you had iterators, you could simply use a reverse iterator and you wouldn't need to actually reverse the list (though this would of course require a doubly linked list for the expected linear performance).

(Oh also, if you do make a list, don't use the name list unless you put it in namespace. Someone would inevitably drag your list and std::list into the global namespace, and it could end badly.)

---

Even if you don't make a full out list class, you should make some effort to abstract away the gritty details. The most obvious and straightforward way to do this is to use functions rather than operating on the list directly (node* list_add(node* head, int data);, list_destroy(node* head);, so on). Not only does this reduce code duplication (and thus the likelihood of fixing one section of code only to leave another broken), but it provides a better experience to use the list.

---

On a more stylistic/technical note, I would give node a constuctor. That allows you to save quite a bit of initialization code when creating nodes:

struct node { 
    int data;
    node *next;
    explicit node(int data, node *next = NULL) : data(data), next(next)
    { }
};

This allows much more succinct node creation:

for (int i=0; i<10; i++) {
    list = new node(i, list);
}

---

When there are simple conditions and post-actions, I find for loops easier to immediatley grasp than while loops:

void show_list(node *list) {
    for (; list != NULL; list = list->next) {
        std::cout << list->data << ", ";
    }
}

---

The semantics of your reverse strike me as a bit C. list = reverse(list) makes it look like a new copy of the list is created that is reversed. For example, imagine node* newList = reverse(list). Without reading the code (as there is no documentation), it is not clear that newList is not copy of list. After this call, list is no longer safe to use, but nothing indicates this. It's just an unexpected side effect.

This usage seems a bit unnatural and prone to error. I would mutate the parameter to reverse. You can even still return it for the list = reverse(list) usage if you want (though I wouldn't since that brings back the ambiguity of whether or not a copy is made).

void reverse(node*& list) {
    node *prev = NULL;
    node *next;

    while (list) {
        next = list->next;
        list->next = prev;
        prev = list;
        list = next;
    }
    list = prev;
}

Answer 5

Code this valuable shouldn't be limited solely to int data.

template<typename T>
struct node { 
    T data;
    node *next;
};

Answer 6

It might be helpful to have a little more context for this code, to answer questions such as why you don't do something like this:

#include <list>
...
  std::list<int> my_list;
  ... put something in my_list to make a non-trivial test ...
  show_list(my_list);
  my_list.reverse();
  show_list(my_list);

There's also a singly-linked list, slist, if you want to avoid the double-linking of std::list, although I've previously found slist not as portable as std::list. (That is, not everyone's implementation of the STL seemed to provide it.)

If it's really worth creating your own linked list, how about making a class called something like List containing objects of type Node, or implement these as templates List<T> and Node<T> as others have recommended? Then you can make reverse() be a member function of List<T> so that you can write something like:

List<T> my_list;
... other code ...
my_list.reverse();

A member function returning void would be my preferred way to modify an object "in place"--the function doesn't return anything, and in this case it doesn't even have parameters to play with, so it's clear the ONLY thing it can do is to modify the original list. And notice that that's how list reversal is implemented in STL.