Pointers to other structures within a structure

Question

My lecturer has presented the following piece of code, with an insufficient explanation of what it represents.

typedef struct _s {
    int         value;
    struct _s   *next;
}  STACKITEM;

STACKITEM    *stack = NULL;

1. I understand what pointers and structures are. However, I do not know what it means to have a pointer to a structure, within a structure. Please clarify and elaborate on this concept.

2. I do not understand why the structure is declared typedef. This seems redundant for the following reasons:

A typical structure states as follows.

struct struct_format_name { 
members;
} individual_struct_object_name;

Therefore, we have declared an object to be a structure, and given this format of a structure the name _s. So what was the point of using typedef? Except for the typedef keyword, it is the same format that you would use to declare any structure.

3. I would like clarification on the difference between a pointer to a structure pointing to a structured format, as done above, and a pointer to a structure pointing to a particular structure.

I suspect that a pointer to a structure pointing to a structured format, as done above, can point to ANY structure of that format? However, a pointer to a structure pointing to a concrete structure can only point to that particular structure, rather than other structures of the same format?

Answer 1

I understand what pointers and structures are. However, I do not understand what it means to have a pointer to a structure, within a structure. Please clarify and elaborate on this concept.

This is a common C implementation of a data structure known as a singly linked list, where each element in the list explicitly points to the following element. In this case, each instance of a struct _s points to another instance of a struct _s, like so:

+---+---+         +---+---+        +---+---+
|   |   | ----->  |   |   | -----> |   |   |
+---+---+         +---+---+        +---+---+
                                     ^   ^
                                     |   |
                                     |   +---- next
                                     +-------- value

You can implement a stack using a linked list structure, which is what your instructor is doing. A "push" operation would dynamically create a new STACKITEM, save the integer value to it, and make that new STACKITEM the head of the list (a.k.a. the top of the stack). The stack pointer always points to the first element in the list (NULL if the list is empty).

stack: |||

push( &stack, 1 );

       +---+---+
stack: | 1 |   |---|||
       +---+---+

Repeated calls to push will add a new element at the head of the list:

push( &stack, 2 );

       +---+---+    +---+---+
stack: | 2 |   |--->| 1 |   |---|||
       +---+---+    +---+---+

push( &stack, 3 );

       +---+---+    +---+---+    +---+---+
stack: | 3 |   |--->| 2 |   |--->| 1 |   |---|||
       +---+---+    +---+---+    +---+---+

The code would look something like

void push( STACKITEM **stack, int value )
{
  STACKITEM *newItem = malloc( sizeof *newItem );
  if ( newItem )
  {
    newItem->value = value;
    newItem->next  = *stack;    // newItem now points to former top of stack
    *stack         = newItem;   // newItem is now the top of the stack
  }
}

A "pop" operation just works in reverse - it removes the first element of the list by setting the stack pointer to point to the next element and frees that element's memory:

void pop( STACKITEM **stack )
{
  STACKITEM *top = *stack;
  if ( top )
  {
    *stack = top->next;
    free( top );
  }
}

pop( &stack );

       +---+---+    +---+---+
stack: | 2 |   |--->| 1 |   |---|||
       +---+---+    +---+---+

pop( &stack );

       +---+---+
stack: | 1 |   |---|||
       +---+---+

pop( &stack );

stack: |||

I do not understand why the structure is declared typedef. This seems redundant for the following reasons:

typedef serves two basic purposes:

1. Simplify complex type names
2. Abstract away implementation details

In this case, your instructor is aiming for 2 - abstracting away the struct-ness of the stack item type. Unfortunately, if you as the user of the type have to be aware of implementation details, then this doesn't serve much of a purpose.

NOTE: Your instructor should not be using a leading underscore in the tag name; identifiers with leading underscores are reserved for use by the implementation.

Answer 2

A pointer within a structure is no different from a pointer outside of a structure, and a pointer to a structure type can point to any object of that type.

There is no way to define a type that can only point to a specific object.

Your code and your lecturer's code don't accomplish the same thing, so there's no redundancy.
You're defining both a type and an object; they're defining a type and a different name for that type.
(It sounds a little bit like you're confusing types with objects.)

Their typedef isn't strictly necessary but is a very common way to avoid having to type struct whenever you use a structure type.

And your variant is very atypical.
Types are most often defined globally while variables are declared as locally as possible.

Answer 3

This is called a linked list. The pointer next is what allows you to browse the list by having each element point to the next one, and having the last one have next point to NULL, so you know you're at the end. See https://en.wikipedia.org/wiki/Linked_list You're not actually storing a structure, you're storing a pointer to the next element, think of it as an array, but where instead of the elements being aligned, each of them points to the next element using its address instead.

As for the next pointer the reason it is declared with the struct keyword is that the STACKITEM type does not exist yet (it's defined after the structure's definition).

Answer 4

A typical structure is declared as follows.

Only if you never want to create one ever again in the future. The syntax you are questioning is by far the typical way to declare a struct.

The typedef allows you to refer to it by the shorter name of struct_format_name instead of struct struct_format_name.