Most new programmers have a general trend to overcomplicate the matter at hand. The cause of this is because instead of sitting down and actually thinking about the problem at hand, new programmers decide to just jump in and start coding. With this in mind, let's revisit what your thought process should have been:
Problem: Create a program to handle book orders
Your solution: Implement a linked list. Now unless for academia, I can tell you this isn't necessarily the best option; however, I will play along.
Problem: What is a linked list?
YOUR answer:
Code:
struct order {
char dir;
float price;
int size;
char instr[5];
};
struct bookOrder {
struct bookOrder *next;
struct order *order;
};
My Answer: A linked list is simply a group of structures (containers to be exact, you can have a series of class objects) that have at least one member that is a pointer to the next object in the list. - Notice I didn't start programming anything yet, however with my answer let's look at your structure (node definition) and see what we could come up with:
Code:
struct order {
char dir;
float price;
int size;
char instr[5];
struct order* next;
};
Problem: How do I implement my linked list in my program?
YOUR answer: <more random coding>
My answer: A linked list is a group or chain of nodes. As with all chains we need to define an anchor or starting point (which can be as simple as an instance of our node) and an ending point. You define the end of a linked list by having the last node’s next pointer set to NULL.Now in the beginning of our program to signify an initially empty list we will set firstNode to NULL..
With that in mind let's revisit our program:
Code:
int main (void){
struct order *myOrder;
myOrder = NULL;
return (0);
}
The remaining concept to grasp the fundamentals of linked lists lies in successfully adding and removing nodes from our list. These topics revolve around dynamic memory allocation, using malloc() and free().This topic is as easy to understand however it seems to be the hardest for new programmers to grasp. The prototype for malloc() is:
Code:
void* malloc(size_t size);
All malloc() does is allocate size bytes and returns a pointer of type void to that memory, or NULL if an error occured.The standard convention for using malloc is:
Code:
pointer = malloc(n * sizeof(*pointer));
where n is the number of elements you need and *pointer (the dereferenced pointer, which in your case would be **pointer) is used to determine the size of the individual element.
So let's take a look at our addNode function:
Code:
void addNode(struct order** bookOrder){
struct order* newNode = malloc(sizeof(**bookOrder));
//if couldn't allocate memory, exit
if(!newNode){
printf("Couldn't allocate memory\n");
return;
}
}
Now that we understand how to allocate the memory, lets take a look at how we add the node to our list. Remember that we signify the end of our list by having the last node’s next node pointer be NULL. Thus to add a new node we simply “walk through” our linked list until we find the last node. Once we are there we set the last node’s next node pointer to our newly created node. Thus the implementation would look like:
Code:
//first check if the linked list is empty
//if it is make the new node the first node
if(*bookOrder == NULL) {
*bookOrder = newNode;
return;
}
//if not find the last node
walker = *bookOrder;
while(walker->next != NULL){
walker = walker->next;
}
//set last node's next node to our new node
walker->next = newNode;
So now look at our program with this knowledge:
Code:
#include <stdio.h>
#include <stdlib.h>
struct order {
char dir;
float price;
int size;
char instr[5];
struct order* next;
};
void addNode(struct order**);
int main (void){
struct order *myOrder;
myOrder = NULL;
for(int i=0; i < 3; i++)
addNode(&myOrder);
for(int j = 0; j < 3; j++){
printf("Book %d is $%f\n",j, myOrder->price);
myOrder = myOrder->next;
}
getchar();
return (0);
}
void addNode(struct order** bookOrder){
//Demonstration only
static float price = 1.0f;
//-----------------------
//Create our walker pointer
struct order* walker;
//Allocate space for our newNode
struct order* newNode = malloc(sizeof(**bookOrder));
//if couldn't allocate memory, exit
if(!newNode){
printf("Couldn't allocate memory\n");
return;
}
//here we would intiliaze our values for our order
newNode->price = price++;
newNode->next = NULL;
//ect.....
//Check to see if new list
if(*bookOrder==NULL){
*bookOrder = newNode;
return;
}
//else walk to the end of our list
walker = *bookOrder;
while(walker->next != NULL){
walker = walker->next;
}
//add our new node
walker->next = newNode;
}