10

I could not grasp the reason we create pointers of nodes instead of node structures when we try to implement linked lists as here: 

typedef struct node {
    int val;
    struct node * next;
} node_t;

and

node_t * head = NULL;
head = malloc(sizeof(node_t));
if (head == NULL) {
    return 1;
}

head->val = 1;
head->next = NULL;

here, why do we declare nodes such as head as pointers of structures instead of direct structures>

Huzo
  • 1,652
  • 1
  • 21
  • 52
  • 6
    If `head`is already a structure holding all the data of a node, how do you represent an empty list? – Gerhardh Feb 16 '18 at 13:13
  • @Gerhardh maybe we can have `head` as a pointer and the rest as structure? – Huzo Feb 16 '18 at 13:17
  • 4
    What does it mean to have "the rest as structure"? Should `node_t` contain a field `node_t next`? That would not be linked but nested resulting in a recursively growing structure of infinite size. – Gerhardh Feb 16 '18 at 13:19
  • 1
    We use the head pointer to build a list conveniently via a function. We use it also to print, traverse, update, and delete nodes belonging to a list. – machine_1 Feb 16 '18 at 13:23
  • The mentioning of empty lists on this page is really sickening me. – machine_1 Feb 16 '18 at 13:26
  • 2
    Could you describe what you would use instead? An array of nodes or nesting structs? How would you do the memory allocation and linking part without pointers? – Gerhardh Feb 16 '18 at 13:30
  • 1
    @Gerhardh I had thought that we could just have all elements as node structures and link them together via pointers. But then thanks to the answers I realized that I had not considered empty linked lists. Everything is clear now. Thanks – Huzo Feb 16 '18 at 13:32
  • I would guess that dynamically linking an unknown number of nodes might be more difficult than empty lists. – Gerhardh Feb 16 '18 at 13:34
  • 3
    @Huzo If a `node_t` has a `node_t` as a member, then *that* `node_t` would *also* have a `node_t` as a member. Have you actually tried doing this? It just doesn't work. – Cubic Feb 16 '18 at 14:45
  • 4
    I saw this question and it felt oddly familiar... [Why do linked lists use pointers instead of storing nodes inside of nodes](https://stackoverflow.com/questions/29543780/why-do-linked-lists-use-pointers-instead-of-storing-nodes-inside-of-nodes) – Emil Laine Feb 16 '18 at 16:45
  • 3
    Just to respond the the text of the title as written, the nodes *are not* pointers. They are structures that contain a payload (something interesting) and a pointer. And that pointer is the "link" that holds the list together so it is what makes the list "linked", but it is generally the payload that you care about. The pointers are of interest only to the person writing the code to implement the list (which in class means you, of course), but no to the user of the abstract notion "here's a list of data". – dmckee --- ex-moderator kitten Feb 16 '18 at 17:04
  • 1
    This question is **not a duplicate**. It's asking why the list is manage using a pointer to the head node instead of using the head node directly. The question is not asking why the nodes themselves use pointers to the next nodes. – Vaelus Feb 16 '18 at 18:07
  • @Vaelus: Per our conversation below, I disagree, and stand by the duplicate as it is now. If you're still not convinced, refer to the OP's comment above: _"maybe we can have head as a pointer and the rest as structure?"_ There is plenty of evidence on this page that their intention is not what you claim it was. – Lightness Races in Orbit Feb 16 '18 at 18:16
  • @Huzo Are you asking why both `next` and `head` are pointers, or just why `head` is a pointer? – Vaelus Feb 16 '18 at 18:19
  • @LightnessRacesinOrbit I had a misunderstanding before that comment. However when I reread the answer and reply to that comment I realized my misunderstanding in your answer – Huzo Feb 16 '18 at 22:59
  • @Vaelus My question was: why is `head` a pointer? And not a structure like the other nodes that are linked with another via pointers. – Huzo Feb 17 '18 at 00:44

6 Answers6

12

Having head as a pointer allows for things like empty lists (head == NULL) or a simple way to delete elements at the front of the list, by moving the head pointer to another (e.g. second) element in the list. Having head as a structure, these operations would be impossible or at least much less efficient to implement.

user2736738
  • 30,591
  • 5
  • 42
  • 56
Mithrandir
  • 24,869
  • 6
  • 50
  • 66
  • I see, but can we then use the other nodes as structures? – Huzo Feb 16 '18 at 13:18
  • 1
    @Huzo Every element in the linked list is a structure, but the list is meant to be growing (or shrinking) as needs be. Only by using pointers you can let your list grow or shrink at run time. – Mithrandir Feb 16 '18 at 13:25
12

The primary reason is that the C language simply won't allow it - a struct type cannot contain an instance of itself. There are two reasons for this:

  1. The struct type is not complete until the closing }, and you cannot create an instance of an incomplete type;

  2. If a struct type could contain an instance of itself, then the instance would be infinitely large (struct foo contains an instance of struct foo, which contains an instance of struct foo, which contains an instance of struct foo, ad infinitum).

