Implement an advance method in a linked list without const cast

Question

I'm making a rather simple version of a linked list which is accessed through a Link class. The goal here is to make an advance() method that will be used to traverse the list. However, the most lightweight solution I have involves using a const_cast which is undesirable. Is there solution to this that I have not considered?

Link* Link::advance(int n) const
{
    if(!this) return nullptr;

    Link* it = const_cast<Link*>(this);
    if(n > 0) {
        while(n--) {
            it = it->next(); //the next link in the list
        }
    }
    else if(n < 0) {
        while(n++) {
            it = it->previous(); //the previous link in the list
        }
    }
    return it;
}

Answer 1

This is more of a semantical problem than it seems.

By having the signature: Link* Link::advance(int n) const

What this means is that given a node instance of your linked list you want it to provide access to one of its brother node wether in front or behind it.

The interesting part is the following: A node does not own its brothers.

They all kind of exist at the same level. This is even more obvious given that the same node is pointed to by a next and a previous pointer at the same time from different other node instances.

The reason why your node can provide access to other nodes it doesn't own, is because he has a link to a non const instance of them (a next and a previous pointer). And that is the only reason. This has nothing to do with the current node instance itself and thus justify the const of the advance member function.

Now the only real problem comes from the fact that a node has no link to itself, and thus cannot provide access to itself the same way it can provide access to one of its brother.

---

There are two ways to take actions based on that:

1) Either you change the base facts of this situation, which means changing Link* Link::advance(int n) const, and there are multiple ways to do this like removing the const, adding an iterator concept and other methods, returning const instances etc. each takes a different approach angle.

2) Or you keep on this path which means you need to have a link on yourself too to totally respect the semantic you have given to your function:

class Link
{
public:
  Link()
    :
    previous_(nullptr),
    current_(this),
    next_(nullptr)
  {}

  // ...

  Link* advance(int n) const;

  // ...

  Link* previous() const { return previous_; }
  Link* next() const { return next_; }

  // ...

private:
  Link *previous_;
  Link * const current_;
  Link *next_;
};

Link* Link::advance(int n) const
{
  //if(!this) return nullptr;

  Link* it = current_;
  if(n > 0) {
    while(n--) {
      it = it->next(); //the next link in the list
    }
  }
  else if(n < 0) {
    while(n++) {
      it = it->previous(); //the previous link in the list
    }
  }
  return it;
}