Why Do Linked Lists Use Pointers Instead of Storing Nodes Inside of Nodes

Why do linked lists use pointers instead of storing nodes inside of nodes

It's not just better, it's the only possible way.

If you stored a Node object inside itself, what would sizeof(Node) be? It would be sizeof(int) + sizeof(Node), which would be equal to sizeof(int) + (sizeof(int) + sizeof(Node)), which would be equal to sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node))), etc. to infinity.

An object like that can't exist. It's impossible.

In a C Linked List why are the nodes also pointers?

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.

Why do so many example linked lists put the next pointer at the end of each node instead of at the beginning?

Because textbooks on datastructures are mostly meant to teach concepts to beginners. That kind of 'optimization' just adds a lot of noise to the beginner's ear. It is what you do with your knowledge after school, that separates you from the rest...

Using pointers to pointers to update linked lists in C

As you said, pp is a pointer to the pointer to the "current node in the position in the list" - this is sometimes called a "handler" in the literature. The name pp comes from "pointer to pointer".

* is the "dereference operator", specifically it means "the data at", so *pp means "the data at memory location pp," which in this case is the actual pointer to the current node.

When you use an assignment operator with a derefernce, you are saying set the data at memory location pp to new_node (that data happens to also be a pointer). Remember, new_node is a pointer to your new node's data. So when you run the line:

new_node->next = *pp;

you are setting the "next" entry in the data at new_node equal to the pointer to the "current" node. Then when you run the line:

*pp = new_node;

you are updating the pointer at location pp to point to the structured data in struct node format at new_node.

Sometimes when unwrapping all these pointers and dereferences in C, it helps me to make sure I understand the type of every expression and subexpression.

For example here are various expressions above, and their types, expressed as boolean operations in modern C using the typeof operator. Note that in a real program, at compile time these will be replaced with the value 1 ("truthy" in C) :)

typeof(new_node) == struct node *;
typeof(pp) == struct node **;
typeof(*pp) == struct node *;
typeof(*new_node) = struct node;

Note that since in C, the = operator causes memory to be copied to cause the left side of the expression to be equal to the right side in any future evaluations (commonly referred to as the lvalue and the rvalue of the expression). So in the parlance, After an = the lvalue could evaluate differently than before. The rvalue is used for calculating the new value of the lvalue, but itself remains unmodified after the assignment operation.

It is important to remember, anytime you use = you are blowing over any data in the lvalue. This is often confusing, as = is the ONLY operator in C that causes "side-effects" (Sometimes () is also considered an operator, of course function calls can also cause side-effects, as in this example using a pointer argument to the function and dereferencing it within the function body).

ALL other operators simply evaluate inside expressions (for example, *, &, + etc.), but when you use = it makes changes. For example, any given expression containing the lvalue or anything dependent on the lvalue might evaluate to a different value before and after an = operation. Because functions can have pointer arguments as in this example, function calls can also cause side effects.

You can also, more simply, think of * as an operator that "removes *'s" from types, and & as an operator that "adds *'s" to types - as above they are called the dereference and reference operator.

nodes in linked list with smart or raw pointers?

Now it depends which kind of Linked list you are talking about

if it is double linked list
unique pointer forward with a raw pointer backward works

shared pointer works but its too much (it will be using sword to cut vegetable)

Excellent video CppCon 2016: Herb Sutter “Leak-Freedom in C++

https://youtu.be/JfmTagWcqoE?t=23m6s

---

Related Topics