General Practise (?) Question wrt Linked Lists

[nesevolved]

This has nothing to do with any particular piece of code, but is more of a "what's good practise" question. When designing nodes to use in linked lists (and other data structures), which method of storing data within the node tends to work best, an instance of an object, or a pointer of the object's type? My natural inclination would be to use a pointer, as it seems to me to be better for decoupling the actual information from the list. In reality, is the coupling of the data to the node a moot point, or would decoupling it lead to more errors (memory leaks, et cetera) than it's worth? Thanks in advance for any answers you may provide.

struct Node{
  int val;
  Node* next;
};

vs

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

[Zhuge]

I can't think of a good reason you'd want to use a pointer to the data type rather than just the data type.

...Perhaps if you had large amount of static data that was expensive to copy and you were making a linked list of some subset of that data, or something?

[nesevolved]

Yeah, that's more or less the use case I had in mind. Specifically, I was planning to use it as part of a collision detection algorithm for what *might* be our final project in my data structures class (writing a Zelda-esque game). The objects might get rather on the large side, and I wanted to be able to bypass all that copying. I'm thinking that I could make two sorts of nodes, a Node, that has an instance of the data for fundamental types or smaller classes, and have a PNode to handle this sort of situation. I would just use the STL, but seeing as it is an elementary data structures course, I don't think my prof would be too happy about that. :) Anyway, thanks for your reply, Zhuge.

[IWishIKnew]

well, if you're worrying about leaks, wrap it in a class. Classes are made for this.

[keskiverto]

I would just use the STL, but seeing as it is an elementary data structures course, I don't think my prof would be too happy about that.

The T in STL means template. std::list takes the data-type as template parameter. Thus, a "node" is generic.

The standard containers do copy their values. Therefore, one has to use a pointer-type, if copying is not possible for the data-type, or is very expensive. Polymorphism is an another example, where pointers are required.

There are several "smart pointer" variations for avoiding leaks. The main design question with dynamically allocated memory is, who owns the data? The owner should deallocate, and others should not dereference after that.