Anthony B Anthony B - 3 years ago 141
C Question

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

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 Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download