Adding a node to the middle of a singly linked list

Question

So I have code that I will show below

struct GraphicElement {
char* fileName;
struct GraphicElement* pNext;
    };
struct RasterGraphic {
struct GraphicElement* GraphicElements;
    };

AND ALSO

void InsertGraphicElement(struct RasterGraphic* pA)
{
int counter = 1;
int response = 0;
char tempString[256];
struct GraphicElement *newNode = malloc(sizeof(*newNode));
if (newNode == NULL) return;
newNode->fileName = malloc(256 * sizeof(char));
if (newNode->fileName == NULL) return;
newNode->pNext = NULL;


printf("Insert a GraphicElement in the RasterGraphic\nPlease enter the GraphicElement filename: ");
scanf("%s", newNode->fileName);


if (pA->GraphicElements == NULL)
{
    pA->GraphicElements = newNode;
    printf("This is the first GraphicElement in the list\n");
}
else
{

    struct GraphicElement *tempHead = pA->GraphicElements;
    while (tempHead->pNext != NULL)
    {
        tempHead = tempHead->pNext;
        counter++;
    }

    printf("There are %d GraphicElement(s) in the list. Please specify the position (<= %d) to insert at :", counter, counter);
    scanf("%d", &response);

    if (response == counter) {
        tempHead->pNext = newNode;
        return;

    }
}

return;
}

So as you can see I have a struct definition and then a function to insert a node into the list. I have it so that if its the first node it inserts and tells the user it is the first element in the list. Where I am having a problem is adding more elements. Right now the code has no problems adding new nodes in sequence. The user is asked where they would like to insert into the list. Right now as long as they choose to just add it in sequence it works perfectly. I've tried a lot of things i just cant figure out the logic to loop through and be able to add a node to the middle of the list so an example output would be like this..

List contains 1, 2, 3 the user adds a fourth element 4 but wants to add it to spot 1 which is where the 2 is sitting so the new updated list would look like 1, 4, 2, 3.

Answer 1

There is no magic to inserting anywhere within the linked list, the only real challenge is keeping your pointers straight when handling three conditions:

1. inserting the first node (or new first node);
2. inserting a node between at some position between the existing first and last node; and
3. inserting at the end of the list.

The first case, inserting the first (or new first) node simply requires allocating a new node and either inserting it is the first node in the list, or if the head node already exists, setting newnode->next = head; and head = newnode;

Inserting at the end is not much different, you just iterate to the last node and set last->next = newnode;

The case of inserting a node in between takes a bit more thought. The easiest way to keep your pointers straight is to pull out a pencil and paper and draw out your pointer diagram of your list and then break the list in two where you need to insert the new node, and figure out the steps required before you pickup the keyboard (it will go a lot easier that way)

Nothing fancy is needed, just a block diagram with your next (or your pNext) pointer connecting the nodes. A simple list will two nodes (A and B) will do, e.g.

       A           B
    +------+    +------+
    | node |    | node |
    | next |--> | next |-->NULL
    +------+    +------+

Then just break the list at the point where the new node will be inserted, e.g.

       A               B
    +------+    |   +------+
    | node |    /   | node |
    | next |--> \   | next |-->NULL
    +------+    /   +------+
                |
               new
            +------+
            | node |
            | next |-->
            +------+

That allows you to visualize the needed steps. Locate node A, set new->next = B;, set A->next = new; (note: you must stop at the node before the location you wish to insert the new node) The result will then be:

       A           new         B
    +------+    +------+    +------+
    | node |    | node |    | node |
    | next |--> | next |--> | next |-->NULL
    +------+    +------+    +------+

When an understanding of exactly what you need to do to handle the insertion, now pick up the keyboard and implement that logic.

Since you will have a single insert function to handle all three cases, as @WhozCraig commented, when handling list operations (or pointers in general where you may need to assign a new block of memory within a function changing the address of the pointer), it helps to pass the address of the pointer to your function (so that your function receives the pointer itself -- instead of a copy of the pointer).

Whether in your case you need to initially allocate for the list wrapper, or in a simple list where you may assign a new node as the first node in the list, passing the address of the pointer allows the change within the function without having to return and assign the return as the new address back in the calling function.

Adding a couple of typedefs gelement_t for your struct GraphicElement and rgraphic_t for struct RasterGraphic types, both to cut down on typing an remove some of the MixedCase style awkwardness, you can think about your InsertGraphicElement function in the following way.

