C++ and Linked List Question

J

JC0724

Weaksauce
Joined
Oct 11, 2008
Messages
105
I am trying to understand the difference or why I can create a Linked List using a class constructor vs creating it with a struct(when inserting a node from the head of the list)?

Ex:
//head = NULL;
void addNode(theData) {
head = new ClassName(theData, head);
}
//This data would get being inserted at the head of the linked list, while creating a link between nodes. Also the first insert will have NULL in it, so I can use that to flow threw the linked list.

But if I have a struct

And I go

void addNode(theData) {
head = new ClassName;
head->data=theData;
}

There is no place to put in the the "head", like in the constructor if I was using a class? And if I do this

void addNode(theData) {
head = new ClassName;
head->data=theData;
head ->next = NULL;
}

Then it is not continuously adding to the list from the head, it is only adding one Node and recopying over the node over and over again.

So it is my understanding that the "new operator" creates a new node and head points to that. So I understand why the constructor why works for inserting into the head of the list. By putting the "head" in the constructor with the "new" operating you are creating a whole new node and re pointing the pointer at it while also creating a link between the nodes.

I don't see how that is possible using Struct when trying to insert from the head of the list.

Am I looking at this correctly? Am I understanding the terminology right?
 
If you use
Code: 
 tags around code in your posts here, people will like you more.

In C++, structs can have constructors. Nothing's stopping you from the exact same construct with a class or struct. 

The new operator allocates memory for a new object and runs the constructor on it. That new object can be the instance of a class or a struct, and what the constructor does is up to you. 

If you want a constructor with no parameters (the only real difference about your second example), then you need to get it initialized correctly outside of the constructor. Here's one way to make it happen:

[code]
void addNode(theData) {
   ClassName *temp = new ClassName();
   temp->data = theData;
   temp->next = head;
   head = temp;
}
 
I think you're just mixing the concepts of a linked list and a node inside of a linked list, I would keep them separate. In C and with structs, people only use one Node struct, the "trick" is their linked list is not a Node struct itself, but it's a Node* to the first node in the list. So in C++ if you want to encapsulate that into a class, you need a Node* inside your class which always points to the first node in the list. If you create an empty linked list, then that pointer should be nullptr.

Once you're inside of a class' constructor, someone has already provided memory for that instance of the class, whether it's on the stack or heap, you don't care. Your sole job in the constructor is to initialize this instance's data to a valid state. If your class has dynamicly allocated data, then you can allocate it here.

Code: 
/////////////////////////////////////////////
// Node struct

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

/////////////////////////////////////////////
// LinkedList class

class LinkedList {
public:
  LinkedList( void ) {
    head = nullptr;
  }
  LinkedList( int value ) { 
    head = new Node();
    head->next = nullptr;
    head->data = value;
  }
  ~LinkedList( void ) {
    // clean-up your linked list. The answer is not "delete head;"
  }
private:
  Node* head;
};

The constructor simply initializes the head pointer to nullptr so it is in a valid state, or if a value is provided, it allocates a node right away and initializes it. This is a silly constructor, but it's just to demonstrate. Also in C++ you can declare classes inside of classes, and this is one example where it kinda makes sense to do so.
 
Good advice, Blazestorm. I'd also add that in your example it is very easy to add and modify the data members of the struct without changing the mechanics of the linked-list. With a few tweaks that code could be easily adapted to a template to hold any type you may desire.

Its also good to mention the extra attention needed to the destructor in situations like this. Finding the end of the chain and deleting your way back is pretty simple, and any objects in the struct will have their destructor called implicitly as well, ensuring that other dynamic memory is properly released. If you want pointers in your struct, C++11's std::shared_ptr will automatically delete what its pointing at as well.

This is also a good opportunity to point out copy constructors, as those need special care if you don't want to end up with a new list object that is pointing to the members of the old one.
 
haz_mat said:
Its also good to mention the extra attention needed to the destructor in situations like this. Finding the end of the chain and deleting your way back is pretty simple, and any objects in the struct will have their destructor called implicitly as well, ensuring that other dynamic memory is properly released. If you want pointers in your struct, C++11's std::shared_ptr will automatically delete what its pointing at as well.
Click to expand...

Of course you do have to remember that in some situations (such as a doubly-linked list. It looks like the thread starter is using single linkage, but it's worth mentioning), care must be taken to avoid reference cycles. In something like a doubly-linked list, the forward link can be a shared pointer, but the reverse link should be a weak pointer. If you have to objects holding reference counting pointers to each other, the reference count will never hit zero and you're stuck with a leak. Thus, one can be a shared_ptr, but the other needs to be a weak_ptr so that only one pointer contributes to reference counts.
 
Dogs said:
Of course you do have to remember that in some situations (such as a doubly-linked list. It looks like the thread starter is using single linkage, but it's worth mentioning), care must be taken to avoid reference cycles. In something like a doubly-linked list, the forward link can be a shared pointer, but the reverse link should be a weak pointer. If you have to objects holding reference counting pointers to each other, the reference count will never hit zero and you're stuck with a leak. Thus, one can be a shared_ptr, but the other needs to be a weak_ptr so that only one pointer contributes to reference counts.
Click to expand...

Thanks for elaborating on that, definitely good to know. As always in C++ with more power comes more responsibility :)
 
haz_mat said:
Good advice, Blazestorm. I'd also add that in your example it is very easy to add and modify the data members of the struct without changing the mechanics of the linked-list. With a few tweaks that code could be easily adapted to a template to hold any type you may desire.
Click to expand...

I was keeping it simple to demonstrate the most basic implementation of a linked list in C++. It sounds like he's a beginner, so no need to bring in templates, shared_ptr, weak_ptr etc.
 
Blazestorm said:
I was keeping it simple to demonstrate the most basic implementation of a linked list in C++. It sounds like he's a beginner, so no need to bring in templates, shared_ptr, weak_ptr etc.
Click to expand...

Right. You really shouldn't be messing with smart pointers until you have a strong grasp on how regular pointers work and how to use them.
 
You must log in or register to reply here.
Back
Top