Linked list: Dereferencing to incomplete type

shalombi · #1 08-Jun-2007, 12:53

I have been experimenting with linked lists and was making a small program to sort of sum up all what I learned so far.

I'm getting a weird error, Dereferencing pointer to incomplete type from this line.

CPP / C++ / C Code:

head->next_item = head->next_item->next_item;

Head is a pointer to a struct which was declared so.

CPP / C++ / C Code:

typedef struct{
        int value;
        struct Linked_List *next_item;
        } Linked_List;

And initialized so.

CPP / C++ / C Code:

Linked_List *head;  //head pointer to list
  head = malloc(sizeof(Linked_List)); //malloc list
  head->next_item = NULL;

I'm also getting warnings for assignment from incompatible pointer type on lines like these.

CPP / C++ / C Code:

head = head->next_item;

From what I gathered it is because of the self reference in the structure and I shouldn't use typedef, is there a work around so that I can keep it as it is or what is the proper way to do this?

Thanks

Max

davekw7x · #2 08-Jun-2007, 12:59

Quote:

Originally Posted by shalombi

From what I gathered it is because of the self reference in the structure and I shouldn't use typedef, is there a work around so that I can keep it as it is or what is the proper way to do this?

You must use a tag for the struct. The tag can have the same name as the type (but I usually make it different, just for my own sensibilities).

CPP / C++ / C Code:

typedef struct Linked_List_{
        int value;
        struct Linked_List_ *next_item;
       } Linked_List;

In my example, Linked_List_ is the tag. Note that the pointer member inside the struct definition uses the tag.

It would be legal, and many people would prefer, to write

CPP / C++ / C Code:

typedef struct Linked_List {
        int value;
        struct Linked_List *next_item;
        } Linked_List;

Regards,

Dave

shalombi · #3 08-Jun-2007, 14:06

Thanks, I have fixed it, could you explain the behavior or point to an article about this?

I have tried to google this but didn't find anything other than a few articles saying do it this way with no explanation.

Max

davekw7x · #4 08-Jun-2007, 14:47

Quote:

Originally Posted by shalombi

Thanks, I have fixed it, could you explain the behavior or point to an article about this?

I have tried to google this but didn't find anything other than a few articles saying do it this way with no explanation.

Max

I learned the language by looking at examples (and narrative) in the book known as "K&R": The C Programming Language by Brian W. Kernighan and Dennis M. Richie. The first edition was published in 1978, and was just about the only (hard copy) book available on C at the time. The second edition was published in 1988, and is still in print.

The point is, that if you want to refer to a struct in some of the definitions of its members or in some later program declarations, then you must use a tag:

CPP / C++ / C Code:

struct point_ {
  int x;
  int y;
}

point_ is the tag.

Once this declaration has been made, then you can do things like this:

CPP / C++ / C Code:

struct point_ *head; /* a pointer to a struct like the one with tag point_ */

struct point_ myStruct; /* a struct like the one with tag point_ */

Etc.

If you don't want to type the "struct" every time, then you can do this:

CPP / C++ / C Code:

typedef struct point_ point;

Then you could write

CPP / C++ / C Code:

    point *head1;
    point myStruct1;

etc.

Now, as I previously mentioned, I like to give the tag a different name than the data type itself. This is not necessary, since the namespace for tags does not overlap the namespace for type definitions.

So everything that I have written so far could have been written;

CPP / C++ / C Code:

struct point { /* point is the tag */
  int x;
  int y;
}
.
.
.
struct point *head; /* a pointer to a struct like the one with tag point */

struct point myStruct; /* a struct like the one with tag point */
.
.
.
typedef struct point point;
point *head1;
point myStruct1;

If you want to have a pointer to the same kind of struct as a member of the struct, then you must use the tag in the definition of the struct:

CPP / C++ / C Code:

struct point_ {
    int x;
    int y;
    struct point_ *next;
};

If you want to put everything (the declaration and the typedef) in the same statement, then you can do it, but remember that you have to use the tag;

CPP / C++ / C Code:

typedef struct point_ {
    int x;
    int y;
    struct point_ *next; /* the struct tag is "point_" */
} point; /* the data type being declared is "point" */

Or

CPP / C++ / C Code:

typedef struct point {
    int x;
    int y;
    struct point *next; /* the struct tag is "point" */
} point; /* the data type being declared is "point" */

This is one of the "tricks of the trade" that many people don't try to understand; they just use something like the last thing that I wrote, and they treat it as an idiom. I believe that idioms are useful in the short term, but for the long haul, understanding trumps idioms every time. (That's just my opinion, of course. See footnote.)

An on-line reference: http://www-ccs.ucsd.edu/c/. I use this a lot to make sure I understand standard library function usage, but they have some other language features also.

So, click on declarations Then scroll down through "Visibility and Namespaces" on your way to "Tags" and "Type Definitions".

Regards,

Dave

Footnote:
"The opinions expressed here are not necessarily my own.
It's these dang voices in my head."
---davekw7x

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
game problem using linkedListType.h and random function	eureka360	C++ Forum	5	16-Feb-2007 10:48
[Include] Doubly-linked List	dsmith	C Programming Language	6	14-Apr-2006 13:12
linked list error message	Krandygrl00	C++ Forum	4	22-Jun-2005 14:13
search linked list	itsmecathys	C++ Forum	20	18-Apr-2005 01:34

Linked list: Dereferencing to incomplete type

Re: Linked list: Dereferencing to incomplete type

Re: Linked list: Dereferencing to incomplete type

Re: Linked list: Dereferencing to incomplete type