// Implements a list of numbers using a linked list
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int number;
struct node *next;
}
node;
node *makelist(int argc, char *argv[]);
int check_spaces(char *input);
int *nodes(char *input, int amount);
node *add(char *input, node *list, int *numbers, int amount);
/*int delete();
int find();*/
int main(int argc, char *argv[])
{
//Get linked list
node *list = makelist(argc, argv);
//Print linked list
for (node *ptr = list; ptr != NULL; ptr = ptr->next)
{
printf("%i ", ptr->number);
}
printf("\n");
// Free memory
node *ptr = list;
while (ptr != NULL)
{
node *next = ptr->next;
free(ptr);
ptr = next;
}
char c;
//Give choices
printf("Do you want to (d)delete a node, (a)add a node, or (f)find a node? ");
//Repeat if incorrect input
do
{
scanf("%c", &c);
if (c == 'd' || c == 'a' || c == 'f')
{
break;
}
else
{
printf("Wrong input, try again. ");
}
}
while (c != 'd' || c != 'a' || c != 'f');
//If user chose to "add" node(s)
if (c == 'a')
{
char *name = get_string("");
char *input = get_string("What are the node(s) that you want to add? ");
int amount = check_spaces(input);
int *numbers = malloc(amount * 4);
*numbers = *nodes(input, amount);
list = add(input, list, numbers, amount);
for (node *ptr2 = list; ptr2 != NULL; ptr2 = ptr2->next)
{
printf("%i ", ptr2->number);
}
free(numbers);
free(list);
}
//If user chose to "delete" node(s)
else if (c == 'd')
{
printf("d");
}
//If user chose to "find" node(s)
else
{
printf("c");
}
return 0;
}
//Make linked list
node *makelist(int argc, char *argv[])
{
// Memory for numbers
node *list = NULL;
// For each command-line argument
for (int i = 1; i < argc; i++)
{
// Convert argument to int
int number = atoi(argv[i]);
// Allocate node for number
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 0;
}
n->number = number;
n->next = NULL;
// If list is empty
if (list == NULL)
{
// This node is the whole list
list = n;
}
// If list has numbers already
else
{
// Iterate over nodes in list
for (node *ptr = list; ptr != NULL; ptr = ptr->next)
{
// If at end of list
if (ptr->next == NULL)
{
// Append node
ptr->next = n;
break;
}
}
}
}
return list;
}
//Add function
node *add(char *input, node *list, int *numbers, int amount)
{
int a = 0;
while (numbers[a] != '\0')
{
a++;
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 0;
}
n->number = numbers[amount-a];
// Prepend node to list
n->next = list;
list = n;
}
return list;
}
//Get command line arguments from printf
int *nodes(char *input, int amount)
{
int *y = malloc(amount * 4);
char *x = &input[0];
y[0] = atoi(x);
int i = 0;
int j = 1;
while (input[i] != '\0')
{
if (input[i] == ' ')
{
x = &input[i+1];
y[j] = atoi(x);
j++;
}
i++;
}
return y;
}
//How many nodes are we messing with
int check_spaces(char *input)
{
int numbers = 1;
int i = 0;
while (input[i] != '\0')
{
if (input[i] == ' ')
{
numbers++;
}
i++;
}
return numbers;
}
/*int delete()
{
}
int find()
{
}*/
The issue is stemming from C's inability to return arrays. The question is about the adding function, because the other functions are incomplete.
My whole plan was to use atoi to convert the users command line arguments into numbers, and then to reverse add them into the linked list. If my list was 3, 4, 5, and I put in 1,2, it would become 1,2,3,4,5 (in theory).
My nodes function is what does all the converting, and I can't return an array because of the rules of C. So I've returned a pointer instead. I thought all of the numbers were back to back because of malloc, so I had a loop going through n->number = numbers[amount - a]. The first value was spot on, but then the rest were just a bunch of garbage values.
I'm pretty sure its because the pointer only points to the first object, and the rest are in the order they were added in. I've tried messing around with accessing the other values, but with no such luck. To be honest, I feel like there's something huge I'm missing.
There has to be something I'm overcomplicating here.
I believe you are, as you said, overcomplicating things.
The issue is stemming from C's inability to return arrays
Well, the issue in itself is not clear to me.
C inability does not existMy whole plan was to use atoi to convert the users command line arguments into numbers, and then to reverse add them into the linked list. If my list was 3, 4, 5, and I put in 1,2, it would become 1,2,3,4,5 (in theory).
It just means that you want to add the elements always at the start of the list. It is not a common choice: in general is preferred to have the elements inserted at the end, preserving the order of insertion. Such a list is called stable.
Another common option is to insert the elements in order but preserving the order of insertion of possible duplicates. So if you add 1 1 2 3 4 the second 1 will de inserted after the first 1
My nodes function is what does all the converting, and I can't return an array because of the rules of C. So I've returned a pointer instead
This is the node function
// Get command line arguments from printf
int* nodes(char* input, int amount)
{
int* y = malloc(amount * 4);
char* x = &input[0];
y[0] = atoi(x);
int i = 0;
int j = 1;
while (input[i] != '\0')
{
if (input[i] == ' ')
{
x = &input[i + 1];
y[j] = atoi(x);
j++;
}
i++;
}
return y;
}
What are you trying to do? You said that atoi would be used to convert the arguments, but now node "does all the converting". How can it be?
I thought all of the numbers were back to back because of malloc, so I had a loop going through n->number = numbers[amount - a]. The first value was spot on, but then the rest were just a bunch of garbage values.
I do not understand what you are trying to say. malloc just allocates memory based on a single argument, the size in bytes.
I'm pretty sure its because the pointer only points to the first object, and the rest are in the order they were added in.
Well, it is expected: pointers point to something. Only to one something. About the rest I do not see what it is. May be the other elements? Or the other nodes?
I feel like there's something huge I'm missing.
I also believe you are. See the example and discussion below. Maybe it adds something
C complete EXAMPLEI will try to show you an approach that can be used for every program, but using the linked list the way you are trying to build.
Because it is a very very common assignment to students, I will leave complete code and output.
Consider this program p at start
#include <stdio.h>
int main(int argc, char* argv[])
{
if (argc < 2)
{
printf("\tNo arguments provided!\n");
return -1;
}
printf(
" %d arguments on the command line\n\n", argc - 1);
for (int i = 1; i < argc; i += 1)
printf(" #%d \"%s\"\n", i, argv[i]);
return 0;
}
Presented with these arguments
p 1 2 3 4 5 5
This is the output:
6 arguments on the command line
#1 "1"
#2 "2"
#3 "3"
#4 "4"
#5 "5"
#6 "5"
The operating system is providing the array. There is no need to convert this to another array of int just to insert into the linked list. We can just use these values and in this order.
This is what you call a linked list:
typedef struct node
{
int number;
struct node* next;
} node;
But it is not. Failure on seeing this will make your life really harder around daa structures. Do you have a ext-book on that?
A linked list is a --- possibly empty --- collection of nodes. Each node constains or points to some data.
A node is not a list. A list is not a node.
This is a node:
typedef struct s_n
{
int number;
struct s_n* next;
} Node;
Note that having pointers to only one direction is much more complicated than having next and prev pointers. Single linked lists are harder than double linked lists to manage.
Why? Navigation. For example when you need to delete a node --- and you will --- and have only next pointers you must remember that, unless you are deleting the first element, some previous node points to the one you are deleting, but you do not have its address...
Supose list is { v, x, y }. When deleting x if you had prev pointer in Node then x->prev points to v and v->next points to x. And x->next points to y.
In order to delete x you must point v to y and y pointing back to v before deleting x. And it is easy:
x->prev->next = y and y->prev = v. Then x can be deleted.
If you have only next pointers you need to save state in the code for delete. See the example below.
typedef struct
{
unsigned size;
Node* head;
Node* tail;
} List;
Now we have a list AND a node. Note the convention of reserving the first letter in uppercase for names created in the program.
As you see the list has 2 pointers, because we want to keep the values in the order of insertion and it would not be efficient to traverse the list every time just to get the address of the last node.
And, as it is handy to know how many nodes are in the list at any time, we also have size. I believe that is easy to know how it is unsigned value.
You can for sure go without size but it is way simpler to always know the number of items in the if it is always in the list.
Just before programming anything, let us see the operations we will need and how the program will work.
The operations:
At program start the list will be created with the values supplied in the command line. If there were none the list will be created empty, since all operations are still possible on an empty list
In the style of RAII in C++ at first we have
List* create();
List* destroy(List* toGo);
Using this way makes life easier: one can create List in a single line and to destroy a List we can at the same time guarantee that the list pointer is invalidated: no chance of dangling pointers.
Note that we do no have yet a single line of code. Just looking around the data.
If we want to destroy a list it is clear that we will need to delete all nodes before deleting the list in itself, or else we will leak memory. As we are testing, it is clear that we will need an option to print the list contents also. So we add these functions as a minimum
int add(int data, List* list);
Node* delete(int one, List* list);
int display(List* list, const char* title);
int find(int one, List* list);
Since we have some definitions and the original program that echoes the line arguments we can write a second program
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct s_n
{
int number;
struct s_n* next;
} Node;
typedef struct
{
unsigned size;
Node* head;
Node* tail;
} List;
List* create();
List* destroy(List* toGo);
int add(int data, List* list);
int delete(int one, List* list);
int display(List* list, const char* title);
int find(int one, List* list);
int main(int argc, char* argv[])
{
if (argc < 2)
{
printf("\tNo arguments provided!\n");
return -1;
}
printf(
" %d arguments on the command line\n\n",
argc - 1);
for (int i = 1; i < argc; i += 1)
printf(" #%d \"%s\"\n", i, argv[i]);
return 0;
}
List* create() { return NULL; }
List* destroy(List* toGo) { return NULL; }
int add(int data, List* list) { return 0; }
int delete(int one, List* list);
int display(List* list, const char* title) { return 0; }
int find(int one, List* list) { return 0; }
And we can even run it...
create and destroy listTo create a list is just a matter of allocating memory for it and marking it as empty
List* create()
{
List* one = malloc(sizeof(List));
if (one == NULL) return NULL;
one->size = 0;
one->head = NULL;
one->tail = NULL;
return one;
}
To delete a list is also basic: we know we have size nodes and we know how to delete each one, since we have a function for that, so...
List* destroy(List* gone)
{
if (gone == NULL) return NULL;
for (unsigned i = 0; i < gone->size; i += 1)
{
Node* p = gone->head->next;
free(gone->head);
gone->head = p;
}
free(gone);
return NULL;
};
This is ok since nodes here do not allocate memory.
programNow we can run this version of main:
int main(int argc, char* argv[])
{
List* my_list = create();
my_list = destroy(my_list);
return 0;
}
Note that destroy() always returns NULL and it may seem silly. But the target is to be able to invalidate the List pointer in the same line that the list is destroyed, and in the code that calls destroy():
my_list = destroy(my_list);
This leaves no chance for a dangling invalid pointer to remain lost in the calling code...
And it runs ok! It does little but it is good for moral support
add()int add(int data, List* list)
{ // insert at last element
if (list == NULL) return -1;
Node* p = malloc(sizeof(Node));
p->number = data; // data copied to node
p->next = NULL; // inserted at tail
if (list->size == 0)
{
list->head = list->tail = p;
list->size = 1;
return 0;
}
list->tail->next = p;
list->tail = p;
list->size += 1; // count it in
return 0;
}
A bit more than 10 lines. Note that we use the tail pointer to insert at the end and preserve the insertion order of the nodes. Anyway to insert at the beginning or head is identical, just using the head pointer and make your node->next point to head first before reassigning head.
display()It is obvious that we can call display() on an empty list or on a list with dozens of items. Or even with an invalid pointer, so let us do it.
The use of a title is very handy here, so no need to precede tests by the very very common printfs...
int display(List* list, const char* title)
{
if (title != NULL) printf("%s", title);
if (list == NULL)
{
printf("\nList does not exist\n");
return 0;
}
printf("\nList size: %u\n [ ", list->size);
Node* p = list->head;
for (unsigned i = 0; i < list->size; i += 1)
{
printf("%d ", p->number);
p = p->next;
}
printf("]\n\n");
return 0;
};
display() just follows the pointers. This list is really minimalist with a single number.
Consider this:
int main(int argc, char* argv[])
{
if (argc < 2)
{
printf("\tNo arguments provided!\n");
return -1;
}
printf(
" %d arguments on the command line\n", argc - 1);
List* my_list = create();
display(my_list, "list empty");
for (int i = 1; i < argc; i += 1)
add(atoi(argv[i]), my_list);
display(my_list, "after insertions");
my_list = destroy(my_list);
display(my_list, "afer destroy()");
return 0;
}
And the output for
p 1 2 3 4 5
5 arguments on the command line
list empty
List size: 0
[ ]
after insertions
List size: 5
[ 1 2 3 4 5 ]
afer destroy()
List does not exist
Until now, no surprises: working at the first run as expected, since we wrote step by step around the data
delete() and find() simple implementationsThese are similar to display() since it is the matter of navigate the whole list, but
delete() return 0 when element is found and deletedfind() returns the Node address when found, or NULLThis is a possible delete():
int delete(int data, List* list)
{ // delete the 1st node that contains 'data'
if (list == NULL) return -1;
Node* p = list->head;
Node* prev = NULL;
for (unsigned i = 0; i < list->size; i += 1)
{
if (p->number == data)
{ // this is the one
if (p == list->head)
list->head = p->next;
else
{
prev->next = p->next;
if (p == list->tail) list->tail = prev;
}
list->size -= 1;
free(p);
return 0;
}
prev = p; // save state: no back pointer
p = p->next; // go ahead
}
return -2; // not found
};
about 15 lines due to the missing back pointers
And a possible find():
Node* find(int data, List* list)
{ // return address of the first node with 'data'
// or NULL if not found. Do not consider the
// 'list` as sorted
if (list == NULL)
{
fprintf(stderr, "\nfind(): List does not exist\n");
return NULL;
}
Node* p = list->head;
for (unsigned i = 0; i < list->size; i += 1)
{
if (p->number == data) return p;
p = p->next;
}
return NULL;
};
Now it is a good time to bring back the very first program and insert the arguments that came on the command line.
It can not be hard since we already have add(). The arguments are strings, but it is good to know that we have also atoi() so:
int main(int argc, char* argv[])
{
if (argc < 2)
{
printf("\tNo arguments provided!\n");
return -1;
}
printf(
" %d arguments on the command line\n", argc - 1);
List* my_list = create();
display(my_list, "list empty");
for (int i = 1; i < argc; i += 1)
add(atoi(argv[i]), my_list);
display(my_list, "after insertions");
//
delete (1, my_list);
delete (3, my_list);
delete (5, my_list);
display(my_list, "after delete 1 3 & 5");
//
my_list = destroy(my_list);
display(my_list, "afer destroy()");
return 0;
}
3 calls to delete the first, last and a middle record were inserted for testing...
for (int i = 1; i < argc; i += 1) add(atoi(argv[i]), my_list);
Just calling atoi() before inserting the argument in the list.
We know that add() works, we know that atoi() works, and the rest we already tested, so it is just a matter of copy and paste stuff.
5 arguments on the command line
list empty
List size: 0
[ ]
after insertions
List size: 5
[ 1 2 3 4 5 ]
after delete 1 3 & 5
List size: 2
[ 2 4 ]
afer destroy()
List does not exist
C code#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct s_n
{
int number;
struct s_n* next;
} Node;
typedef struct
{
unsigned size;
Node* head;
Node* tail;
} List;
List* create();
List* destroy(List* toGo);
int add(int data, List* list);
int delete(int one, List* list);
int display(List* list, const char* title);
Node* find(int one, List* list);
int main(int argc, char* argv[])
{
if (argc < 2)
{
printf("\tNo arguments provided!\n");
return -1;
}
printf(
" %d arguments on the command line\n", argc - 1);
List* my_list = create();
display(my_list, "list empty");
for (int i = 1; i < argc; i += 1)
add(atoi(argv[i]), my_list);
display(my_list, "after insertions");
//
delete (1, my_list);
delete (3, my_list);
delete (5, my_list);
display(my_list, "after delete 1 3 & 5");
//
my_list = destroy(my_list);
display(my_list, "afer destroy()");
return 0;
}
List* create()
{
List* one = malloc(sizeof(List));
if (one == NULL) return NULL;
one->size = 0;
one->head = NULL;
one->tail = NULL;
return one;
}
List* destroy(List* gone)
{
if (gone == NULL) return NULL;
for (unsigned i = 0; i < gone->size; i += 1)
{
Node* p = gone->head->next;
free(gone->head);
gone->head = p;
}
free(gone);
return NULL;
};
int add(int data, List* list)
{ // insert at last element
if (list == NULL) return -1;
Node* p = malloc(sizeof(Node));
p->number = data; // data copied to node
p->next = NULL; // inserted at tail
if (list->size == 0)
{
list->head = list->tail = p;
list->size = 1;
return 0;
}
list->tail->next = p;
list->tail = p;
list->size += 1; // count it in
return 0;
}
int delete(int data, List* list)
{ // delete the 1st node that contains 'data'
if (list == NULL) return -1;
Node* p = list->head;
Node* prev = NULL;
for (unsigned i = 0; i < list->size; i += 1)
{
if (p->number == data)
{ // this is the one
if (p == list->head)
list->head = p->next;
else
{
prev->next = p->next;
if (p == list->tail) list->tail = prev;
}
list->size -= 1;
free(p);
return 0;
}
prev = p; // save state: no back pointer
p = p->next; // go ahead
}
return -2; // not found
};
int display(List* list, const char* title)
{
if (title != NULL) printf("%s", title);
if (list == NULL)
{
printf("\nList does not exist\n");
return 0;
}
printf("\nList size: %u\n [ ", list->size);
Node* p = list->head;
for (unsigned i = 0; i < list->size; i += 1)
{
printf("%d ", p->number);
p = p->next;
}
printf("]\n\n");
return 0;
};
Node* find(int data, List* list)
{ // return address of the first node with 'data'
// or NULL if not found. Do not consider the
// 'list` as sorted
if (list == NULL)
{
fprintf(stderr, "\nfind(): List does not exist\n");
return NULL;
}
Node* p = list->head;
for (unsigned i = 0; i < list->size; i += 1)
{
if (p->number == data) return p;
p = p->next;
}
return NULL;
};
I only wanted to show a way of write such things.
There are tests missing for find() but it is the same as delete(). Please let me know if it helps and if there are something I could add.