linked list doesn't add node properly

Question

I was learning linked list, where I was solving a question where you have to add a node in between nodes in a circular singly linked list. the problem with my code is that it doesn't add node at the correct position. I can't find what is wrong in my code. the function used for adding in between nodes is add_node_in_bet.

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

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

void addTOend(struct node **tail, int info)
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = info;
    if (*tail == NULL)
    {
        *tail = temp;
        (*tail)->next = (*tail);
    }
    else
    {
        temp->next = (*tail)->next;
        (*tail)->next = temp;
        *tail = temp;
    }
}

void add_node_in_bet(struct node **tail, int info, int pos)
{
    struct node *new = (struct node *)malloc(sizeof(struct node *));
    struct node *p = (*tail)->next;
    new->data = info;
    if (p == *tail)
    {
        new->next = (*tail)->next;
        (*tail)->next = new;
        (*tail) = new;
    }
    else if (p == (*tail)->next)
    {
        new->next = p;
        (*tail)->next= new;
    }
    else
    {
        while (pos > 2)
        {
            p = p->next;
            pos--;
        }
        new->next = p->next;
        p->next = new;
    }
}

void print(struct node **tail)
{
    struct node *p;
    p = (*tail)->next;
    do
    {
        printf("%d ", p->data);
        p = p->next;
    }
    while (p != (*tail)->next);
}

int main()
{
    struct node *tail = NULL;
    addTOend(&tail, 69);
    addTOend(&tail, 65);
    addTOend(&tail, 19);
    addTOend(&tail, 67);
    addTOend(&tail, 68);
    addTOend(&tail, 61);
    addTOend(&tail, 64);
    add_node_in_bet(&tail, 0, 2);
    print(&tail);
}

Output I got for my code.

0 69 65 19 67 68 61 64

I recommend you take some paper and a pencil, and try to draw your operations to visualize them. Use labeled boxes for nodes and other variables, and arrows for the pointers. Try to make sense of each operation on paper first, before implementing the steps in code. — Some programmer dude
– Some programmer dude, Commented Dec 18, 2023 at 21:14
As for debugging you basically do the same... While stepping through the code in your debugger draw all the operations you do. — Some programmer dude
– Some programmer dude, Commented Dec 18, 2023 at 21:15
As a hint about your problem, how big is a node structure? And how big is a pointer to a node structure? Tip: Use the variable itself when getting the size for how much to allocate, as in struct node *new = malloc(sizeof *new); — Some programmer dude
– Some programmer dude, Commented Dec 18, 2023 at 21:17
1) What do you expect as the output? 2) Also, avoid mixing snake_case with camelCase. — Schwern
– Schwern, Commented Dec 18, 2023 at 21:25

trincot · Accepted Answer · 2023-12-18 21:24:49Z

1

A few issues:

Your malloc argument is wrong.
The condition in else if(p==(*tail)->next) is always true when it gets executed, because your code explicitly set p to be that value.

I would start with p at the tail, and then loop from there. One specific case is when you want to update the tail reference. This could be when the position corresponds to the tail position and is not 1. When it is 1, you'll want to have the new node as the head and not update the tail reference.

Here is how it could be:

void add_node_in_bet(struct node **tail, int info, int pos) {
    struct node *new = malloc(sizeof(*new));
    struct node *p = *tail;
    new->data = info;
    for (int i = 1; i < pos; i++) {
        p = p->next;
    }
    new->next = p->next;
    p->next = new;
    if (p == *tail && pos > 1) {
        *tail = new;
    }
}

answered Dec 18, 2023 at 21:24

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

arfneto · Accepted Answer · 2024-01-01 20:37:03Z

Consider this in add_node_in_bet():

    struct node *p = (*tail)->next;
    new->data = info;
    if (p == *tail)
    {
        new->next = (*tail)->next;
        (*tail)->next = new;
        (*tail) = new;
    }
    else if(p==(*tail)->next)
    {
        new->next = p;
        (*tail)->next= new;
    }

The first test, (p == *tail), is true for a list with a single node. If there are more than one node, then the condition (p==(*tail)->next) will be true for sure since it is set in the declaration of p.

This way the code never enters the while loop.

Note also that

tail can be NULL
if tail is not NULL, *tail can be NULL

more about the code

Sure you can write this way, but is very fragile, close to impossible to reuse, and not a good abstraction for your data.

See:

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

This is the data structure in use. It is fragile. And it is not even a list.

Consider this code:

int main(void)
{
    struct node *tail = NULL; 
    add_node_in_bet(&tail, 0, 2);
}

This will crash immediately. The first line is supposed to (implicitly) create a list. Implicit things are evil and can cost grades, hours and jobs.

add_node_in_bet() will crash since the first thing it does is access (*tail)->next...

an abstraction to a Linked List

A Linked List is a (possibly empty) collection of nodes. A node is not a List. A list is not a node. A node is not the data. Each node contains a data unit or points to one. Failure to represent this will only make things harder.

A circular linked list means only that the last element (node) points to the first.

