Adding node to the front of a linked list

Question

I'm really confused as to what exactly is going on here..

I have the function

void addToFront(int data)  
{
  Node* tmp = new Node();
  tmp -> data = data;
  tmp -> next = head;
  head = tmp;
}

So when we do the line tmp-> next = head, we are making the tmp pointer point to what head is pointing to (the current first element of the list)? Because that's what it feels like, but wouldn't that just make it point to head? And then when we do head = tmp, we are making head point to the new node that we created, correct?

Sadique · Accepted Answer · 2013-10-05 05:34:39Z

15

This is how your list was (suppose)

 +----+-----+   +-----+-----+   +-----+------+
 |  A |     +-->|     |     +-->|     |      |
 +----+-----+   +-----+-----+   +-----+------+
 /

Head is pointing to location A.

You make a new node

 +----+----+
 | B  |    |
 +----+----+
 /

tmp now points to B. You insert data in tmp->data, and then make tmp -> next = head;. So now we have:

 +----+----+     +----+-----+   +-----+-----+   +-----+------+
 | B  |next|---->|  A |     +-->|     |     +-->|     |      |
 +----+----+     +----+-----+   +-----+-----+   +-----+------+
                  /

And then you makehead to point to B instead of A.

 +----+----+     +----+-----+   +-----+-----+   +-----+------+
 | B  |next|---->|  A |     +-->|     |     +-->|     |      |
 +----+----+     +----+-----+   +-----+-----+   +-----+------+
 /  \

head & tmp point to B now.

edited Oct 5, 2013 at 5:34

answered Oct 5, 2013 at 5:22

Sadique

22.8k7 gold badges68 silver badges92 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

ChuckCottrill Over a year ago

Here is a complete implementation stackoverflow.com/questions/19148576/…

David Schwartz · Accepted Answer · 2013-10-05 05:13:19Z

1

So when we do the line tmp-> next =head, we are making the tmp pointer point to what head is pointing to (the current first element of the list)? Because that's what it feels like,

Correct.

but wouldn't that just make it point to head?

No. To point to head, it would need to contain the address of head. But this line makes it contain the value of head. So no.

And then when we do head = tmp, we are making head point to the new node that we created, correct?

Yes.

answered Oct 5, 2013 at 5:13

David Schwartz

184k18 gold badges229 silver badges293 bronze badges

8 Comments

FrostyStraw Over a year ago

@so then since the value of a pointer is the address of the thing it points to, for tmp to get the value of head would mean that it is getting the address of what head points to..

David Schwartz Over a year ago

That's right. tmp -> next = head; gives tmp -> next and head the same value. Thus tmp -> next now points to whatever head points to.

FrostyStraw Over a year ago

but then wouldn't head = tmp mean that head now points to whatever tmp is pointing to? And isn't tmp now pointing to what was formerly the first node on the linked list?

David Schwartz Over a year ago

@FrostyStraw Yes. That's exactly what you want to put a new node at the head of a singly-linked list. That node points to the former head. That node is the new head.

FrostyStraw Over a year ago

Ohh, I see. Because tmp is pointing at the new node that was created, so head now has the value of what tmp is pointing to, and is hence pointing to the new node. I thought it was saying that head was getting the value of what the new node was pointing at, and thus was pointing at the second node. I think I get it now though, thank you!

|

muhammad sameer · Accepted Answer · 2016-01-16 12:33:30Z

0

#include<iostream>
using namespace std;
struct Node
{
    int data;
    Node *link;
};
class LinkList
{
    Node *headptr;
public:
    LinkList()
    {
        headptr=NULL;
    }

    void InsertatFirst(int val)
    {
        Node *newNode;
        newNode = new Node;
        newNode ->link =NULL;
        newNode ->data = val;
        newNode ->link=headptr;
        headptr = newNode;
    }

    void Display()
    {
        Node *disNode;
        disNode = headptr;
        while(disNode !=NULL)
        {
            cout<<"Display Node Value is "<<disNode ->data<<endl<<endl;
            disNode =  disNode->link;
        }
    }

};
void main()
{
    LinkList lobj;
    lobj.InsertatFirst(45);
    lobj.InsertatFirst(2);
    lobj.InsertatFirst(1);
    lobj.InsertatFirst(0);
    lobj.InsertatFirst(-1);
    lobj.Display();
}

answered Jan 16, 2016 at 12:33

muhammad sameer

1

1 Comment

Bono Over a year ago

While this code may answer the question, it would be better to include some context, explaining how it works and when to use it. Code-only answers are not useful in the long run.

Wesley · Accepted Answer · 2016-10-16 09:53:37Z

0

void addToFront(int data) {
  Node* tmp = new Node(t); //assume your Node constructor can handle this
  if(numElements != 0) {   //should check weather empty or not
    x->next = head;        //link them first
    head = x;             //and now make the head point to the new head
  } else {      //if empty you should also set the tail pointer
    head = x;
    tail = x;
  }
  numElements++;
}

If there is a head, the new node "next" will be point to the current head which is pointing to another node. and then head=x, the pointer called head is now set to point to the new node rather than the previous one

edited Oct 16, 2016 at 9:53

answered Oct 16, 2016 at 9:45

Wesley

12 bronze badges

Collectives™ on Stack Overflow

Adding node to the front of a linked list

4 Answers 4

1 Comment

8 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

8 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related