Page 1 of 1

Linked List using Structures in C Creating a Stack of integers in C Rate Topic: -----

#1 bodom658  Icon User is offline

  • Villiage Idiom
  • member icon

Reputation: 113
  • View blog
  • Posts: 1,123
  • Joined: 22-February 08

Posted 19 April 2009 - 12:02 AM

First of all, I would like to make note that this is not a C++ Tutorial, this is a C tutorial.

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

Is This A Good Question/Topic? 3
  • +

Replies To: Linked List using Structures in C

#2 tarmizi_adam2005  Icon User is online

  • جوروترا

Reputation: 233
  • View blog
  • Posts: 842
  • Joined: 18-April 09

Posted 20 April 2009 - 03:05 AM

Nice tutorial u have here, easy to understand.. unlike my professor in data structure class :D. And err, aren't push and pop for stack ADT ?
Was This Post Helpful? 0
  • +
  • -

#3 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3105
  • View blog
  • Posts: 19,144
  • Joined: 14-September 07

Posted 20 April 2009 - 10:02 AM

You can push and pop in a list as well. It just doesn't "have" to follow LIFO rules.
Was This Post Helpful? 0
  • +
  • -

#4 bodom658  Icon User is offline

  • Villiage Idiom
  • member icon

Reputation: 113
  • View blog
  • Posts: 1,123
  • Joined: 22-February 08

Posted 20 April 2009 - 10:28 AM

KYA is correct. As the years have passed, push and pop's ambiguity has grown, and they are now acceptedly used for adding and removing values from a list. This can be seen in the Vector class for C++, which utilizes Push_Back and Pop_Back, among others.
Was This Post Helpful? 1
  • +
  • -

#5 SHENGTON  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 112
  • Joined: 10-October 08

Posted 19 August 2010 - 12:59 AM

Hello,

What's the meaning of this lines bodom658? I'm still a student and very newbie with this. Hope you can explain it to me line by line. Thanks! :)

int main()
{
	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;
}


and this code to:
void InitList(struct list *sList)
{
	sList->start = NULL;
}

Was This Post Helpful? 0
  • +
  • -

#6 bodom658  Icon User is offline

  • Villiage Idiom
  • member icon

Reputation: 113
  • View blog
  • Posts: 1,123
  • Joined: 22-February 08

Posted 15 September 2010 - 06:29 PM

View PostSHENGTON, on 19 August 2010 - 02:59 AM, said:

Hello,

What's the meaning of this lines bodom658? I'm still a student and very newbie with this. Hope you can explain it to me line by line. Thanks! :)

int main()
{
	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;
}


and this code to:
void InitList(struct list *sList)
{
	sList->start = NULL;
}


Hey, sorry it took so long to reply, apparently I don't get email from these....
The main function is just a sample showing how the list works. x is an index variable for the for loops that manipulate the data in the list (pushing and popping from it)

The InitList function can be thought of the list's constructor. It sets up the list so that the start or head of the list is a null pointer. That way, we don't have any undefined behavior. It's a safety thing.

Back in the main function, the first for adds 100 items to the list, then the print function prints them out. The second for removes 25 items, and the third removes the rest, and demonstrates the safety measures built in to the pop function, so that we do not try to pop off non existant values.

More questions? Just ask!
Was This Post Helpful? 0
  • +
  • -

#7 slash9x  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 24-November 10

Posted 24 November 2010 - 05:22 PM

Hey, thanks for the tut bodom658. I'm trying to make a linked list myself also. But I run into a segmentation fault when compiling the code. Can you help me figure where the problem is?

#include <stdio.h>
#include <stdlib.h>

struct Profile{
       unsigned number;
       char name[75];
       char email[50];
       float GPA;
};

struct node{
       struct Profile student;
       struct node* next;
};

void initList(struct node* head){
     head->student.number = 1;
     printf("Enter student's name:");
     scanf("%s", head->student.name);
     printf("Enter student's email:");
     scanf("%s", head->student.email);
     printf("What is the student GPA?");
     scanf("%f", &(head->student.GPA)); 
     head->next = NULL;
}

int main(){
    struct node* list;
    initList(list);
    printf("%s", list->student.name);
    return 0;
}


This post has been edited by slash9x: 24 November 2010 - 05:30 PM

Was This Post Helpful? 0
  • +
  • -

#8 bodom658  Icon User is offline

  • Villiage Idiom
  • member icon

Reputation: 113
  • View blog
  • Posts: 1,123
  • Joined: 22-February 08

Posted 06 April 2011 - 06:57 AM

View Postslash9x, on 24 November 2010 - 09:22 PM, said:

Hey, thanks for the tut bodom658. I'm trying to make a linked list myself also. But I run into a segmentation fault when compiling the code. Can you help me figure where the problem is?

#include <stdio.h>
#include <stdlib.h>

struct Profile{
       unsigned number;
       char name[75];
       char email[50];
       float GPA;
};

struct node{
       struct Profile student;
       struct node* next;
};

void initList(struct node* head){
     head->student.number = 1;
     printf("Enter student's name:");
     scanf("%s", head->student.name);
     printf("Enter student's email:");
     scanf("%s", head->student.email);
     printf("What is the student GPA?");
     scanf("%f", &(head->student.GPA)); 
     head->next = NULL;
}

int main(){
    struct node* list;
    initList(list);
    printf("%s", list->student.name);
    return 0;
}



Hi,

It looks like you are trying to assign to the pointer of a structure without actually assigning any memory to it, which is going to generate the segfault you are getting. Check out the 'malloc' function from <stdlib.h> . basic use: struct node* mynode = (struct node*)malloc(sizeof(node));
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1