C++ and Linked List Question

[JC0133]

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?

 

[Ken g6]

Class is the C++ way to do it; Struct is the C way to do it.

In your C-style addNode functions, where is the rest of the linked list? In the C++-style function it's "head", but you haven't introduced it to the C-style functions.

If you're going to do it the C way (Though why do it that way?) you probably want to pass in the old "head" and return the new "head". (Or you could use globals, but that's just ugly.) You might consider passing the pointer by reference, so you can return the new "head" to where it came from. Or you could return the new head instead of void.

 

[Cogman]

I agree with everything ken has said.

One gotcha, though. new doesn't JUST create a new node. It creates a new node in heap memory. Memory on the heap is manually managed. That means it is vitally important that you ensure that everything which is "newed" up has an accompanying "delete" statement.

 

[purbeast0]

i remember when i first learned linked lists in college, i simply could not grasp the concept behind it. then one of my buddies who had already graduated was helping me out, and he drew it out on paper.

once i saw it drawn out on paper, it just clicked. and from that point forward, i started drawing out stuff on paper to visualize it. i'm 10 years into my career and i still draw out stuff now a days just as much as i used to do it back in college. granted, i'm not doing c++ now, but in general when i'm doing list manipulation and am having trouble, i'll draw it out and can usually see the problem immediately.

it's crazy to look back now and remember how hard i struggled with that concept, and now i understand it (and collections in general) like the back of my hand.

 

[Gryz]

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.

Have you ever tried to swap values in two variables ?

a = b;
b = a;

That doesn't work.
Do you know why ?
Do you know how to solve it ?

You are doing a similar thing in your code.
You overwrite a value, which you want to use later.
You need to use a 2nd variable. In this case, a 2nd pointer.
Use that to store a value you need later.

Give it another try.
If you still can't figure it out, I'll write an example here.

 

[sao123]

I think you need a bit of logic In your method:

 //assuming class definition
 class linked_list
 {
 //member data
 Node *head;
 Node *tail;
  
 //member methods
 void Add_at_Head(data);
 };
  
 void Add_at_head(Data)
 {
     if  (head == null)
     {  
         head = new node (data, null); 
     }
     else
     {
         node *newhead = new node(data, &head);
         head = &newhead;
     }
 }