First, your InsertGraphicElement function will either succeed or fail, so choose a meaningful return type that can indicate success or failure. When dealing with lists, returning a pointer to the newly inserted node is helpful and allows a return of NULL in the even of failure, e.g.

gelement_t *InsertGraphicElement (rgraphic_t **pA)

Since you are passing a pointer to pointer to your RasterGraphic struct, you can add data to the struct to make it a bit more useful as a wrapper to your actual list. Adding a node-counter is a convenient way to keep track of the number of nodes in a singly-linked list without having to iterate over the list each time, e.g.

typedef struct RasterGraphic {
    size_t nelements;
    gelement_t *GraphicElements;
} rgraphic_t;

Within your function you should validate that you have an allocated pointer, and if not, then allocate for the RasterGraphic struct, e.g.

    int position = 0;

    if (!*pA) {                         /* if list NULL - allocate new list */
        puts ("allocating new list.");
        *pA = malloc (sizeof **pA);
        if (!*pA) {                     /* validate every allocation */
            perror ("malloc-*list");
            exit (EXIT_FAILURE);
        }
        (*pA)->nelements = 0;           /* initialize values */
        (*pA)->GraphicElements = NULL;
    }

Next you can allocate and validate the new node to add either as the first node or at position, e.g.

    gelement_t *node = malloc (sizeof *node);   /* allocate node */
    if (!node) {    /* validate */
        perror ("malloc-node");
        exit (EXIT_FAILURE);
    }

Next collect your filename and position information and set node->fileName to a newly allocated block holding the filename entered by the user (a couple of helper-functions make this much easier), e.g.

    node->fileName = get_filename_stdin();  /* request filename */
    if (!node->fileName) {  /* validate */
        free (node);
        return NULL;
    }
    node->pNext = NULL; /* set next pointer NULL */

    position = get_int_stdin (*pA);    /* request position */

You are now at the point within the function where you handle the 3-cases identified at the beginning of the answer. If there is no (*pA)->GraphicElements node yet, you will add the first node (so you don't need to ask for position). If it isn't the first node, and the position requested is 0, you insert as a new first node. (both can be handled in a single case)

If the position requested is greater than zero, then you iterate to the node before the insertion point and insert as indicated with the diagram above and insert the node there.

One approach would be:

    gelement_t *p = (*pA)->GraphicElements;

    if (!p || position == 0) {  /* insert as new head */
        node->pNext = p;
        (*pA)->GraphicElements = node;
    }
    else {  /* insert at position (default end) */
        int n = 0;
        while (n < position - 1 && p->pNext) {  /* locate node before */
            p = p->pNext;
            n++;
        }
        node->pNext = p->pNext; /* set node->pNext to current pNext */
        p->pNext = node;        /* set current pNext to node */
    }

    (*pA)->nelements++; /* increment number of elements in list */

Which will handle your insertion based on the user input. All that remains is to:

    return node;    /* meaningful return to indicate success/failure */
}