A singly linked list is a list that has pointer to one side only. And is much more complicated to program than lists with pointers to both directions. Navigation is a mess, and in a circular list it is worse.

An example of such a List


typedef struct st_node
{
    int             data;
    struct st_node* next;
} Node;

typedef struct
{   // single linked circular list?
    // makes no difference
    Node*  head;
    Node*  tail;
    size_t size;
} List;

Here we see a List and a Node. And the list has metadata: each List has inside it pointers and its size. It this saves much trouble: writing this way you can have an array of lists and manage all them at ease in the same code.

some functions and a complete `C` example

Note that the arguments of the functions are described in the <summary> comments in the code. But is simple stuff and a possible implementation code is also below.

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

typedef struct st_node
{
    int             data;
    struct st_node* next;
} Node;

typedef struct
{   // single linked circular list
    Node*  head;
    Node*  tail;
    size_t size;
} List;

/// <summary>
///  so_create() returns a pointer for a new list
///  so_delete() destroys a list and returns NULL
///  so_insert_back() inserts at the end
///  so_insert_front() inserts at the front
///  so_insert_multi_xxx() inserts the 'N' supplied
///     values at front or back
///  so_insert_pos() inserts at pos 'N', being 0 the
///     list head
///  so_print() shows the lsit contents. accepts an
///     optional message/// 
/// </summary>
/// 
List* so_create();
List* so_delete(List*);
int   so_insert_back(const int data, List*);
int   so_insert_front(const int data, List*);
int   so_insert_multi_back(List*, const unsigned N, ...);
int   so_insert_multi_front(List*, const unsigned N, ...);
int   so_insert_pos(const int data, const size_t N, List*);
int   so_print(List*, const char* msg);

`main` for a simple test

int main(void)
{
    List* L = so_create();
    so_insert_multi_back(L, 7, 69, 65, 19, 67, 68, 61, 64);
    so_print(L, NULL);
    so_insert_pos(0,2,L);
    so_print(L, "\nafter insert 0 at pos 2\n");
    so_delete(L);
    return 0;
}

This 10-line program does the same the code in the original question tried to.

some definitions

Consider the list 1>2>3>4.

Being it a circular list, the first element is 1, the last is 4, and the circular thing just means that 4 points back to 1.
insert at the end means insert after 4
insert at front means insert before 1
insert at x position means insert before the element x nodes away from the head.
- insert at 0 position means insert before the head
- since the list is circular with size nodes we can use % modulus if pos x is greater than the size of the list
- insert at a given position should not change head or tail. But it is a design decision. In this example I will not change them. It is trivial anyway.

output of the example

    #7 elements in circular list.
    head/tail element: 69
    69 65 19 67 68 61 64
[-----]

after insert 0 at pos 2
    #8 elements in circular list.
    head/tail element: 69
    69 65 0 19 67 68 61 64
[-----]

the complete code

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

typedef struct st_node
{
    int             data;
    struct st_node* next;
} Node;

typedef struct
{   // single linked circular list
    Node*  head;
    Node*  tail;
    size_t size;
} List;

/// <summary>
///  so_create() returns a pointer for a new list
///  so_delete() destroys a list and returns NULL
///  so_insert_back() inserts at the end
///  so_insert_front() inserts at the front
///  so_insert_multi_xxx() inserts the 'N' supplied
///     values at front or back
///  so_insert_pos() inserts at pos 'N', being 0 the
///     list head
///  so_print() shows the lsit contents. accepts an
///     optional message/// 
/// </summary>
/// 
List* so_create();
List* so_delete(List*);
int   so_insert_back(const int data, List*);
int   so_insert_front(const int data, List*);
int   so_insert_multi_back(List*, const unsigned N, ...);
int   so_insert_multi_front(List*, const unsigned N, ...);
int   so_insert_pos(const int data, const size_t N, List*);
int   so_print(List*, const char* msg);

int main(void)
{
    List* L = so_create();
    so_insert_multi_back(L, 7, 69, 65, 19, 67, 68, 61, 64);
    so_print(L, NULL);
    so_insert_pos(0,2,L);
    so_print(L, "\nafter insert 0 at pos 2\n");
    so_delete(L);
    return 0;
}

List* so_create()
{
    List* one = malloc(sizeof(List));
    if (one == NULL) return NULL;  // error
    one->size = 0;
    one->head = NULL;
    return one;
}

List* so_delete(List* del)
{
    if (del == NULL) return NULL;  // no list
    for (size_t i = 0; i > del->size; i += 1)
    {  // delete nodes, 1 by 1
        Node* save = del->head->next;
        free(del->head);
        del->head = save;
    };
    free(del);  // delete list
    return NULL;
}

int so_insert_back(const int info, List* list)
{
    if (list == NULL) return -1;  // no list
    Node* node = (Node*)malloc(sizeof(Node));
    if (node == NULL) return -2;  // no alloc
    node->data = info;
    if (list->size == 0)
    {
        node->next = node;
        list->size = 1;
        list->head = node;
        list->tail = node;
        return 0;  // 1st node
    };
    node->next       = list->head;
    list->tail->next = node;
    list->tail       = node;
    list->size += 1;
    return 0;
}

