Ninalol - 6 months ago 32

C Question

I am having big problems understanding linked lists and I would be very thankful if someone could explain me the following.

`Element_t *pushfront(Element_t *list)`

{

if(list==0)

return allocate();

list->prev=allocate();

list->prev->next=list;

list=list->prev;

return list;

}

What here means

`list->prev->next=list`

What means this:

`f->next->prev=f->prev`

I know that this is just a part from program code, but I hope someone can give me general meaning of these as simpliest as can?

Answer

The list has nodes that have references to the previous node and to the next node in the list.

The function gets the first node of the list. So this first node does not have a previous node.

In this statement

```
list->prev=allocate();
```

a previous node is created because as it follows from the function name it push a new node at the beginning of the list.

In this statement

```
list->prev->next=list;
```

expression `list->prev`

yields the address of the new created node. This created node shall point to the current first node of the list. Thus its data member `next`

shall contain the address of the node `list`

.

And this statement

```
list->prev->next=list;
```

does this.

It can be imagined simpler if to introduce an intermediate variable.

For example

```
Element_t *new_node = allocate();
list->prev = new_node; // list->prev=allocate();
new_node->next = list; //list->prev->next=list;
list = new_node; //list=list->prev;
return list;
```

As for this question

What means this: f->next->prev=f->prev?

then it looks like that the node `f`

is removed from the list. Now its next node (`f->next`

) will not point to `f`

but will point to the preceding node of `f`

.

Again it will be more clear if to introduce intermediate variables.

```
Element_t *previous_node_of_f = f->prev;
Element_t *next_node_of_f = f->next;
next_node_of_f->prev = previous_node_of_f; // f->next->prev=f->prev
```

If to add also a statement like this

```
previous_node_of_f->next = next_node_of_f;
```

then the node `f`

will be fully removed from the list.

```
--------------------------------------------------------
| prev ^
| |
---------------------- ---------------------- ----------------------
| previous_node_of_f | | f | | next_node_of_f |
---------------------- ---------------------- ----------------------
| ^
| next |
-------------------------------------------------------
```