Take the 2-minute tour ×

suppose I have a structure.

struct node {
 string info;
 node link*;


what is the difference between

node k;
node b;

k.info = "string";
b.info = "string";
k.link = &b;


node *k;
node *b;
k = new node;
b = new node;    
k->info = "string";
b->info = "string";
k->link = b;

in terms of memory allocation? Are both examples correct and create a proper linked list? Added: In most books the second example is used, why is that? Is there a down side to using the first example?

share|improve this question
I find it easier working with -> notation. –  Cyrus Jun 14 '11 at 5:08

9 Answers 9

up vote 6 down vote accepted

Yes. both are technically correct.

In the first example, the memory is on the stack, in the second on the heap.

When the memory is on the stack, the "compiler" is in charge of freeing the memory (when variables go out of scope). Since your linked list can outlive the variables you explicitly created, this can cause all sorts of problems. For example, in the first example, if b goes out of scope, but k doesn't, then k will have a dangling pointer, which leads to undefined behavior (aka bad).

When the memory is on the heap, you have to manage the memory, which can cause problems if you forget to free it. This is harder then it sounds, considering exceptions. I suggest you use some form of a smart pointer. This is the most common and safest way to use a linked list.

share|improve this answer
-1. The standard doesn't talk about heap. Why don't you use automatic variable, and dynamic variable? –  Nawaz Jun 14 '11 at 5:09
I didn't talk about the standard, I talk about what happens 99.99% of the time. The standard is meant to be terse and precise, stackoverflow is meant to be instructional. –  Gilad Naor Jun 14 '11 at 5:10
@Gilad: What you talk about is not C++. Its implementation. Standard specifies the behavior the program, and implementation provides means to achieve that. So when you talk about C++, I think its better to use automatic variables and dynamic variables. –  Nawaz Jun 14 '11 at 5:16
@Nawaz, I agree, I don't talk about C++. I attempt to make an explanation that will make things clear for someone who asked this kind of question. For completeness sake, there are your comments, and the other answers. –  Gilad Naor Jun 14 '11 at 5:19
The standard doesn't talk about heap and stack, but it does specify the lifetime of automatic variables, and those lifetimes correspond to a stack protocol. The problem with the original post is not the use of the word "stack", it is the suggestion of using smart pointers. Complex data structures (any form of graph, including lists) are a place where smart pointers are not appropriate (usually); the graph is a clear owner of the nodes, and can delete them when appropriate. –  James Kanze Jun 14 '11 at 8:15

Both are correct and will create a proper linked list, but with the first example uses automatic allocation (global or on stack, within the scope, depends on the context), and the second - dynamic (for each new you have to call delete eventually).

When to use which depends on your program's logic, but usually linked lists are done using dynamic allocation (your second example), from my personal experience.

share|improve this answer
One of the reasons for using a linked list is that you don't know how many elements it's going to contain. That means dynamic allocation. –  James Kanze Jun 14 '11 at 8:15

Its not about a linked list.

  • The . is used to refer a structure component when the structure object is known
  • The -> is used to refer a structure component when the address of the structure object is known


node k, *m, *n;

m = &k;
n = new node;

k.info  = "Hello";   // k is a node type object so use directly . operator
m->info = "Hi";      // m is a pointer to an object to type node, so use -> operator
n->info = "Man";     // n is a pointer to an object to type node, so use -> operator
*(m).info = "This";  // *(m) refers to an object itself, we use . operator on it
*(n).info = "Is a test"; // *(n) refers to an object itself, we use . opeartor on it

All of there are valid syntax

  • When you do node k; inside a function it is generally allocated on the stack
  • When you do static node k; or declare node k; as global, it is allocated on the .data or similar section of the executable
  • When you use new to allocate some memory it is generally allocated from the heap

In the books the second example is used because, you do not know in advance how many nodes would be used, so it is not practical to allocate node as local variables with tons of variable definitions. Instead a pointer is used to allocate the memory temporarily, initialize them and then link it to an appropriate position of the list. In future the address references of the pointer links in the linked lists would let us access the nodes of the linked list in the order of the linking. In this way we have used node *k; k = new node; so we have an address to an object of type node therefore it is natural to use k->info; but you can use any syntax. You need to remember that on the left hand side of the -> should be an address to the type of class/structure of which the member you want to access, and on the left hand side of the . operator should be the object itself.

PS. You should free the memory by delete (which you allocated with new) after you have finished using.

share|improve this answer

The difference is in where the nodes are deleted.

In the first example, they are deleted automatically on return from the function they were declared in. You can't choose to delete them manually.

In the second example, you need to delete the nodes using the "delete" keyword. This means they are not deleted automatically, but gives you more flexibility in how long the nodes will hang around.

share|improve this answer

Both are technically correct.

Difference: In first, memory will be allocated on stack and you don't need to take care of freeing memory etc. Compiler will take care of everything. In second, memory would be allocated on heap and you need to take care of freeing the memory.

Why most books uses Second way: Although you need to take care of memory allocation (using new, malloc() etc) and memory freeing (delete, free()), there are several advantages:

  1. Many a times, you need to access the memory outside variable's scope (for ex: outside function where variable is defined). You can't do this if you don't allocate memory on heap. However, if you use pointers, you can do it very easily.

  2. You can do complex and smart operations using pointers. However, it makes your code difficult to understand.

I would suggest you to become habitual of second way since it is much powerful and smart way (comes at the price of code complexity).

share|improve this answer

As has already been pointed out, the difference in the two forms is that the second involves dynamic allocation, with manual management of the lifetime of the objects. Since the second is more complicated, one might ask why it is ever used. There are two reasons: the first (already mentionned) is that the lifetime of the object doesn't correspond to a lifetime directly managed by the compiler. The second is that you don't know the size (or the number of elements) in advance. The reason why most implementations of a list will dynamically allocate the nodes is because you generally don't know exactly how many nodes you'll need in advance. The whole point of a list is that it is a dynamic structure, with no fixed size.

share|improve this answer

This https://users.cs.jmu.edu/bernstdh/web/common/lectures/slides_cpp_dynamic-memory.php shall explain Dynamic memory allocation crisply

share|improve this answer

Yes. Both examples are correct. Pointers to objects can access functions within structs and classes through the use of the -> operator. The memory for the pointers will be allocated on the heap. The . operator is used by objects to access functions. The memory for these will be on the stack.

share|improve this answer

Using -> operator is a must-use when dealing with dynamically allocated objects. For example: Imagine that you have a class List, which has a method getRoot(), which returns Nodes. Nodes also have method getNext(), which gives you next node in list.

*List myList;

Let's suppose we know that myList is a List with 5 nodes. The list and the 5 nodes are located in heap (dynammically allocated). Now, we will want to acces the last node.

(*(*(*(*(*myList).geRoot() ).getNext()).getNext()).getNext()).getNext();

Those two sentences are equivalent, and will return the fifth and last node. For the sanity of programmer, use the first one.

share|improve this answer

Your Answer


