Re: simple question on linked list insert

From: Karl Heinz Buchegger (kbuchegg_at_gascad.at)
Date: 01/28/04 

Date: Wed, 28 Jan 2004 11:52:38 +0100

Digital Puer wrote:
>
> Can someone explain why the linked list insertion code (emphasised below)
> does not work? It is a function to create a linked list and insert
> two elements. The code in question creates the head fine, but
> subsequent nodes are not inserted.

When working with dynamic data structures, your best friend is
a piece of paper, a pencil and an eraser.
To figure out whar a piece of code does, you play computer and
execute everything on paper what your program tells you to do.

>
> /* this function creates a linked list with two integers */
> void insert(Node **head, int a, int b)
> {
>

   head a b
   +------+ +------+ +-------+
   | o--------+ | 10 | | 20 |
   +------+ | +------+ +-------+
                |
                |
                v main::head
                +---------+
                | |
                +---------+

> Node *ptr;

   head a b
   +------+ +------+ +-------+
   | o--------+ | 10 | | 20 |
   +------+ | +------+ +-------+
                |
                |
                v main::head
                +---------+
                | |
                +---------+

    ptr
    +------+
    | |
    +------+

> *head = make_node(a);

make_node creates a new node and returns a pointer to it.
This pointer is stored in *head. So look up head and dereference
it (follow the arrow). You end up in a rectangle where you originate
a new arrow that points to the new allocated node.

   head a b
   +------+ +------+ +-------+
   | o--------+ | 10 | | 20 |
   +------+ | +------+ +-------+
                |
                |
                v main::head
                +---------+ +------------+
                | o-------------------->| data: 10 |
                +---------+ | next: NULL |
                                         +------------+

    ptr
    +------+
    | |
    +------+

>
> /* this works fine */
> ptr = *head;

ptr should point to the same location as *head does. So look
up head, follow the arrow (derference it). You end up with a pointer.
Make ptr point to the same thing as this pointer does.

   head a b
   +------+ +------+ +-------+
   | o--------+ | 10 | | 20 |
   +------+ | +------+ +-------+
                |
                |
                v main::head
                +---------+ +------------+
                | o-------------------->| data: 10 |
                +---------+ +--->| next: NULL |
                                    | +------------+
                                    |
                                    |
    ptr |
    +------+ |
    | o---------------------------+
    +------+

> ptr->next = make_node(b);
>

create a new node (initialize it with b). make_node returns
its address. Store this address in ptr->next.

   ptr look up ptr
   ptr-> follow the arrow (derference it)
   ptr->next look up the next field.

In this field you should originate an arrow which points
to the new node:

   head a b
   +------+ +------+ +-------+
   | o--------+ | 10 | | 20 |
   +------+ | +------+ +-------+
                |
                |
                v main::head
                +---------+ +------------+
                | o-------------------->| data: 10 |
                +---------+ +--->| next: o--------+
                                    | +------------+ |
                                    | |
                                    | +-------------------+
    ptr | | +------------+
    +------+ | +--->| data: 20 |
    | o---------------------------+ | next: NULL |
    +------+ +------------+

> /*
> BUT THIS CODE DOESN'T -- WHY?????

Lets rool back to the situation when only the head node
came into existance. The situation was this:

   head a b
   +------+ +------+ +-------+
   | o--------+ | 10 | | 20 |
   +------+ | +------+ +-------+
                |
                |
                v main::head
                +---------+ +------------+
                | o-------------------->| data: 10 |
                +---------+ | next: NULL |
                                         +------------+

    ptr
    +------+
    | |
    +------+

> ptr = (*head)->next;

 *head look up head and derference it (follow the arraow)
 (*head)-> again follow the arrow
 (*head)->next look up the next field

 ptr = (*head)->next make ptr point to the same thing as the next field does
                        Hmm. The next field doesn't point anywhere. It contains
                        NULL. Thus ptr will also be NULL

   head a b
   +------+ +------+ +-------+
   | o--------+ | 10 | | 20 |
   +------+ | +------+ +-------+
                |
                |
                v main::head
                +---------+ +------------+
                | o-------------------->| data: 10 |
                +---------+ | next: NULL |
                                         +------------+

    ptr
    +------+
    | NULL |
    +------+

> ptr = make_node(b);

create a new node, initialize it with b. Make prt point to that node.

   head a b
   +------+ +------+ +-------+
   | o--------+ | 10 | | 20 |
   +------+ | +------+ +-------+
                |
                |
                v main::head
                +---------+ +------------+
                | o-------------------->| data: 10 |
                +---------+ | next: NULL |
                                         +------------+

    ptr
    +------+ +------------+
    | o------------------>| data: 20 |
    +------+ | next: NULL |
                           +------------+

and since this is the last thing that insert does, insert returns
to the caller and when doing so all local variables are destroyed:

                  main::head
                +---------+ +------------+
                | o-------------------->| data: 10 |
                +---------+ | next: NULL |
                                         +------------+

    
                           +------------+
                           | data: 20 |
                           | next: NULL |
                           +------------+ 

-- 
Karl Heinz Buchegger
kbuchegg@gascad.at

Relevant Pages