Starting linked lists

**jack jordan** · 11-07-2017

I am using a book to learn about linked lists. I am going through the exercises and I find this exercise:

Assume the following definitions:

Code:

struct gradeNode {
    char lastName[20];
    double grade;
    struct gradeNode *nextPtr;
};
 
typedef struct gradeNode GradeNode;
typedef struct GradeNode *GradeNodePtr;

Create a new node of type GradeNode that's pointed to by pointer newPtr of type GradeNodePtr. Assign the string "Jones" to member lastName and the value 91.5 to member grade (use strcpy). Provide any necessary declarations and statements.

The book suggests this as the code to do this:

Code:

GradeNodePtr newPtr;
newPtr = malloc(sizeof(GradeNode));
strcpy(newPtr->lastName, "Jones");
newPtr->grade = 91.5;
newPtr->nextPtr = NULL;

My IDE doesn't like this. It gives the error "pointer to incomplete class type not allowed." My belief is that this means that newPtr might have allocated space for a GradeNode, but it doesn't actually point to a GradeNode. There are no lastName or grade members for it to point to.

My question is then, how do I best preserve the spirit of the question and code it correctly?

*******************
EDIT:
It looks like I made a mistake in the definitions.

Code:

typedef struct GradeNode *GradeNodePtr;

is supposed to be

Code:

typedef GradeNode *GradeNodePtr;

So in typing this post out, I found what the problem was.

**ddutch** · 11-08-2017

keep it even smalller:

Code:

typedef struct gradeNode
{
    char lastName[20];
    double grade;
    struct GradeNode *nextPtr;
} GradeNode, *GradeNodePtr;

**rcgldr** · 11-08-2017

What Microsoft tends to do is add a underline suffix to the struct name when used for a typedef (the typedef name won't have the underscore). In some cases, it's better to have the next pointer as the first member of a node.

Code:

typedef struct GradeNode_ {
    struct GradeNode_ *nextPtr;
    char lastName[20];
    double grade;
}GradeNode, *GradeNodePtr;

**Hodor** · 11-08-2017

Originally Posted by rcgldr

What Microsoft tends to do is add a underline suffix to the struct name when used for a typedef (the typedef name won't have the underscore). In some cases, it's better to have the next pointer as the first member of a node.

a) Can you give an example of why adding a suffix to the struct tag is a good idea?
b) Yes, if you do casting magic and set things up so that strict aliasing isn't an issue then having the linkage as the first member of the struct can eliminate some special cases in dealing with adding/removing nodes from the list but it's probably beyond the scope of this thread

I'm more interested in the answer to question (a). That's just a Microsoft style thing I assume (maybe their compiler was [more] broken in an earlier version)

Edit: As for the typedefs being there in the first place that's a whole other discussion. What value do they add to this code? I would argue that it makes the code harder to read by obscuring that newPtr->nextPtr is a pointer (which would be obvious if it wasn't typdefed) requiring silly Hungarian Notation (adding the type to the variable name so the programmer knows what type it is because it's now hidden by the typedef... ugh) when if it was hidden the variable could simply be named "next" and all relevant information/documentation without ugly additions to the variable name.

**rcgldr** · 11-08-2017

Originally Posted by Hodor

a) Can you give an example of why adding a suffix to the struct tag is a good idea?

For C compilers (like Microsoft / Visual Studio) that don't treat | struct NAME ... | the same as | typedef struct ... NAME | . The suffix for the struct name allows it to be used within the struct definition for these compilers. Underscore suffix such as | typedef struct NAME_ ... NAME | is what I've seen used by Microsoft and at some companies I've worked with. However, sometimes it's the typedefs that get a suffix of _t, such as uint32_t or uint64_t.

first member of list node as the next pointer

Originally Posted by Hodor

b) Yes, if you do casting magic and set things up so that strict aliasing isn't an issue then having the linkage as the first member of the struct can eliminate some special cases in dealing with adding/removing nodes from the list but it's probably beyond the scope of this thread.

