Why does "typdef struct { struct S *s; } S;" containing a pointer to same type compile?

In the first case, your struct has two equivalent names: struct Element (where Element is a struct tag) and Element (where Element is a typedef, an alias for an existing type).

In the second case, you just didn't define a tag for the struct. Normally that would be perfectly valid, but here you're referring to the nonexistent type struct Element in the declaration of the next member.

In that context, struct Element is an incomplete type. You can't declare objects of incomplete types, but you can declare pointers to them.

The declaration

typedef struct
{
    char value;
    struct Element *next;
} Element;

is legal, but it doesn't make next a pointer to the enclosing type. It makes it a pointer to some incomplete type, and you won't be able to refer to it until and unless you declare the full type.

Your second declaration is one of the plethora of things that don't make sense, but are still legal C.

You might consider just omitting the typedef and consistently referring to the type as struct Element. As lot of people like the convenience of having a one-word name for a structure type, but my own personal opinion is that there's not much benefit to that (unless the type is truly opaque, i.e., users of the type don't even know it's a struct). It's a matter of style.

Note that you need to refer to the type as struct Element, not Element, within the definition itself, since the typedef name Element isn't visible yet.

The fact that the struct tag and the typedef have the same name may seem confusing, but it's perfectly legititimate. Struct tags and typedefs are in separate namespaces (in the C sense, not the C++ sense); a struct tag can only appear immediately after the struct keyword.

Another alternative is to separate the typedef from the struct definition:

typedef struct Element Element;

struct Element {
    char value;
    Element *next;
};

(You can use an incomplete type name in a typedef.)

Your first variant is correct. Your second variant doesn't do what it appears to do.

In C, it's valid to forward-declare a struct type anywhere, even in the middle of declaring something else. (The scoping rules for such declarations-in-passing are confusing to the point where I'm not going to try to explain them -- suffice to say that you should avoid doing so.) That is why you don't get an error on the second construct. But what it means to the compiler is this:

struct _Anonymous_1 // name not actually accessible to code
{
    char value;
    struct Element *next;
};
typedef struct _Anonymous_1 Element;

After this code, the type "struct Element" is completely unrelated to the type "Element", and has not been fully declared. If you were to attempt to use that type, e.g. in

char cadr(Element *cons)
{
    return cons->next->value;
}

the compiler would not be happy:

test.c: In function ‘cadr’:
test.c:9:22: error: dereferencing pointer to incomplete type

An alternative to your first variant, that lets you use 'Element' instead of 'struct Element' everywhere, including inside the definition of the type, is

typedef struct Element Element;
struct Element
{
    char value;
    Element *next;
};

But in C there is no way to avoid having to manually make sure that "struct Element" is the same thing as "Element". If you don't want to have to deal with it, C++ is waiting for you over there ⟶