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

user_8936368 0
Viewed 162

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.

data-structures c++
3 Answers

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.

user_4049700

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.

user_45813010

Yes, your code is correct for your question "not to create new nodes for a function called rest(), where the rest list is returned without the head."

But you need to delete the head node in case your professor want. But he not mention it so I assume that he just want to return the rest without head.

template<typename T>
struct ListNode{
    T value;
    ListNode<T>* next;
    ListNode(const T &v) : value(v), next(nullptr) {}
};

ListNode<int>* rest(ListNode<int> *head)
{
    if (head) // head is not nullptr
        return nullptr;
    else
        return head->next;
}

You could imagine like below:

In example, we have a list with a few elements and a head pointer which point to the first element:

0x1             0x2                    0x3
-------         --------------
|head |     --> |value1| next|    -->  .....
-------         --------------

so that mean :

&head = 0x1; // the address of pointer head is 0x1

head = 0x2; // head pointer will point to the block memory which have address 0x2, i mean, the first element of list

next = 0x3; // next pointer will point to the block memory which have address 0x3, the second element of list

So when we call "return head->next", you can easy see that it will return 0x3, the address of the second element.

user_14255200
Related