Amit Singh Tomar Amit Singh Tomar - 1 month ago 16
C Question

Structure In C for linked list

Sorry for asking such a stupid question but I am really confused.

struct Amit
{
int a;
struct Amit *link;
}
*start;


Here both
*link
and
*start
are used to point to a node of a linked list, but what's the difference between these two and why can't we put
*start
inside the structure body?

Answer

The link is a member of the structure type. Every structure of type struct Amit has one.

The start is a variable of type 'pointer to struct Amit'. At any given time, there can be at most one variable called start visible.

You could put start inside the structure, but it would become a member of the structure (like link), and you would still need to declare variables of the structure type, or pointers to them.

The idea is that each structure on a list except the last contains a link pointer to the next structure on the list. Normally, the last structure on the list has a link pointer that is NULL (0). When searching down a list, you look at the values, and when you need the next item, you follow the link to it, stopping when the link is NULL.

struct Amit *item = start;
while (item != NULL && item->a != value_wanted)
    item = item->link;

It is possible to build a circular linked list instead, which has a different stop criterion.


Looking at the comments, and explaining a bit more...

One way to create a list is:

struct Amit root = { 0, NULL };
struct Amit *start = &root;

The variable root is a structure initialized with root.a == 0 and root.link == NULL (or, equivalently, root.link == 0). The pointer variable start points to (stores the address of) root. Given a new node:

struct Amit next = { 1, NULL };

we can add that to the front of the list which start points to:

next.link = start;
start = &next;

A more plausible way to create a list is by dynamically allocating nodes, including the root node. Consistency is crucial because you have to free the dynamically allocated nodes, and having some nodes dynamically allocated and others not is messy. (I'm assuming that function void *emalloc(size_t nbytes); is a cover function for malloc() that never returns a null pointer - so it does the error checking for me.)

// Create the empty list
start = emalloc(sizeof(*start));
start->a = 0;
start->link = NULL;

// Create a node
struct Amit *node = emalloc(sizeof(*node));
node->a = 42;
node->link = NULL:

// Add the node to the font of the list
node->link = start;
start = node;

You'd normally package this stuff up into functions which manage the allocation, initialization and linking of the nodes.

struct Amit *add_node(struct Amit *start, int value)
{
    struct Amit *node = emalloc(sizeof(*node));
    node->a = value;
    node->link = start;
    return start;
}

start = add_node(start, 42);
start = add_node(start, 30);
start = add_node(start, 18);

for (node = start; node->link != 0; node = node->link)
    printf("Node: %d (%p)\n", node->a, node->link);

Etc.