How do you allocate memory for an linked list when passing its reference instead of its pointer?

How do you allocate memory for an link list when passing its reference instead of its pointer?

For example:

struct node {
  string info;
  node *next;

};

void add(node &aNode){


//if I use
node *newNode;
newNode = new node;
aNode.next = newNode; //aNode.next = newNode; doesn't work either

//allocating on heap seems to give segmentation error.


}


int main() {                                                        

  node *aNode;
  aNode = new node;
  add (aNode);


}

Compiler error: error: invalid initialization of reference of type ‘no开发者_开发百科de&’ from expr

alternatively if I use

int main() {                                                        

  node aNode;
  add (aNode);
  add (aNode);
  aNode.next->next->info = "abc";
  string a = aNode.next->next->info;


}

This give segmentation fault.

So is it possible to allocate for an linked list just with its reference? (this is C++)

It should be

node * newNode = new node;
aNode.next = newNode

You have to take care of deletion manually, e.g. check if aNode.next isn't already occupied (and delete if it is).

Further, the add function signature should read:

void add(node & aNode) { ... }

By the way, the STL comes with a nice <forward_list> ;-)

It's hard to tell what you're actually asking, but going by the question title perhaps you have in mind a node structure like this:

struct Node {
  Node & next;
  /* payload data */
  Node(Node & n) : next(n) /* ... */ { }
};

Such a node would store its successor "by reference"; but you would have to initialize it with an existing node! (There is no such thing as a "null" reference.) By the Poultry-Oval Impasse, you cannot do this.

Alright, while you continue to refuse to post your full code, here is my almost literal copy/paste of your code which works fine with me:

Update: I'm adding a feature to add a node at the end, which you might want.

#include <string>

struct node {
  std::string info;
  node *next;
  node(std::string i = "") : info(i), next(NULL) { }
};

void add(node &aNode)
{
  node *newNode;
  newNode = new node;
  aNode.next = newNode;
}

void add_at_end(node &aNode, std::string value = "")
{
  node *newNode, *n = &aNode;
  while (n->next) n = n->next; // move to the end

  newNode = new node(value);
  n->next = newNode;
}

int main()
{
  node aNode, bNode;
  add(aNode);
  add_at_end(bNode, "Hello");
  add_at_end(bNode, "World");
  add_at_end(bNode, "!");
}

Compile with g++ -o prog prog.cpp -W -Wall -pedantic.

Finally, here's the STL way of achieving the same thing:

#include <forward_list>
#include <string>
int main() {
  std::forward_list<std::string> bList;
  bList.push_front("Hello");
  bList.push_front("World");
  bList.push_front("!");
}

In your second variant of main(), you are calling add(aNode) twice. But you're providing it the same parameter each time. So although you're creating two new node objects, one of them is lost forever (a memory leak). And aNode.next ends up pointing to the other one. aNode.next->next is not a valid pointer, hence the seg-fault when you try to access something through it.

Depending on what you want to achieve, you could try this:

node aNode;
add(aNode);        // Basically does: aNode.next = new node;
add(*aNode.next);  // Basically does: aNode.next->next = new node;

There are better ways of doing linked-lists, but this would at least avoid the seg-fault.

Try

int main() {                                                        

  node *aNode;
  aNode = new node;
  add (*aNode);
}

You have to pass reference to object, not a pointer.

I checked your code and I didn't get segmentation fault when allocating on stack: http://ideone.com/gTRIG.

My proposition:

#include <string>
using namespace std;

struct node {
  string info;
  node *next;
  node(string str): info(str), next(NULL) {}
  ~node() { if(next != NULL) delete next; }
  node *add(string info){
    node *newNode = new node(info);
    return aNode.next = newNode;
  }
};

int main(){
  node rootNode("My rootnode");
  node *nxt = rootNode.add("Next node");
  nxt->add("Last node");
  // No need to call delete, because destructor will clear heap
}