C - Linked List - how to assign and go through the list

Question

i'm having trouble with building a linked list using two structs node - contains data and pointer to the next, and list which contains pointer to the head of the list.

i managed to implement it with only the node struct.

i have initialized a struct of a list in the main function than allocated memory for a list struct using malloc than i allocated memory for the head which is a pointer to the first node

sent it to another function where there the input,allocating,assigning goes, but im having hard time to understand how to go through the list without changing the pointer to the head.

and after im done with the nodes and assignment how to get the head pointer to point back at the start of the list.

should i work with copies? (node *temp) ??

thanks everyone!

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

typedef struct node
{
    int data;
    struct node *next;
}node;

typedef struct list
{
    struct node *head;
}list;

void main()
{
    list *list_a;
    list_a = (list*)malloc(sizeof(list));
    list_a->head = (node*)malloc(sizeof(node));

    assignment(list_a);
}
void assignment(list *list_a)
{
    int data;

    printf("please enter the numbers:\n(to stop enter ""-1"")\n\n");
    scanf("%d", &data);

    while (data != -1)
    {
        list_a->head->data = data;
        list_a->head->next = (node*)malloc(sizeof(node));
        list_a->head = list_a->head->next;

        printf("enter a number:\n");
        scanf("%d", &data);
    }
}

Answer 1

There are a number of ways to do a linked list, from the mind-numbingly simple add-at-head (which ends up with a list in reverse order) to a fairly standard add-at-tail where you iterate over your nodes to find the end node, and add the new node there. In all cases, it is just a matter of handling your pointers correctly, allocating storage (for both your list parent struct, and each node) and validating all allocations, and then cleaning up after yourself and freeing the used memory when it is no longer needed.

Nested structures where you have a struct holding the head node (and hopefully other useful data to justify the nested approach) are quite common, but there is no need for a parent struct for the list itself. The list address is simply the address of the first node.

When learning lists, it really helps to break the tasks of managing the list down into simple separate functions. This allows you to concentrate (a bit easier) on each list operation singularly. For example, with your list, you will need to:

1. create/allocate for each node, initialize next pointer NULL and set the data value;
2. create/allocate for your list, allocating for head and initializing any additional information contained in the list struct;
3. add nodes to your list, creating the list if needed and adding the node setting data to the proper value and updating any list information needed;
4. get data out of your list; and
5. finally freeing the memory for your nodes and your list when it is no longer needed.

In your case, and continuing from my comment to your question, you can declare your structure and typedefs similar to the following:

typedef struct node {
    int data;
    struct node *next;
} node_t;

typedef struct list {
    struct node *head;
    size_t n;           /* at least make parent hold list size */
} list_t;