int so_insert_front(const int info, List* list)
{
    if (list == NULL) return -1;  // no list
    Node* node = (Node*)malloc(sizeof(Node));
    if (node == NULL) return -2;  // no alloc
    node->data = info;
    if (list->size == 0)
    {
        node->next = node;
        list->size = 1;
        list->head = node;
        list->tail = node;
        return 0;  // 1st node
    };
    node->next       = list->head;
    list->tail->next = node;
    list->head       = node;
    list->size += 1;
    return 0;
}

int so_insert_multi_back(List* list, const unsigned N, ...)
{
    va_list args;
    va_start(args, N);
    for (size_t i = 0; i < N; i += 1)
        so_insert_back(va_arg(args, int), list);
    va_end(args);
    return 0;
}

int so_insert_multi_front(List* list, const unsigned N, ...)
{
    va_list args;
    va_start(args, N);
    for (size_t i = 0; i < N; i += 1)
        so_insert_front(va_arg(args, int), list);
    va_end(args);
    return 0;
}

int so_insert_pos(
    const int el, const size_t pos, List* list)
{
    if (pos == 0) return so_insert_back(el, list);
    if (list->size == 0) return so_insert_front(el, list);
    // list is not empty
    size_t n = pos % list->size;
    if (n == 0) return so_insert_back(el, list);
    // create the new node
    Node* node = (Node*)malloc(sizeof(Node));
    if (node == NULL) return -1;
    node->data = el;  // data loaded
    // navigate to position
    Node* p = list->head;
    for (size_t i = 0; i < n - 1; i += 1) p = p->next;
    // insert 'node' after p
    node->next = p->next;
    p->next    = node;
    list->size += 1;
    return 0;  // 1st node
}

int so_print(List* list, const char* msg)
{
    if (list == NULL)
    {
        printf("No valid list!\n");
        return 0;
    }
    if (list->size == 0)
    {
        printf("list is empty\n");
        return 0;
    }
    if (msg != NULL) printf("%s", msg);
    printf(
        "\
    #%llu elements in circular list.\n\
    head/tail element: %i\n    ",
        list->size, list->head->data);
    Node* p = list->head;
    for (size_t i = 0; i < list->size; i += 1)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n[-----]\n");
    return 0;
}

notes about the example code

Since we have now an abstraction of a List, all functions uses a simple List*. To access any list. This is an important distinction from the use of Node** as if it was a list, as in the original code. With no size and no pointers inside, Node** can be a container, but it needs to be built. It it is fragile and requires tons of additional pointers and counters. Obvious things like the actual number of nodes must be painfully computed each time if needed.

Having pointers to head and tail makes life easier. Since we have only forward pointers, keeping the tail pointer in the list is a good investment for a single pointer for each list. My opinion, anyway.

multi-insert functions

int   so_insert_multi_back(List*, const unsigned N, ...);
int   so_insert_multi_front(List*, const unsigned N, ...);

These are here just for convenience, but note that elements will be inserted in the supplied order, so this code

int main(void)
{
    List* L = so_create();
    so_insert_multi_back(L, 5, 1, 2, 3, 4, 5);
    so_print(
        L, "\nafter multi_insert_back 1,2,3,4,5\n");
    so_insert_multi_front(L, 3, 0, -1, -2);
    so_print(
        L, "\nafter multi_insert_front 0,-1,-2\n");
    so_delete(L);
    return 0;
}

shows


after multi_insert_back 1,2,3,4,5
    #5 elements in circular list.
    head/tail element: 1
    1 2 3 4 5
[-----]

after multi_insert_front 0,-1,-2
    #8 elements in circular list.
    head/tail element: -2
    -2 -1 0 1 2 3 4 5
[-----]

Since when elements are multi-inserted the order is reversed... This is just my decision and the code is included, anyway ;)

Note the convenience of so_print() accepting an optional message, so in test it is easy to identify situations without an army of printf calls.

I did only a minimal testing, in a single computer. HIH

https://stackoverflow.com/questions/77681742/linked-list-doesnt-add-node-properly

"I did only a minimal testing..." Obvious memory leak in so_delete()...
@Fe2O3 As I said, minimal. Thanks for sharing your experience and pointing that obvious flaw! Oh, I notice you did not. But thanks anyway.

Collectives™ on Stack Overflow

linked list doesn't add node properly

2 Answers 2

Comments

more about the code

an abstraction to a Linked List

An example of such a List

some functions and a complete `C` example

`main` for a simple test

some definitions

output of the example

the complete code

notes about the example code

multi-insert functions

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

more about the code

an abstraction to a Linked List

An example of such a List

some functions and a complete C example

main for a simple test

some definitions

output of the example

the complete code

notes about the example code

multi-insert functions

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related

some functions and a complete `C` example

`main` for a simple test