Trying to create an empty linked list in C

Question

I'm trying to create an empty linked list, which asks the user for the maximum number of terms that the list can hold. (I didn't add my code for that as its simply a printf). I then have to create a new function which asks the user to insert input into the previously created list.

My question is, how do I make the create_q() function return the empty list?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct node_t {
    int value;
    int priority;
    struct node_t *next;
}node;

typedef struct priority_linked_list {
    struct name *head;
    int current_size;
    int max_size;
}priority_list;

typedef node *Node;
typedef priority_list *List;

void create_q(int max_terms) {

    node *head = NULL;
    node *next = NULL;
    List *current_size = 0;
    List *max_size = max_terms;

}

Answer 1

In C, linked lists are usually implemented as a series of nodes stored on the heap that point to eachother. The heap is a persistent memory area that runs throughout the life-cycle of the program.

When you create a variable normally in a C function, and the function returns, the variable that you created is no longer accessible. However when you create something on the heap in a function, and the function is returned, the data you allocated on the heap is still there. However, you have no way of accessing it-- unless the function returns a pointer.

So what you would do for create_q() would be to create the linked list on the heap (using a function in stdlib.h called "malloc"), and then you would return a pointer to your first node, letting the main function know where on the heap to find the first node. Then that first node would have a pointer in it, telling the program where on the heap to find the second node, and so forth.

However, you're probably approaching linked lists the wrong way. Unless this is for some sort of homework project, you probably wouldn't want to create an empty linked list. One of the benefits of a linked list is that it's a dynamic structure in which you can easily insert new nodes. You could still have some variable keeping track of the maximum size you want the list to be, but you probably wouldn't want to actually create the nodes until you had to.

Just keep in mind what a linked list is. It's a set of nodes floating on the heap (in C) that each store some data, and contain a pointer to the next node floating on the heap. All you need, to access the linked list, is a pointer to the first node. To add a new node, you simply "walk" through the list till you reach the last node, and then create a new node and have the old-last node point to it.

Answer 2

Is this what you had in mind?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct node_t
{
    int value;
    int priority;

    struct node_t *next;
};

static int current_size;
static int max_size;
static struct node_t* head = NULL;

struct node_t* create_q(int);

struct node_t* create_q(int max_terms)
{
    int i; // loop counter/index

    current_size = max_terms;
    max_size = max_terms;

    if( NULL == (head = malloc(sizeof(struct node_t)*max_terms)))
    { // then, malloc failed
        perror("malloc failed for struct node_t list");
        exit( EXIT_FAILURE );
    }

    // implied else, malloc successful

    // set all fields to '0,0,Null'
    memset( head, 0x00, sizeof(struct node_t)*max_terms);

    // set all next links, except last link
    for(i=0;i<(max_terms-1);i++)
    {
        head[i].next = &head[i+1];
    }

    // set last link
    head[i].next = NULL;

    return( head );
} // end function: create_q

Answer 3

I suspect you are looking for something like the following for creating or initializing your priority linked list.

/*****
 * alloc_q - allocate memory for the priority linked list
 */
struct priority_linked_list *alloc_q(void)
{
    struct priority_linked_list *list;

    list = malloc(sizeof(*list));
    return list;
}

/******
 * init_q - initialize the priority linked list
 */
void init_q(struct priority_linked_list *list, int max_terms)
{
    list->head = NULL;
    list->current_size = 0;
    list->max_size = max_terms;
}

/******
 * create_q - allocate AND initialize the priority linked list
 */
struct priority_linked_list *create_q(int max_terms)
{
    struct priority_linked_list *list;

    list = alloc_q();
    if (list == NULL) {
        return NULL;
    }
    init_q(list, max_terms);
    return list;
}

Allocation of nodes and their addition/removal to/from the list would be handled separately.

There may be typos in the above (I have not tested it). However, it should be enough to get you on the path you want.

Hope it helps.