question about Linked List, C++

Question

4.00/5 (1 vote)

See more:

Hey guys, I have a small question.

I've written this function that is supposed to insert an element at the beginning of the linked list.

C#

void insertAtStart(node* head /* pointer to head of the list*/, int data /* value of the new node that is to be inserted*/)
{
    /* perform insertion */

    node* temp = new node; // create a temporary node
    temp->next=head; // make this new node point where the head of the list was pointing previously
    temp->data=data; // update value of the temporary node
    head=temp; // make head pointer point to this newly inserted node
}

My problems start when I want to invoke above function:

insertAtStart(head,9000);

The thing is when I debug, the address where the "head" is pointing before and after invocation of the

C++

insertAtStart

function remains the same.

Thus basically nothing gets changed. Is it because "temp" node gets destroyed once the insertAtStart function has been called? or the "head" must be declared globally somewhere - if yes, why? (and why isn't current solution working?).

Thanks!

Posted 29-Sep-12 0:33am

WebMaster

Updated 29-Sep-12 0:38am

v2

Add a Solution

2 solutions

Solution 2

To: Espen Harlinn

This looks neat I will give it a try. However why does not my solution work? Actually I have noticed if I just try to change the value where a pointer is pointing to in a function it does not work. e.g.,

C#

void insertAtStart(node* head, int data)
{
    head=NULL;
}

Now if I call somewhere:

C++

node* head = someOtherPointer;
insertAtStart(head, data);
// after calling this function head still points where it was pointing, instead of pointing now to NULL?? Why? just interesting.

Posted 29-Sep-12 0:53am

WebMaster

Updated 29-Sep-12 0:54am

v2

Comments

Espen Harlinn 29-Sep-12 7:16am

void insertAtStart(node* head, int data)

head is just a value, passed on the stack, that points to a node.

By altering the code to:
void insertAtStart(node** head, int data)
you pass the address of a pointer to a node on the stack, so now you can manipulate the contents of the pointer to the node.

[no name] 29-Sep-12 10:28am

So it means "head" in this function: void insertAtStart(node* head, int data),
is basically a copy of the original "head" in some sense right? That's why when we assign a different value to "head" (e.g., as in my above example) within the function doesn't change anything right?

Espen Harlinn 29-Sep-12 10:33am

That sounds about right :-D

nv3 29-Sep-12 11:50am

head and data in your function are passed "by value". If you modify them in your function the outside values will not be influenced. To pass a parameter "by reference" you either must use a reference parameter (as the name says) or pass a pointer to the variable which you want to change. As your variable in this case is a pointer itself, you must pass a pointer-to-pointer.

[no name] 29-Sep-12 17:18pm

Yes I understand. However the trick is that if I change the value where my pointer points to, it will be changed. i.e., if I call inside the insertAt() function following:
*head=15;// for instance
then I believe also the value of the original "head" pointer will be changed.
i.e., *head will be equal to 15 in the main now. However what I discovered now is that if I just make "head" point somewhere else in the function, this doesn't affect where the original "head" value points to.

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Espen Harlinn · Accepted Answer · 2012-09-29T00:43:00

Solution 1

Alter your code to something like this:

void insertAtStart(node** head /* pointer to pointer to head of the list*/, int data /* value of the new node that is to be inserted*/)
{
    if(head == nullptr)
    {
      // Do somthing to indicate that you forgot to pass a valid pointer
    }
    /* perform insertion */
 
    node* temp = new node; // create a temporary node
    temp->next=*head; // make this new node point where the head of the list was pointing previously
    temp->data=data; // update value of the temporary node
    *head=temp; // make head pointer point to this newly inserted node
}

Which you can use like this:

node *head = nullptr;
insertAtStart(&head,8000);
insertAtStart(&head,9000);

Best regards
Espen Harlinn

Posted 29-Sep-12 0:43am

Espen Harlinn

Comments

pasztorpisti 29-Sep-12 7:45am

+5, however this whole stuff looks much like C to me. :-) Instead of if a lot of times a debug runtime check with assert does the job but in this case I would rather use neither if(null) nor assert, since the tag is C++ I would rather go with node*& head and in this case the ref isn't null by definition. If it happens to be null then the error is somewhere else deeper in the call stack.

Espen Harlinn 29-Sep-12 8:01am

Thanks, I guess OP is currently learning this stuff, otherwise he would probably be using std::list

pasztorpisti 29-Sep-12 8:27am

Sure, at the beginning every small piece of info is gold. :-)

[no name] 29-Sep-12 10:26am

"Thanks, I guess OP is currently learning this stuff, otherwise he would probably be using std::list"

Hey, not actually, I was just trying to dig in how data structures like linked list work for instance. Thanks for your help anyway.

Espen Harlinn 29-Sep-12 10:30am

Hmm, wasn't trying to be insulting, and doesn't "trying to dig in how data structures like linked list work" and "learning this stuff" mean the same thing?

[no name] 29-Sep-12 10:37am

I didn't take your comment as an insult :)

Espen Harlinn 29-Sep-12 10:38am

Brilliant :-D