So for a class of mine I need to write a linked list in C, which adds or deletes items as they are read from a file, and as they are inserted, they are placed in order via insertion sort. Each line in the file contains a name, followed by either a or d, which states whether to add or delete that name.
I understand the concept of linked lists, and have implemented them in Java before. For some reason I just can't get this to work in C. Any help would be greatly appreciated.
The first value now makes it into the list, but there is another issue as commented below.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
char name[42];
struct node *next;
};
void insertNode(char name[42], struct node *head)
{
struct node *new = (struct node*)malloc(sizeof(struct node));
strcpy(new->name, name);
struct node *curr = head;
int finished = 0;
if(!curr)
{
head = new;
return;
}
while(curr->next != NULL) //This loop right here is not working
//it doesn't make it into the loop, curr somehow equals null
//not sure why this isn't working
{
if((strcmp(curr->name, new->name) < 0))
{
new->next = curr->next;
curr->next = new;
finished = 1;
break;
}
curr = curr->next;
}
if(finished = 0)
{
new->next = curr->next;
curr->next = new;
}
}
void removeNode(char name[42], struct node *head)
{
struct node *temp = (struct node*)malloc(sizeof(struct node));
strcpy(temp->name, name);
struct node *curr = head;
while(curr->next != NULL)
{
if(curr->next == temp)
{
curr->next = temp->next;
free(temp->name);
temp->next = NULL;
}
}
}
void FREE(struct node *head)
{
int i;
struct node *temp;
while(head != NULL)
{
temp = head;
head = head->next;
free(temp);
}
}
void printList(struct node *head)
{
struct node *curr = head;
printf("Linked list:\n");
while(curr != NULL)
{
printf("%s\n", curr->name);
curr = curr->next;
}
}
int main(void)
{
FILE *input = fopen("hw7.data", "r");
struct node *head = (struct node*)malloc(sizeof(struct node));
head->next = NULL;
strcpy(head->name, "");
char *tempText = NULL;
char *tempName = NULL;
char *tempOP = NULL;
size_t lineLen;
int i = 0;
getline(&tempText, &lineLen, input);
while(!feof(input))
{
tempName = strtok(tempText, " ");
tempOP = strtok(NULL, "\n");
if(i == 0)
{
strcpy(head->name, tempName);
i = 1;
}
if(tempOP[0] == 'a')
{
insertNode(tempName, head);
}
else
{
removeNode(tempName, head);
}
getline(&tempText, &lineLen, input);
}
printList(head);
fclose(input);
FREE(head);
return 0;
}
Here is the data file:
Beverly a
Kathy a
Radell a
Gary a
Chuck a
David a
kari a
Tom a
Tanya a
Scott a
Beverly d
Brenda d
Kathy a
Gary a
WenChen a
Chuck a
Mike a
Emanuel a
Linda a
Bernie a
Hassan a
Brian a
Gary d
Kathy d
Gary a
Eunjin a
Kathy a
Brenda a
Jun a
Peanut a
Travis a
There are a plethora of things wrong in this code, including, but not limited to:
free on data that was never directly malloc'd or realloc'dfeof in a while condition.Reworking the code for each of these, start with the basics. To avoid buffer overflowing your structure name member, just use a dynamic allocation. You're already killing caching by using a linked list; may as well make sure it's 6-feet-under:
struct node
{
char *name; /* will use strdup() for allocation */
struct node *next;
};
Moving on, the insertion routine can walk the list using a pointer to pointer (and main passes us the head pointer by address) so we can modify it via dereference. This is critical, and missing in your code:
void insertNode(char const name[], struct node **head)
{
printf("Adding: %s\n", name);
while (*head && strcmp((*head)->name, name) < 0)
head = &(*head)->next;
struct node *p = malloc(sizeof *p);
p->name = strdup(name);
p->next = *head;
*head = p;
}
When it comes to removal, we can do the same thing, which has the added advantage of proper head pointer management, even in the case of a single node in the linked list, or even none at all:
void removeNode(char const name[], struct node **head)
{
int cmp = 0;
while (*head && (cmp = strcmp((*head)->name, name)) < 0)
head = &(*head)->next;
if (*head && (cmp == 0))
{
printf("Removing: %s\n", name);
struct node *tmp = *head;
*head = tmp->next;
free(tmp->name); // note: freeing what we strdup()'d
free(tmp);
}
else
{
printf("Not found: %s\n", name);
}
}
Though not required for this case, I always advise using the same by-address pointer to pointer mechanics with the scorched-earth freeList ideology as well. It ensures you don't leave the caller with a dangling pointer they foolishly may try to dereference.
void freeList(struct node **head)
{
while (*head)
{
struct node *tmp = *head;
*head = tmp->next;
free(tmp->name);
free(tmp);
}
}
When it comes to printing the list, walking it with a const pointer is trivial:
void printList(struct node const *head)
{
printf("Linked list:\n");
for (; head; head = head->next)
printf("%s\n", head->name);
}
Finally, the heart of your program, main. Fixing the while-loop to only continue while line content is actually read, and properly freeing the final result from getline rather than letting it leak (not that it matter here, since the program will shortly exit, but good practice), we get:
int main()
{
FILE *input = fopen("hw7.data", "r");
if (!input)
{
perror("Failed to open file: ");
return EXIT_FAILURE;
}
struct node *head = NULL;
char *text = NULL;
size_t lineLen = 0;
while(getline(&text, &lineLen, input) > 0)
{
char *name = strtok(text, " ");
char *op = strtok(NULL, "\n");
if(*op == 'a')
{
insertNode(name, &head);
}
else if (*op == 'd')
{
removeNode(name, &head);
}
}
fclose(input);
free(text);
printList(head);
freeList(&head);
return EXIT_SUCCESS;
}
Output
The following is the output from your input, with the added instrumentation I put in insertNode and removeNode to let you know what is going on:
Adding: Beverly
Adding: Kathy
Adding: Radell
Adding: Gary
Adding: Chuck
Adding: David
Adding: kari
Adding: Tom
Adding: Tanya
Adding: Scott
Removing: Beverly
Not found: Brenda
Adding: Kathy
Adding: Gary
Adding: WenChen
Adding: Chuck
Adding: Mike
Adding: Emanuel
Adding: Linda
Adding: Bernie
Adding: Hassan
Adding: Brian
Removing: Gary
Removing: Kathy
Adding: Gary
Adding: Eunjin
Adding: Kathy
Adding: Brenda
Adding: Jun
Adding: Peanut
Adding: Travis
Linked list:
Bernie
Brenda
Brian
Chuck
Chuck
David
Emanuel
Eunjin
Gary
Gary
Hassan
Jun
Kathy
Kathy
Linda
Mike
Peanut
Radell
Scott
Tanya
Tom
Travis
WenChen
kari
Summary
There were plenty of things wrong. I addressed everything I could find above, and hopefully provided some concrete examples of linked-list management that you can use now and in the future.
I strongly advise you walk this code in a debugger and pay very close attention to the variables as they change. Load up your watch-list and see what each line does as you progress through the input items. Learning by debugging correctly functioning code can be a great learning technique, and worth the half-hour you should spend on it.