You can, however, create pointers to incomplete types (since the size of the pointer doesn't depend on the size of the pointed-to type). So if you want a struct type to contain a member that refers to another instance of the same type, it must be done through a pointer.

John Bode
  • 119,563
  • 19
  • 122
  • 198
  • Indeed, if you use unions (or are a bit free with type casting), you can have a list of many different types. As for instance events in X. – jamesqf Feb 16 '18 at 17:38
  • The question isn't asking why the node struct contains a pointer to the next node. It's asking why the whole list is manipulated using a pointer to the head instead of the head itself. – Vaelus Feb 16 '18 at 18:05
  • @Vaelus: it's actually asking both questions. Why do we use pointers within the `struct` type and why we use pointers to track the list. – John Bode Feb 16 '18 at 18:46
6

why do we declare nodes such as head as pointers of structures instead of direct structures

Declaring head as a pointer allows us to have an empty list, i.e. when head is NULL

Andriy Berestovskyy
  • 8,059
  • 3
  • 17
  • 33
  • Hmm, So the advantage is the ability to free space and manipulate memory? – Huzo Feb 16 '18 at 13:16
  • Is that the only advantage? – Huzo Feb 16 '18 at 13:16
  • 1
    @Huzo the advantage of empty list is to know the list is empty ;) Regarding the dynamic memory allocation, i.e. `malloc()` We allocate memory on demand, not all nodes at once. It is an advantage if you do care about the memory, but in terms of performance it is slower than a simple array of nodes. So it depends... – Andriy Berestovskyy Feb 16 '18 at 13:19
3

Because that's the whole point: a collection of nodes, that are linked like a chain. You can detach and re-attach nodes with ease and poise, because to do so you need only change pointer values. This would be impossible if your type were more like an array. If you want that, use an array.

Besides which, it is impossible for a type to contain an instance of itself. So a node contains a node, which contains a node, which contains a node, which contains a node, and so forth… how can that work?

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • The question isn't asking why the node struct has a pointer to next. – Vaelus Feb 16 '18 at 18:02
  • @Vaelus: It sure looks that way to me, and apparently to everybody else on this page. – Lightness Races in Orbit Feb 16 '18 at 18:03
  • The question is asking why the list is managed with a pointer to head instead of using the head node directly. Hence the accepted answer. – Vaelus Feb 16 '18 at 18:06
  • @Vaelus: I disagree. The title and most of the body says the OP means _all_ the nodes, not just head. The OP even _said this themselves_ in comments underneath the accepted answer; so the accepted answer doesn't really answer the question. – Lightness Races in Orbit Feb 16 '18 at 18:09
  • I think the question isn't worded very well, but considering that the accepted answer discusses *only* why the list is managed using a pointer, and how the OP has only responded to such answers, I think my interpretation of the question is what the OP meant. – Vaelus Feb 16 '18 at 18:12
  • @Vaelus: Then we'll have to agree to disagree. – Lightness Races in Orbit Feb 16 '18 at 18:15
1

As someone else has already said, by using pointers we have a convenient way of indicating an empty list or the end of the list by using a NULL pointer.

We could of course modify our nodes to have a flag indicating that it is "the end of the list" (EOL). However, another important reason it that is give the list the ability to easily grow (up to the amount amount of available memory) or shrink dynamically without having to reallocate memory to hold the entire list and copy it every time that it grows or shrinks. It also makes it easier to insert or remove an item.

Marker
  • 972
  • 6
  • 9
  • How does linking the nodes work with your approach? Do you mean an array of structs? – Gerhardh Feb 16 '18 at 13:28
  • Yes, if you don't use pointers, you would need an array of structs. It would either need to be a fixed capacity or every time is grows beyond its capacity, you would need to reallocate a larger array, copy the old array into it, and then delete the old array. Insertions and deletions also involve a lot of copying or somehow flagging the item as empty. I do sometimes used fixed lists in embedded development on simple processors where I know the maximum list size will never change. – Marker Feb 16 '18 at 13:33
1

It would not be a "linked" list if the nodes are not actually linked to each other. It could still be a list of some sort, but it would not be linked.

Compare to the word "link" or hyperlink on the internet. They are also pointers, because almost no site store actual contents of the linked sites.

mathreadler
  • 447
  • 5
  • 16