C++ what is the difference between using . or -> for linked list

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;

and

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?

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.

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.

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

Like

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.

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.

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).

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.

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

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.

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->getRoot()->getNext()->getNext()->getNext()->getRoot();
(*(*(*(*(*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.