Here we a simply added a counter to track the number of nodes in your list as an additional, useful, piece of data to justify the outer stuct. It gives you the node count without having to iterate over the list each time to obtain in (it's just a small efficiency improvement if you need that data). You have the number of nodes in your list with a simple list->n.

Following our list outline, you need a way to create nodes for your list. Whether it is the first node, or last node, you don't care. When you need a node, your create_node function should handle the allocation/validation and initialization. Nothing fancy is needed, e.g.

/** function to create node and set data value to data.
 *  returns new node on success, NULL otherwise.
 */
node_t *create_node (int data)
{
    node_t *newnode = malloc (sizeof *newnode);   /* allocate */

    if (newnode == NULL) {  /* validate/handle error */
        perror ("create_node() malloc-newnode");
        return NULL;
    }

    newnode->data = data;   /* initialize members */
    newnode->next = NULL;

    return newnode;         /* return pointer to new node */
}

Your create_list function simply needs to allocate for the list struct (and I also have it allocate the first node and initialize the values and pointer 0/NULL). You can have it do whatever you like, e.g. add another parameter passing data for the fist node, etc. I simply have it create the list and first node.

/** function to create list and allocates/initilizes head, set list->n = 0.
 *  returns new list on success, NULL otherwise.
 */
list_t *create_list (void)
{
    node_t *head = NULL;
    list_t *list = malloc (sizeof *list);   /* allocate list */

    if (!list) {    /* validate/handle error */
        perror ("create_list() malloc-list");
        return NULL;
    }

    head = create_node (0);     /* create the first node */

    if (!head)                  /* validate/handle error */
        return NULL;

    list->head = head;          /* initialize list values */
    list->n = 0;

    return list;                /* return list */
}

Your add_node function can be fairly simple, but for purposes here, rather than just stopping if the list is not yet allocated, we will have the add_node function create the list if it doesn't exists and then add the node. This choice has important implications. Since I will handle the case where the list doesn't exist, that means the list address may change within the function. To handle this potential, I must pass the address-of the list as a parameter (e.g. list_t **list instead of simply list_t *list). By having the actual address of the pointer, I can change where the original pointer points and that change will be visible back in the calling function (rather changing where a copy of the pointer points which would not be seen back in the caller).

The function needs to handle two cases (1) "am I the first node?" and (2) "if I'm not the first node, then iterate to end and add there". You can do something similar to:

/** add node to list, create list if list NULL, set node->data to data.
 *  return new node on success, NULL otherwise.
 */
node_t *add_node (list_t **list, int data)
{
    node_t *node;

    if (!*list) {   /* handle list doesn't exist */
        *list = create_list();
        if (!*list)
            return NULL;

        node = (*list)->head;   /* (..)-> required by operator precedence */
        node->data = data;
    }
    else {  /* list already exists */
        node = (*list)->head;               /* set node to list->head */

        /* iterate over nodes to find last and add node at end */
        while (node->next)
            node = node->next;

        node->next = create_node (data);    /* allocate next node */
        node = node->next;                  /* change to new node */
    }

    (*list)->n++;   /* increment number of nodes in list */

    return node;    /* return node */
}

By doing it this way, I can simply declare the pointer in main() and initialize it NULL and then simply call add_node(&list, x) in main() letting the list functions handle the pointers and allocation.

Your additional list functions are just functions that iterate over each node in the list doing something with the information like printing the list or freeing all the nodes in the list. (pay careful attention to how the node-to-be-freed (e.g. the victim) is handled in the free_list function)

/** print the value of each node in list */
void prn_list (const list_t *list)
{
    /* iterate over list printing data value */
    for (node_t *node = list->head; node; node = node->next)
        printf (" %d", node->data);
    putchar ('\n');     /* tidy up with newline */
}

/** free all nodes in list and free list */
void free_list (list_t *list)
{
    node_t *node = list->head;      /* set node to head */

    while (node) {                  /* iterate over each nod */
        node_t *victim = node;      /* setting victim to free */
        node = node->next;          /* change to next node */
        free (victim);              /* free victim */
    }

    free (list);    /* free list */
}

(note the two different examples of iterating over the nodes using either a for or while loop)

Putting all the pieces together, adding 25 nodes, and printing them out before freeing all memory associated with the list, you could do something like the following:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#if ! defined (_WIN32) && ! defined (_WIN64)
 #include <stdlib.h>    /* Linux has malloc/free in the stdlib header */
#endif

typedef struct node {
    int data;
    struct node *next;
} node_t;

typedef struct list {
    struct node *head;
    size_t n;           /* at least make parent hold list size */
} list_t;

/** function to create node and set data value to data.
 *  returns new node on success, NULL otherwise.
 */
node_t *create_node (int data)
{
    node_t *newnode = malloc (sizeof *newnode);   /* allocate */

    if (newnode == NULL) {  /* validate/handle error */
        perror ("create_node() malloc-newnode");
        return NULL;
    }

    newnode->data = data;   /* initialize members */
    newnode->next = NULL;

    return newnode;         /* return pointer to new node */
}

/** function to create list and allocates/initilizes head, set list->n = 0.
 *  returns new list on success, NULL otherwise.
 */
list_t *create_list (void)
{
    node_t *head = NULL;
    list_t *list = malloc (sizeof *list);   /* allocate list */

    if (!list) {    /* validate/handle error */
        perror ("create_list() malloc-list");
        return NULL;
    }

    head = create_node (0);     /* create the first node */

    if (!head)                  /* validate/handle error */
        return NULL;

    list->head = head;          /* initialize list values */
    list->n = 0;

    return list;                /* return list */
}

/** add node to list, create list if list NULL, set node->data to data.
 *  return new node on success, NULL otherwise.
 */
node_t *add_node (list_t **list, int data)
{
    node_t *node;

    if (!*list) {   /* handle list doesn't exist */
        *list = create_list();
        if (!*list)
            return NULL;

        node = (*list)->head;   /* (..)-> required by operator precedence */
        node->data = data;
    }
    else {  /* list already exists */
        node = (*list)->head;               /* set node to list->head */

        /* iterate over nodes to find last and add node at end */
        while (node->next)
            node = node->next;

        node->next = create_node (data);    /* allocate next node */
        node = node->next;                  /* change to new node */
    }

    (*list)->n++;   /* increment number of nodes in list */

    return node;    /* return node */
}

/** print the value of each node in list */
void prn_list (const list_t *list)
{
    /* iterate over list printing data value */
    for (node_t *node = list->head; node; node = node->next)
        printf (" %d", node->data);
    putchar ('\n');     /* tidy up with newline */
}

/** free all nodes in list and free list */
void free_list (list_t *list)
{
    node_t *node = list->head;      /* set node to head */

    while (node) {                  /* iterate over each nod */
        node_t *victim = node;      /* setting victim to free */
        node = node->next;          /* change to next node */
        free (victim);              /* free victim */
    }

    free (list);    /* free list */
}

int main (void)
{
    list_t *list = NULL;    /* just declare list and set pointer NULL */

    for (int i = 0; i < 25; i++)                /* add 25 nodes to list */
        if (add_node (&list, i + 1) == NULL)    /* validate each addition */
            break;

    /* print list content, beginning with number of nodes in list */
    printf ("list contains: %lu nodes\n\n", list->n);
    prn_list (list);    /* followed by each node value */
    free_list (list);   /* and then delete list */

    return 0;
}

Example Use/Output

$ /bin/llsingle_w_parent
list contains: 25 nodes

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Memory Use/Error Check

In any code you write that dynamically allocates memory, you have 2 responsibilities regarding any block of memory allocated: (1) always preserve a pointer to the starting address for the block of memory so, (2) it can be freed when it is no longer needed.

It is imperative that you use a memory error checking program to insure you do not attempt to access memory or write beyond/outside the bounds of your allocated block, attempt to read or base a conditional jump on an uninitialized value, and finally, to confirm that you free all the memory you have allocated.

For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.

$ valgrind ./bin/llsingle_w_parent
==14749== Memcheck, a memory error detector
==14749== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==14749== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==14749== Command: ./bin/llsingle_w_parent
==14749==
list contains: 25 nodes

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
==14749==
==14749== HEAP SUMMARY:
==14749==     in use at exit: 0 bytes in 0 blocks
==14749==   total heap usage: 26 allocs, 26 frees, 416 bytes allocated
==14749==
==14749== All heap blocks were freed -- no leaks are possible
==14749==
==14749== For counts of detected and suppressed errors, rerun with: -v
==14749== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Always confirm that you have freed all memory you have allocated and that there are no memory errors.

Linked-lists come in all different implementation. You should be aware of a couple of basic distinctions. You have lists that use dummy-node (e.g. dummy head and tail node that do not hold data, but just point to the first/last node in the list). You have circular-linked-lists where the last node points back to the first node (this allows iterating from any node in the list, to any node in the list in a circular fashion across the start and end). So when you look at "linked-list" code, understand that there can be many ways that lists are implemented, all have strengths and weaknesses, so you just have to match your list for the job.

Finally, as specified in the comment, your declaration void main() is incorrect and is an ancient throwback to the early days of windows (like DOS 3.3 and Windows 3.1, Trumpet WinSock, and the Borland Turbo C compiler days) The proper declarations for main are int main (void) and int main (int argc, char **argv) (which you will see written with the equivalent char *argv[]). note: main is a function of type int and it returns a value. See: C11 Standard §5.1.2.2.1 Program startup p1 (draft n1570). See also: See What should main() return in C and C++?

(note: there are some embedded systems that continue to use void main(), but those are the exceptions, not the rule, and are non-compliant with the C-Standard)

Look things over and let me know if you have further questions.

Answer 2

but im having hard time to understand how to go through the list without changing the pointer to the head

Head itself would be the pointer to the first node.

and after im done with the nodes and assignment how to get the head pointer to point back at the start of the list.

You make the new node point to the first node & then shift the pointer pointing to the first node i.e. head to point to the newly added node.

• IMPORTANT - You are missing stdlib.h without which malloc can't be used.

Here is a crude version (just for understanding):

 while(/*IF YOU WANT TO ADD NODES?*/)
 {
       if(head == NULL)
       {
           head = malloc((sizeof(struct node));
           head->data = //USER INPUT;
           head->next=NULL;
       }
       else
       {
            temp = malloc(sizeof(struct node));
            temp->data = //USER INPUT;
            temp->next = head;
            head=temp;
       }
 }

This entire this can be seen in several steps:

First: head->[data||NULL]

Second: temp->[data||Pointer pointing to 1st node]->(head)[data||NULL]

MOVING HEAD TO MAKE IT POINT TO THE NEW 1st NODE

Third: head->[data||Pointer pointing to Previous 1st node]->[data||NULL]

Isn't it cowardly behaviour to downvote without a valid reason?