inserting into a linked list in C in ascending order without prev

Question

I am writing a function to insert into a linked list in C, based off of the following struct:

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


/* self-referential structure */
struct Node {
    int item;
    int id;
    struct Node *next;
};

struct List {
    struct Node *head;
    struct Node *tail;
};


struct List SLL_new(){
    /* construct an empty list */
    struct List list;
    list.head = NULL;
    list.tail = NULL;
    return list;
}

int SSL_length(struct List *list) {
    /* return the number of items in the list */
    struct Node *p;

    int n = 0;
    for (p = list->head; p != NULL; p = p->next) {
        ++n;
    }
    return n;
}

int SLL_empty(struct List *list) {
    /* return true if the list contains no items */
    return list->head == NULL;
}

int SLL_pop(struct List *list) {
    /* remove and return the first item of the list */
    struct Node *node = list->head;
    int item = node->item;
    list->head = node->next;
    if (SLL_empty(list)) {
        list->tail = NULL;
    }
    free(node);
    return item;
}

void SLL_clear(struct List *list) {
    /* remove all the items from the list */
    while (!SLL_empty(list)) {
        SLL_pop(list);
    }
}

void SLL_push(struct List *list, int item) {
    /*  insert the item at the front of the list */
    struct Node *node = malloc(sizeof(struct Node));
    node->item = item;
    node->next = list->head;
    if (SLL_empty(list)) {
        list->tail = node;
    }
    list->head = node;
}

void SLL_append(struct List *list, int item) {
    /* append the item to the end of the list */
    if (SLL_empty(list)) {
        SLL_push(list, item);
    }
    else {
        struct Node *node = malloc(sizeof(struct Node));
        node->item = item;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
}

void SLL_insert(struct List *list, int id, int item) {
    /*append item according to node data */
    struct Node *node = malloc(sizeof(struct Node));
    node->id = id;
    node->item = item;
    if(list->head == NULL){
        list->head = node;
        list->tail = node;
    }
    else if(list->head->id >= node->id){
        node->next = list->head;
        list->head = node;
    }
    else{
        struct Node *temp;
        struct Node *prev;
        temp = list->head->next;
        prev = list->head;
        while(temp != NULL && temp->id <= id) {
            prev = temp;
            temp = temp->next;
        }
        node->next = temp;
        prev->next = node;
    }
}

int main(int argc, char **argv) {
    int i;
    printf("hello world");
    struct List list = SLL_new();
    for (i = 0; i < 5; ++i) {
        SLL_insert(&list, i, i);
    }

}

This is my function so far:

void SLL_insert(struct List *list, int id, int item) {
    /*append item according to node data */
    struct Node *node = malloc(sizeof(struct Node));
    node->id = id;
    node->item = item;
    if(list->head == NULL){
        list->head = node;
        list->tail = node;
    }
    else if(list->head->id >= node->id){
        node->next = list->head;
        list->head = node;
    }
    else{
        struct Node *temp;
        struct Node *prev;
        temp = list->head->next;
        prev = list->head;
        while(temp != NULL && temp->id <= id) {
            prev = temp;
            temp = temp->next;
        }
        node->next = temp;
        prev->next = node;
    }
}

However, when I run this simply trying to insert it using the loop in the main at the bottom of the pastebin, my cmd simply seems to be running in an infinite loop. My question here is why is this the case, I seem to handle every case and there's a definitive stopping value in my while loop. My followup, miscellaneous question out of curiosity is theoretically, how would I insert into a linked list without keeping track of the previous node as I'm iterating through.

Answer 1

I'm going to repeat the advice of other questions.

1. You fail to set node->next=NULL when you insert the first item.
2. You also fail to update list->tail after the first insert.

Other recommendations:

Consider adding a 'constructor' function for Node called SSL_new_node() that returns an initialised node object. It's in the foot-hills of Object Orientation but if you have a single function that initialises nodes to a valid state and only create them using that your code will be more reliable and maintainable.

Add a function called SLL_destroy(struct List*list) that frees the list at the end to avoid memory leaks.

To answer the question about singly linked lists without keeping track of the previous node: You can implement this model efficiently without having a tail in the list. What you have to do (and have done) is keep track of the 'one before' so when you realise your loop has just gone past the insertion point you can pick up the previous node and hook the insertion in. There's no practical way of avoiding that.

You don't seem to make much use of tail anyway. In fact your function append just puts the item at the end of the list. That appears inconsistent with SLL_insert because it appears to be trying to maintain the list in order.

You should probably decide if your lists are ordered or not and if they are make sure all functions maintain that invariant. If you do that all functions are permitted to assume the list is ordered as a pre-condition and must make sure it remains ordered as a post-condition.

Answer 2

After allocating a new node here in SLL_insert:

struct Node *node = malloc(sizeof(struct Node));

you forget to initialize the next pointer to NULL.

And also in SLL_Insert you don't update the tail pointer if the element is inserted at the end of the list.

Answer 3

When you create a node, set its next to NULL.

struct Node *node = malloc(sizeof(struct Node));
node->id = id;
node->item = item;
node->next = NULL;

This way you will know for sure that tail's next is NULL and you will not get an undefined behavior. Also, it is worth to consider creating a separate function which will find the last element smaller or equal than the input and return NULL if not found. It will simplify your life greatly to use such helper functions.