Creating a linked list without declaring node as a pointer

Question

I've been searching around for a good while now on google and a few text books and I can't seem to understand why it is, when building a linked list, that the nodes need to be pointers.

Eg. If i have a node defined as:

typedef struct Node{
    int value;
    struct Node *next;
} Node;

why is it that in order to create a linked list, I would say:

Node *a = malloc(sizeof(Node));
Node *b = malloc(sizeof(Node));
a->value = 1;
b->value = 2;

a->next = b;
b->next = NULL;

rather than:

Node a, b;
a.value = 1;
b.value = 2;

a.next = &b;
b.next = NULL;

To my understanding, the list will still be able to be referenced and traversed as normal, the only difference is the use of the dot, ampersand syntax rather than the arrow?

Your Node *a, *b snippet is invalild. You're declaring pointer variables, without having them point to valid memory. The pointers almost certainly won't point to valid Node objects — Elias Van Ootegem
– Elias Van Ootegem, Commented Oct 30, 2016 at 16:34
With your second example, think about how you would add hundreds of new nodes to your list. Using pointers, you can keep using malloc to add new nodes inside a loop. Without pointers, then you're need to allocate storage some other way, somewhat defeating the benefit of using a linked list. — Neil
– Neil, Commented Oct 30, 2016 at 18:04

harper · Accepted Answer · 2016-10-30 17:06:06Z

4

You can create the list in a way that you mentioned.

But you must care for the life time of the list members. If your

Node a, b;

are in scope of a function then these are lost after the return of that function.

When you use pointers then you usually use the heap and the instances live until they are deleted.

edited Oct 30, 2016 at 17:06

answered Oct 30, 2016 at 16:35

harper

13.8k9 gold badges63 silver badges112 bronze badges

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

Comments

Green Lithium · Accepted Answer · 2016-10-30 16:35:16Z

0

Your first example will not work. You are declaring two Node pointers. However, since you do not initialize these to anything, it is illegal to deference them, since they don't point to anything. You must first use something like malloc to declare memory for them to point to, or assign them to a previously declared local variable. However, you must also remember to call free when you are done with the memory.

In the second example, you are declaring two Node variables, which you use to store instances of the Node. These will be allocated on the stack if they are local variables, and they will live for as long as they are in scope. They hold valid memory, and thus you can use them in the way you have demonstrated.

answered Oct 30, 2016 at 16:35

Green Lithium

6,0306 gold badges32 silver badges33 bronze badges

1 Comment

alphabetguy Over a year ago

My mistake. But under the assumption that i have allocated the required space for a and b, say if i have my two malloc statements underneath "Node *a, *b" for example.. what would be the impending differences at that point between that example of a linked list and the second one that i mentioned?

Collectives™ on Stack Overflow

Creating a linked list without declaring node as a pointer

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related