C language and Queues/linked lists

Question

Can someone please explain the code below. I am new to C and trying to figure it out. why do we have queueNodeT at the end?

typedef char queueElementT;

typedef struct queueNodeTag {
  queueElementT element;
  struct queueNodeTag *next;
} queueNodeT;

That's for the `typedef`. It combines a `struct` declaration and a typedef name for the struct. — Bo Persson, Sep 27 '15 at 21:27
A `typedef` declaration declares an alias for a type. In this case `queueElementT` is declared to be an alias for `char`. Also, `queueNodeT` is declared to be an alias for `struct queueNodeTag`, and `struct queueNodeTag` is furthermore defined as a `struct` having the specified members. — John Bollinger, Sep 27 '15 at 21:43

score 0 · Answer 1 · edited May 23 '17 at 10:27

Let's break it down part by part.

This line simply tells you that queueElementT is defined as char here. Meaning you can write either queueElementT or char, both will work.

typedef char queueElementT;

Now here is the actual struct. It contain two variables, the element it is holding, in this case a char. It then also tells which element is next in the queue.

typedef struct queueNodeTag {
    queueElementT element;
    struct queueNodeTag *next;
} queueNodeT;

More of that can be read in this answer.

A demonstration:

int count (queueNodeTag q) {
    int i = 0;

    if (q == null) {
        return 0;
    }

    if (q.next == null) {
        return 1;
    }

    while (q.next != null) {
        q = q.next;
        i++;
    }

    return i;   
}

Three cases to handle.

q is null, the queue is empty. Return 0.
q.next is null, the queue only contains one element. Return 1.
Repeat until q.next is separated from null, increment i as we go. A better name for i might be elements or something similar.

This code is untested as I currently do not have a C compiler at hand. Someone who has one available can perhaps verify that no mistake has been done?

score 0 · Accepted Answer · answered Sep 27 '15 at 22:29

queueNodeT is the name of the type that the typedef statement is trying to create.

An alternate way to specify this is:

struct queueNodeTag {
    ...
};
typedef struct queueNodeTag queueNodeT;

In C (vs. C++), "struct queueNodeTag" just defines a struct named "queueNodeTag". In C++ [should you get there], this would also define a type named "queueNodeTag"

When creating a pointer variable to the struct, it's slightly shorter to use:

queueNodeT *my_pointer;

than:

struct queueNodeTag *my_pointer;

The trailing "T" is just a coding convention to denote that it's a type name and not a variable. You can use others. Mine is:

struct mystructname {
    ...
};
typedef struct mystructname mystructname_t;
typedef mystructname_t *mystructname_p;

Using mystructname_p, you can change:

struct mystructname *my_pointer;
mystructname_t *my_pointer;

into:

mystructname_p my_pointer;

The "_t" is fairly common. The "_p" thing is my convention, but, I believe other conventions define pointers to types as "p<Mytype>", such as "pMystructName". I much prefer using a suffix for this [and "snake case" notation rather than the "camel hump" notation in your example].

C language and Queues/linked lists

2 Answers2