By returning a pointer that points to a node, is the rest of the list returned as well? c++

Question

I have a project to do where I have to change SLList to LispList and add a few other functions. My only question is that My prof. has asked us not to create new nodes for a function called rest(), where the rest list is returned without the head.

Node* rest(){
      Node* nextToHead = head -> next; //this is a pointer to the next node in the list
      return nextToHead;
    }

by using the pointer nextToHead, will it point to the rest of the list as well? If not, it'll be great if you guys can give me tips on how to return the list without the head and without using any other nodes.

Answer 1

While that technically does return a pointer to the rest of the list, or at least its nodes, the "rest" of a Lisp list is itself a Lisp list – not a different type (like node).

A "Lisp list" doesn't have a head as such; it looks pretty much like this:

struct List
{
    ElementType data;
    List* next;
};

and has the operations

ElementType first(List* l) { return l->data; } /* or "car" */
List* rest(List* l) { return l->next; }        /* or "cdr" */

or, as members:

ElementType List::first() { return data; }
List* List::rest() { return next; }

Note that every node in a Lisp list is the "head" of a sublist of the entire list.

Answer 2

When you return a Node pointer, everything the Node exposes can be used and abused. This includes the rest of the list.

The usual solution is to abstract the Node behind an iterator so that the user doesn't even see a Node. All they get is an iterator. The iterator still provides access to the rest of the list, so you have to restrict things even further

SingleNode rest(){
  return SingleNode (head -> next); 
}

where SingleNode looks something like

class SingleNode
{
    Node* node;
public:
    MyDataType& operator*()
    {
        return node->data;
    }
};

If you can't do this,

1. Make the links in Node private to limit access.
2. Make SLList a friend of Node so only Node and SLList can see the links.
3. Do not have any accessor functions for the links.

Example:

struct Node
{
    friend class SLList;
    MyDataType data;
    // other public stuff
private:
    Node * next;
    // other private stuff
};

Now the holder of a Node pointer can not see the rest of the list. They can still blow up the list by damaging the Node they have access to, but they have to work at it.