I am doing some tests with simply linked lists and it fails me when inserting data, I have tried this:
struct nodo
{
int dato;
nodo *siguiente;
};
typedef nodo * lista;
void insertar(lista l, int dato)
{
nodo *n = new nodo;
n->siguiente = NULL;
n->dato = dato;
l->siguiente = n;
}
int main()
{
lista mi_lista;
insertar(mi_lista, 42);
std::cout << mi_lista->dato;
return 0;
}
I expected the program to display 42
, but instead it displays:
Segmentation fault
How do you insert data into simply linked lists?
1. Nodes are not lists.
I have seen this confusion on StackOverflow in Spanish several times, and I find it very curious that so many users make this mistake.
You have a data structure called
nodo
that stores a pointer to the next element and some data, the first thing you do with it is declare an alias saying that a pointer tonodo
is alista
. And that is as wrong as saying that a step is a ladder, honestly, do they seem the same to you?:Organizing data structures in this way and giving them names that do not adequately describe them is confusing and error prone as you have seen.
2. The alias hides the underlying type.
Normally when in C++ we define a variable of type pointer, we add the asterisk:
But we can hide the pointer in an alias:
Because of this use of the alias, it's not obvious that
lista
it's a pointer, and you end up declaring a pointer that doesn't point to anything:In the call to
insertar
the pointer is used (with the arrow operator->
) and since it doesn't point to anything you get the memory error (Segmentation fault
):Proposal.
Let's start by resolving the first point: lists and nodes are different things, so we'll create a list object:
If you notice, the
nodo
is now a sub-objectlista
that is in the private zone of said object, in this way we follow the principles of encapsulation . We've also added initializers to all members so they have controlled information at creation time; finally, using two pointers (one for the beginning of the list and one for the end) helps us save work when inserting data.The corrected implementation of
insertar
would look like this:With the intention of complementing the previous answer, I wanted to comment on several issues. First of all, that you are creating a C-style list from C++. For example, you use typedef. In C++ the compiler already considers the struct as a new data type. It is possible to create C code and compile it with a C++ compiler. The latter is more strongly typed and can give you warnings and errors that a C compiler will swallow and then malfunction the program. Also, they say in Thinking C++ that if you compile from C++ to C it has every chance of working. Continuing with the code, I think what you are trying to do is the following:
Also, your code has a problem, and that is that when it exits the insert function, n is destroyed, it goes out of scope because it only exists on the insert function stack, hence the Segmentation fault. When it disappears, where does l->next point? Do not lose sight of the assessment of Paula_plus_plus: you confuse the ladder and the step. From the point of view of the C++ code there are several ways to approach the problem. You seem to decide that the very class that defines the objects contained in the list is node, something like the following: a) Integration in the domain class itself b) use of Inheritance c) Null-type element container Although lists they are implemented in the STL as templates to be used as generic data. I will give you the base code of the first option, which is the one you seem to have chosen and,
With templates it would be like this:
This last one is the most reasonable model that I see, a list class (object) that contains the nodes. Nodes are another object. In the nodes I store the data and the operations corresponding to them. Since the list contains a pointer to nodes, I'll be able to iterate through them, insert, delete, and look at what they contain.
I hope I have been helpful.