Ninalol Ninalol - 8 days ago 7
C Question

Understanding code in c (linked lists)

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                                             | 
       -------------------------------------------------------
Comments