On some processors, if simply advancing to a list, it can be slightly faster to not have an offset involved for the next pointer. Some compilers also support an extension to C that allows the last member of a struct to be an unsized array, but that would only mean that the next pointer wouldn't be the last member of a struct. In the typical implementations I've seen for std::list for C++ STL, the internal nodes typically have next and previous pointers as the first two members of a node struct.

Originally Posted by Hodor

As for the typedefs being there in the first place that's a whole other discussion. What value do they add to this code? I would argue that it makes the code harder to read by obscuring that newPtr->nextPtr is a pointer (which would be obvious if it wasn't typdefed).

Again, in typical implementations I've seen for C++ std::list, the typedef _NodePtr is heavily used, and for C++ in general, the "this" pointer is also heavily used, and neither seem to be an issue for the programmers using them.

Originally Posted by Hodor

Hungarian Notation

It's still part of the Windows API, which is a fairly popular API. Defines and typedefs are upper case such as HANDLE, DWORD, ... , and prefixes are used for both typedefs like LPCTSTR, and variable names like lpFileName, dwFlagsAndAttributes, ... .

**Hodor** · 11-08-2017

Originally Posted by rcgldr

For C compilers (like Microsoft / Visual Studio) that don't treat | struct NAME ... | the same as | typedef struct ... NAME | . The suffix for the struct name allows it to be used within the struct definition for these compilers. Underscore suffix such as | typedef struct NAME_ ... NAME | is what I've seen used by Microsoft and at some companies I've worked with. However, sometimes it's the typedefs that get a suffix of _t, such as uint32_t or uint64_t.

Oh well, VS is broken then

