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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

#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();
}