(note: when you are comfortable with the list operation logic, it helps to break this function up into several functions that handle the operations individually, like create_list(), create_node() and add_node(). (where you create your RasterGraphic list, your GraphicElement node and finally add that node at a given position in the list -- that is left to you)

Putting it altogether and adding the helper functions, a short example would be:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>     /* for PATH_MAX */

typedef struct GraphicElement {
    char* fileName;
    struct GraphicElement* pNext;
} gelement_t;

typedef struct RasterGraphic {
    size_t nelements;
    gelement_t *GraphicElements;
} rgraphic_t;

char *get_filename_stdin (void)
{
    char filename[PATH_MAX] = "";
    char *newname = NULL;

    fputs ("enter filename : ", stdout);

    if (fgets (filename, PATH_MAX, stdin)) {
        size_t len = strlen (filename);
        if (len && filename[len-1] == '\n') {
            filename[--len] = 0;
            if (!len) {
                fputs ("error: filename empty.\n", stderr);
                return NULL;
            }
        }
        else if (len == PATH_MAX) {
            fputs ("error: filename exceeds PATH_MAX\n", stderr);
            return NULL;
        }
        newname = malloc (len + 1);
        if (!newname) {
            perror ("malloc-newname");
            exit (EXIT_FAILURE);
        }
        memcpy (newname, filename, len + 1);
    }

    return newname;
}

int get_int_stdin (rgraphic_t *list)
{
    char buf[PATH_MAX];
    int pos = 0;

    if (!list->nelements) {
        puts ("inserting as head.");
        return 0;
    }
    fputs ("index to insert: ", stdout);

    if (fgets (buf, PATH_MAX, stdin))
        if (sscanf (buf, "%d", &pos) != 1 || pos < 0 || 
            pos > (long)list->nelements)
            return list->nelements;

    return pos;
}

gelement_t *InsertGraphicElement (rgraphic_t **pA)
{
    int position = 0;

    if (!*pA) {                         /* if list NULL - allocate new list */
        puts ("allocating new list.");
        *pA = malloc (sizeof **pA);
        if (!*pA) {                     /* validate every allocation */
            perror ("malloc-*list");
            exit (EXIT_FAILURE);
        }
        (*pA)->nelements = 0;           /* initialize values */
        (*pA)->GraphicElements = NULL;
    }

    gelement_t *node = malloc (sizeof *node);   /* allocate node */
    if (!node) {    /* validate */
        perror ("malloc-node");
        exit (EXIT_FAILURE);
    }

    node->fileName = get_filename_stdin();  /* request filename */
    if (!node->fileName) {  /* validate */
        free (node);
        return NULL;
    }
    node->pNext = NULL; /* set next pointer NULL */

    position = get_int_stdin (*pA);     /* request position */

    gelement_t *p = (*pA)->GraphicElements;

    if (!p || position == 0) {  /* insert as new head */
        node->pNext = p;
        (*pA)->GraphicElements = node;
    }
    else {  /* insert at position (default end) */
        int n = 0;
        while (n < position - 1 && p->pNext) {  /* locate node before */
            p = p->pNext;
            n++;
        }
        node->pNext = p->pNext; /* set node->pNext to current pNext */
        p->pNext = node;        /* set current pNext to node */
    }

    (*pA)->nelements++; /* increment number of elements in list */

    return node;    /* meaningful return to indicate success/failure */
}

/* loop over list printing values */
void prn_list (rgraphic_t *list)
{
    size_t n = 0;
    gelement_t *node = list->GraphicElements;

    printf ("\n\n%zu nodes in list\n", list->nelements);

    for (; node; node = node->pNext)
        printf ("%2zu: %s\n", 1 + n++, node->fileName);    
}

/* loop over list freeing memory (pay attention to victim) */
void free_list (rgraphic_t *list)
{
    gelement_t *node = list->GraphicElements;

    while (node) {
        gelement_t *victim = node;
        node = node->pNext;
        free (victim->fileName);
        free (victim);
    }

    free (list);
}

int main (void) {

    rgraphic_t *list = NULL;
    puts ("\nNOTE: pressing [Enter] for index - inserts at end!\n"
        "      [Ctrl+d] at \"filename: \" prompt to end input.\n");

    while (InsertGraphicElement(&list)) {}  /* create list/insert nodes */

    prn_list (list);    /* print list */
    free_list (list);   /* free list */
}

Example Use/Output

$ ./bin/ll_single_insert_ptp

NOTE: pressing [Enter] for index - inserts at end!
      [Ctrl+d] at "filename: " prompt to end input.

allocating new list.
enter filename : one
inserting as head.
enter filename : four
index to insert: 1
enter filename : two
index to insert: 1
enter filename : three
index to insert: 2
enter filename : five
index to insert:
enter filename :

5 nodes in list
 1: one
 2: two
 3: three
 4: four
 5: five

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/ll_single_insert_ptp
==9747== Memcheck, a memory error detector
==9747== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==9747== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==9747== Command: ./bin/ll_single_insert_ptp
==9747==

NOTE: pressing [Enter] for index - inserts at end!
      [Ctrl+d] at "filename: " prompt to end input.

allocating new list.
enter filename : one
inserting as head.
enter filename : four
index to insert: 1
enter filename : two
index to insert: 1
enter filename : three
index to insert: 2
enter filename : five
index to insert:
enter filename :

5 nodes in list
 1: one
 2: two
 3: three
 4: four
 5: five
==9747==
==9747== HEAP SUMMARY:
==9747==     in use at exit: 0 bytes in 0 blocks
==9747==   total heap usage: 12 allocs, 12 frees, 136 bytes allocated
==9747==
==9747== All heap blocks were freed -- no leaks are possible
==9747==
==9747== For counts of detected and suppressed errors, rerun with: -v
==9747== 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.

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