Just so readers don't start using _t as a suffix it might be good to mention that the C Standard specifies that _t is reserved for the compiler
implementation (it will still work of course but it's worth keeping in mind and best avoided IMO).

Originally Posted by rcgldr

On some processors, if simply advancing to a list, it can be slightly faster to not have an offset involved for the next pointer. Some compilers also support an extension to C that allows the last member of a struct to be an unsized array, but that would only mean that the next pointer wouldn't be the last member of a struct. In the typical implementations I've seen for std::list for C++ STL, the internal nodes typically have next and previous pointers as the first two members of a node struct.

I always put it as the first anyway (I worded my original text in an ambiguous way I think). I put the linkage first (and not last, the only other reasonable location in my opinion) so that I can see immediately that the struct is a node for some kind of data structure. As long as the placement is consistent within the entire source it doesn't really matter at all though as long as it's either first or last and not in the middle for obvious readability reasons.

**ddutch** · 11-09-2017

There is no general consensus on the notation of typedeffed types.
As long as you do have a clear, efficient and consistent way ....

**jimblumberg** · 11-09-2017

Again, in typical implementations I've seen for C++ std::list, the typedef _NodePtr is heavily used,

Yes and do you realize that _UPPERCASELETTER is a reserved identifier in any scope? Which means that any programmer, other than the compiler implementation team, should never be using that variable name.

However, sometimes it's the typedefs that get a suffix of _t, such as uint32_t or uint64_t.

I wouldn't suggest using the "_t" suffix since it is a heavily used suffix in the standard and it is also reserved in the POSIX standard.

**rcgldr** · 11-09-2017

Originally Posted by jimblumberg

Yes and do you realize that _UPPERCASELETTER is a reserved identifier in any scope? Which means that any programmer, other than the compiler implementation team, should never be using that variable name.

Are you referring to leading underscore, which is reserved, or usign upper case for defines, enums, typedefs, ... , which is one style of Hungarian notation. My comment about _NodePtr was an example where a pointer type is heavily use, although the "this" pointer for C++ objects is even more heavily used, so I don't see an issue with using pointer types.

Originally Posted by jimblumberg

I wouldn't suggest using the "_t" suffix since it is a heavily used suffix in the standard and it is also reserved in the POSIX standard.

Again, I meant a standard's based usage for "_t", although the influence of that has lead some companies I've worked with to also use "_t" as part of their coding standards. Personally I prefer Windows style Hungarian, which I also used with some old SCO Xenix device drivers, but use whatever standard is being used on a project.

**jimblumberg** · 11-09-2017

Are you referring to leading underscore, which is reserved,

What I am referring to is that a leading underscore followed by either another underscore or any uppercase letter is always reserved for the implementation. Also beware of using anything starting with a leading underscore followed by any character in the global scope because those identifiers are also reserved for the implementation.

Again, I meant a standard's based usage for "_t", although the influence of that has lead some companies I've worked with to also use "_t" as part of their coding standards.

The highlighted portion, IMO, is a bad practice. IMO you should stay away from using this suffix not only because of it's extensive use in the C++ standard, but also because this suffix is reserved in the POSIX standard.

Also you should stay away from prefixes that start with "str" and are followed by another lower case letter, since that is also reserved for future string functions by some compilers.

There are quite a few other combinations to avoid as well. Here is a list of reserved sequences if you happen to be using the GCC compiler.

Personally I prefer Windows style Hungarian

Personally I detest Windows style Hungarian notation and normally won't even bother reading code that uses this style. From what I understand even Microsoft has indicated that this style is no longer recommended for new C++ or C# code. But you're quite welcome to use that style if you prefer, it won't really bother me since I don't do Windows.

**rcgldr** · 11-10-2017

Originally Posted by rcgldr

Again, I meant a standard's based usage for "_t", although the influence of that has lead some companies I've worked with to also use "_t" as part of their coding standards.

Originally Posted by jimblumberg

The highlighted portion, IMO, is a bad practice.

I didn't have much choice since those experiences were part of corporate standards.

Originally Posted by rcgldr

Personally I prefer Windows style Hungarian ...

Originally Posted by jimblumberg

Personally I detest Windows style Hungarian notation and normally won't even bother reading code that uses this style. From what I understand even Microsoft has indicated that this style is no longer recommended for new C++ or C# code. But you're quite welcome to use that style if you prefer, it won't really bother me since I don't do Windows.

I left out a part, I prefer using Hungarian when doing Windows programming to keep the style consistent. If primarily using C++ STL, which isn't Hungarian style, I follow that convention. Other than the Hungarian convention of using all upper case for stuff like typedefs, I don't see any consistency in typedef conventions in the programs I've seen here and at other forums.

**jimblumberg** · 11-10-2017

Other than the Hungarian convention of using all upper case for stuff like typedefs,

Normally in C all upper case is generally reserved for user defined macros (#define) rather than typedefs, as you already have seen there is no one preferred typedef style. I normally use a leading Uppercase letter for typedefs, but if I see a pattern in a particular program I usually will stick to that pattern.

I don't see any consistency in typedef conventions in the programs I've seen here and at other forums.

To be honest you don't really see a lot of consistency in anything in most forums because beginners are not usually consistent and unless there is something seriously wrong (like using reserved words or sequences) you don't always see someone correcting the OP.

I left out a part, I prefer using Hungarian when doing Windows programming to keep the style consistent.

Well if I were forced to use and program for Windows I would probably try to keep with the Windows style. However we'll probably never know because I don't ever intend to use or program for Windows. And if I look at most any Windows API program I get a headache in about a minute, so I tend to ignore Windows programming topics.

Thread: Starting linked lists

Thread Tools

Search Thread

Display

Starting linked lists

Similar Threads

Double Linked Dynamic Lists Vs Unrolled Linked Lists

Suggestions on how to traverse a linked list of linked lists as if it is a 2D-Vector?

Question about Linked lists of lists

question on linked lists(stack with linked lists)

Linked List of Linked lists Revisited.

Tags for this Thread