C is a procedural language, and does not support objects. That is, it does not support entities which contain data and model behavior. We can botch together something of the sort in C, but it is still far from what we would ever consider a class.
C does not support Encapsulation. While you may set up a group of data types to only be accessible through a structure collection, it still can be accessed from anywhere, by anything, as long as the collection exists within a scope seen by what is trying to access it. What I mean by collection here is a structure. Let me clarify.
Let's say I have a structure called MyStruct, and it has two data members.
struct MyStruct {
int a, b;
};
The structure is called MyStruct. This is obvious.
We can then create a variable of this type.
struct Mystruct myCollection;
This item, myCollection, is what I am referring to when I speak of a Collection. It is an entity created from a struct. There probably is a more technical term for it, but for the purposes of this tutorial, Collection will suffice. Please do not confuse structures with classes, or Collections with objects. There is a distinct, powerful difference between these.
Ok, Let's begin.
The Ideology for this linked list is simple. You have one structure that represents a particular node, and one that represents the linked list as a whole. All of our functions, our operations, if you will, are performed on the list as a whole. The node structure is merely used in these operations, and contains our data, the integers.
Let's start with our included header files, and the declaration of our two structures.
Here are our included header files:
#include<stdio.h> #include<stdlib.h>
The reason for the standard library header file will be more apparent later on.
Our node structure is quite simple. It is as follows:
/* Node Structure */
struct node {
int data;
struct node *next;
};
The ideology here is key to understand in order to be able to take full advantage of a linked list. Look at our two data members. We have int data and struct node *next. The first is easy enough to figure out. It is the data member, this integer. We could change this member's type, and the linked list would function in the same fashion, but we are going to leave it as an integer for simplicities sake.
The second data member is this struct node *next. This is a pointer to a node, or at least it will be eventually, as we build our list. Now neither of these need to be initialized here, because in reality, they do not exist yet. Remember, there will be a separate set of these variables for each node we create, each accessed via the name of that node. This will not be a problem for us, as we will never actually access the nodes directly, all of our external functions will utilize the list structure.
Here is the list structure:
/* List Structure */
struct list {
struct node *start;
};
Now, one may question the choice of creating a structure with only one data member. I found it a bit clearer to allow the programmer to think of the list as a collection itself. The pointer inside of it being the first member of the list. Also, it should be clearer as to how to go about managing multiple linked lists if there is some structure representing each individual list. Therefore, this structure is optional, but I believe that it is optimal, and will be using it in this tutorial.
Ok. So where do we go from here. Let's think about list operations. What do we want to be able to do? Well, here is a short list:
--> Initialize the list
--> Push a value onto the list
--> Pop a value off of the list
--> Print the list
Great! So where to start from here? Well, what do we want to do first in our program? We want to initialize the list. We therefore have the following function prototype, which should be placed under our include statements, and above the structure definition:
void InitList(struct list *sList);
Which takes a pointer to a linked list, and returns nothing.
If you have ever written a linked list in C++, you will know that the constructor of the list needs to set the start pointer to NULL. So, in C, we do just that. Think of InitList as our constructor in a way, though we are not constructing an object. In C++, the constructor would be called as the object was declared. In C, we do not have this functionality, and thus must have a function call after the structure declaration. You will see this when we write a sample main function to go along with this.
Here is what the function InitList looks like:
/* Initializes the list structure */
void InitList(struct list *sList)
{
sList->start = NULL;
}
It is not technically initializing a list structure, but it is setting the structure data member, this pointer to a node structure, to NULL, which is exactly what we would have done in a C++ class constructor.
The -> operator is used here instead of a . because we are using a pointer to a list instead of a physical list itself. It should be obvious why we are using pointers. This allows us to make changes to the list from different scopes. For example, if I declare a list in main, I want to be able to make changes to it from outside of the scope of main. Using a pointer allows this to happen.
Ok, great, we have a function that will make sure we have an empty list. Now what? Let us move on to adding a value onto the list. The term Push is used, which to the extent of my knowledge comes from Assembly programming, but we will not get into that.
So how do we push, or add, a value to the beginning of this list. Well, let's think about this.
We want to do the following:
--> Create a new node
--> Add the node to the beginning of the list.
This seems simple, yes? We do, however, come across a slight complication. What happens when we exit the function, if we were to just declare something like struct node p? It gets deleted. So, what we are going to do is create a node pointer, allocate memory at that pointer to be the size of a node object, and then add it to the list. So, how do we do that?
Well, let's see the prototype and the function first, and go from there.
The prototype looks like this:
void push(struct list *sList, int data);
This has the same first argument as InitList, and has a second argument that will take on the value to set our data member in our node to.
Our function definition looks like so:
/* Adds a value to the front of the list */
void push(struct list *sList, int data)
{
struct node *p;
p = malloc(sizeof(struct node));
p->data = data;
p->next = sList->start;
sList->start = p;
}
The first line after the { looks pretty simple, it declares a new node pointer called p. The second line looks like a complete mess, but is pretty easy to understand once it is broken down. malloc is one of the reasons why we included the standard library header file. It returns a pointer to an allocated amount of space the size of it's argument. Here, we specify that it should be the size of a node structure. The code in the argument should make sense to you now.
We can then set p->data and p->next to their new values. Once again, the -> operator is used as we are working with pointers. p->data becomes data, the second argument of our function, and p->net becomes the old first node on the list, which will be sList->start. We then need to set sList->start to p, so that we constantly have a pointer to the first node in our list in the list structure. Make sense? Good!
So now that we have a way to add to the list, let us look at a way to remove from the list, or pop a value off of the list. When I initially wrote this linked list, I declared my pop function as a void. You may find it more useful as an int, in order to return the value popped off. Once you see the code, I am sure you will be intuitive enough to figure out how to do so. Leave a comment if you cannot figure it out, and I will post the modified pop function. In not wanting to mess with my current well functioning code, I will keep it here as a void function.
Here is the prototype, who's argument should be of no surprise to you:
void pop(struct list *sList)
Once again, this, like all the prototypes, should be placed after your include statements.
And, here is the function declaration.
/* Removes the first value of the list */
void pop(struct list *sList)
{
if(sList->start != NULL) {
struct node *p = sList->start;
sList->start = sList->start->next;
free(p);
}
}
The first thing we want to do is make sure that the list is EMPTY. Failure to do so can result in a SEGMENTATION_FAULT. Those are not nice. This is the purpose of the if statement. We then create a pointer to a node, and set it to the memory address of the current first node. We then set our start pointer to that of the second node in the list (or null if one does not exist) and then free the memory that was allocated for the node pointed to by p. This function free is also from the standard library header file.
Finally, we want a method that will allow us to print off the entire list.
Here is the prototype:
void print(struct list *sList)
And here is the function definition:
/* Prints the list */
void print(struct list *sList)
{
struct node *p = sList->start;
while(p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}
The way this works is that we start from the first node in the list, and then for every node in the list, we print off it's data member, and then move to the next node (p=p->next;). If we find the end of the list, i.e. wherever p = NULL, we are done, and we exit out of the function.
With all that being said, here is the entire program including a main function so that you may see it in action:
#include<stdio.h>
#include<stdlib.h>
// Prototypes
void InitList(struct list *sList);
void push(struct list *sList, int data);
void pop(struct list *sList);
void print(struct list *sList);
/* Node Structure */
struct node {
int data;
struct node *next;
};
/* List Structure */
struct list {
struct node *start;
};
int main(int argc, char** argv)
{
int x;
struct list MyList;
InitList(&MyList);
for(x = 0; x < 100; x++) push(&MyList, x);
print(&MyList);
printf("\n");
for(x = 0; x < 25; x++) pop(&MyList);
print(&MyList);
printf("\n");
for(x = 0; x < 80; x++) pop(&MyList);
print(&MyList);
printf("\n");
return 0;
}
/* Initializes the list structure */
void InitList(struct list *sList)
{
sList->start = NULL;
}
/* Adds a value to the front of the list */
void push(struct list *sList, int data)
{
struct node *p;
p = malloc(sizeof(struct node));
p->data = data;
p->next = sList->start;
sList->start = p;
}
/* Prints the list */
void print(struct list *sList)
{
struct node *p = sList->start;
while(p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}
/* Removes the first value of the list */
void pop(struct list *sList)
{
if(sList->start != NULL) {
struct node *p = sList->start;
sList->start = sList->start->next;
free(p);
}
}
I hope you have learned something. If you have any questions, please, leave a comment.
Peace
~Bodom
MultiQuote
. And err, aren't push and pop for stack ADT ?
| 