use of new operator while creating linked list

In the following program :

// illustration of linked list
#include <iostream>

using namespace std;

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

struct node* buildList();

int main() {

struct node* head = buildList();
cout << head->data;
}

struct node* buildList() {
    struct no开发者_开发问答de* head = NULL;
    struct node* second = NULL;
    struct node* third = NULL;

    head = new node;      // builds up a pointer structure on heap
    second = new node;
    third = new node;

    head->data = 1;
    head->next = second;

    head->data = 2;
    second->next = third;

    head->data = 3;
    third->next = NULL;

    return head;
}

i am unaware of the new operator's work here. What task they perform ? (I read that it allocates space on heap.But i don't know what does it mean) If i remove these statements there is no output and the program crashes. Why is that ?

---

The head, second, and third variables are pointers to nodes in memory. But, before you can use them, they must be pointing at a valid node in memory. This is where the new operator comes in. The heap is just an area of memory that has been allocated to your program to dynamically create objects (as opposed to the stack. See here for the difference).

---

* EDIT*

I just thought I'd add in before my answer:

The stack is, in simple terms, the place where your program is currently working and is somewhat temporary. What I mean by that is your main() function may call another function. That function will have its own scope (the area between the {}), its own local variables, space etc. It may in turn call another function. These functions keep being put "on the stack". Once a function returns, it will be taken off the stack and you will return to the point in the next-level-up function in which you started. It's as if you put a piece of paper on top of your current notebook, took some notes, then removed it to get back to your original page. "Stack Variables" are those that you create in normal ways within a function, and they die/destruct upon leaving scope.

Heap variables are those that are static/global, or those created using "new, malloc, etc." These variables are permanent and will persist/exist until you call delete on them explicitly. They will survive outside the scope in which they were created, and if you don't keep track of them their resources will be un-freeable and you will have a memory/resource leak.

Normal Post

The lines:

struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;

are all creating pointers the * after node states that it is a pointer to a node. These pointers are initialized to NULL, or 0. A pointer is just a memory address/location, it has no node object in it yet. So,

node* ptr = NULL;  //creates pointer to a node object, but no node itself.
node  obj;         //creates an actual node object on the stack.

Pointers can be used to point to a stack based object by taking its address with the & operator like this:

node obj;  //Real object.
node* ptr = &obj;  //ptr points to the "address of" obj.

In your case, a node pointer doesn't point to anything until you create it with "new". After that, the pointer points to "dynamically allocated" memory which will persist forever and ever until you call "delete" on it. The perk of this is the memory can persist outside the function in which it is created. So:

void myFunction()
{
    node obj;
}  //obj dies here.

void myOtherFunction()
{
    node* ptr = new obj;
} //the "node" created by new will survive after this.

I could go on, but you need to read a c++ book and understand this - pointers are a key aspect of the language you need to learn completely.

---

struct node* head = NULL; -> creates a pointer (points to null because of the assignment)

head = new node; -> allocates memory to the size of a node and points head to the start of that memory

so if ur pointer is NULL and u never tell it to point to a node (or anything) then any operations on that pointer or with that pointer will fail

---

new constructs a new object of that type.

In this case you're constructing a new node. However in some code you don't need to do that, instead you could simply use objects. i.e node head; head.data = 1; head.next = blah.

The reason new is used is to simply create a "new" object of that type. Usually used for a dynamic thing, in this case it looks like a linked list of some sort, so yes you would require new. But with every new, you need to delete the data when you're finished with otherwise you'll have a memory leak, in which case the larger the list gets, and you don't deconstruct things that are not required anymore, the more memory it's going to waste.

However, you should not need to use any of this code at all. Rather there is already a container in the standard library that offers this type of support, plus extras on the side.

#include <list> 
// and use
std::list<type> data;

you can easily insert and delete data in this list and it will handle the allocations and deallocations for you; which means you don't ever need to use new or delete and you can safely assume that the memory will be managed for you and there will be no memory leaks.