user6005857 user6005857 - 1 month ago 13
C Question

Search linked list by substring and create a new linkedlist with all structs that contain the substring

Suppose I have the following struct:

struct _node {
int id;
char *name;
struct node *next;
};


I want to write a function that goes through the linkedlist and looks for structs whose name member contains a certain substring and adds those structs to a new linkedlist and returns the new linkedlist.

I attempted doing this using strstr but at some point I am getting an infinite loop and I can't figure out exactly why the infinite loop is happening.

Here is my function:

struct _node *containSubstr(struct _node *head, char needle[]) {
if (head == NULL) {
printf("BLOOP BLEEP BOOP BEEP.\n");
exit(EXIT_FAILURE);
}

struct _node *curr = head;
struct _node *returnHead = createEmptyNode();

while (curr != NULL) {
char haystack[strlen(curr->name)];
strcpy(haystack, curr->name);

strToLower(needle);
strToLower(haystack);

if (strstr(haystack, needle) != NULL) {
// this is where I get the infinite loop
append(returnHead, curr);
}

curr = curr->next;
}

return returnHead;
}


The functions append and createEmptyNode are tested and work fine.

I went over the logic multiple times and I think this must work. I filled my code with print statements and it seems like after it finds all the nodes that contain the substring it keeps repeating the last node and goes into an infinite loop.

Here is my append function:

void append(struct _node *head, struct _node *newNode) {
if (head == NULL) {
printf("BLOOP BLEEP BOOP BEEP.\n");
exit(EXIT_FAILURE);
}

struct _node *curr = head;

if(curr == NULL) {
head = newNode;
}
else {
while(curr->next != NULL) {
curr = curr->next;
}
curr->next = newNode;
}
}

Answer

Imagine this case: you have a list L that contains just 2 nodes (A and B) in your linked list. Imagine that both nodes A and B contain a substring you are looking for:

Original list L:

A->B->NULL

So after first iteration your new list L2 should look like this:

A->NULL

But in your append function you don't create a deep copy of a new node. Therefore, your new list L2 looks like this:

Empty_node->A->B->NULL

In the next step you move to node B. So you take your L2 and append there B. Your L2 after second iteration looks like this:

Empty_node->A->B->B (B points to itself).

Since you don't create deep copies you are actually always working with list L and when you append node B to what you think is the list L2 you actually append B to L and then B points to itself (curr->next = newNode; in your append function). So in the next iteration you are again asking if B contains the string you are looking for.

Conclusion

You need to create deep copies when creating new list.

In the current setup your append function modifies original list.