Page 1 of 1

C++ Linked Lists & Custom Linked Lists: Part 1 Implementations of a Data Structure Rate Topic: ***** 2 Votes

#1 mattman059  Icon User is offline

  • Epic Awesomeness
  • member icon

Reputation: 15
  • View blog
  • Posts: 538
  • Joined: 23-October 06

Posted 07 August 2007 - 03:10 PM

*Note* A prerequisite to this tutorial requires that you be comfortable with pointers, linked lists (not STL), and Classes/Objects. If you're not sure about it, born2code has a good tutorial about Data structures on this website. Before we begin talking about making your own linked list I am going to explain some of the more intricate parts of a linked list. Lets take a look at what the typical linked list looks like:


[head] -> [data member|pointer]->NULL




The typical linked list has three parts, the list head, the data members, and the pointer which enables you to access the next (and sometimes previous) data members.


In C++ you create linked lists using the struct keyword. Doing this enables you to create a data type with specific characteristics which can include any other kind of data type. Lets take a look at how to declare one. This specific linked list will be called Student and will hold a name, gpa, as well as the number of course hours a student is enrolled in:

struct Student
{

   string name; // or char name[] with the max number of characters allowed in a name
   double gpa;
   double cur_Hours;
   Student *next;  //pointer to the next student
};




Looking at this code you'll notice a few things. First off the semicolon after the closing bracket is extremely important. If you're familiar with class declarations you know that the ending semicolon is probably more important than even the code inside the class; because basically all a struct is, is a small scale class with no member functions. Second you'll notice the data type on the pointer next is Student. That is because linked lists are known as Self Referential, this allows you to create pointers that point to other Students. If you're using Object Oriented Programming (OOP) then the struct declaration would go int your header file for the class in the private section. Now lets get in some new terminology:

head = This is the front of the list, if you start with an empty list, then this will be equal to NULL.
node = These are the data members that we mentioned earlier: name, gpa, cur_Hours are all nodes.



The first thing you do after declaring the struct for the linked list is create the pointer for the head of the linked list, and initialize it to NULL; this will give you an empty linked list.

Student *head;
head = NULL;   



You could put both of them on one line to save some room, but if you're using classes then the initialization would go in your constructor like this :

public:
  Classroom();
	 { head = NULL; }

...



This is referred to an in-line declaration and should not be used very much because often times it can cause lower performance if you put too much in the header file.
That's what the implementation (className.cpp) is for.

You can have as many heads as your particular linked list requires but make sure to alter their names to distinguish between them (ex. down_head, back_head, head2...etc).

Now lets talk about creating new nodes to add to our list. For an empty list, this is a fairly simple task involving only two steps: 1) check if the list is empty, 2) make head point to the new node. When creating new nodes you should do a couple of things to it. First of all you should assign all of its values and secondly make sure that the next pointer points to NULL.
Let's look at how to do this:

Student *newStudent;
Student *Student_ptr;

newStudent = new Student;
newStudent->name = "Matt"
newStudent->gpa = 3.5;
newStudent->cur_Hours = 18.0;
newStudent->next = NULL;

 




Okay, a few things happened here that may confuse you: what is Student_ptr? What is the first initialization statement doing? What is the -> symbol doing?
So lets take these one at a time. Student_ptr will come in handy later on when we no longer have an empty list. It will traverse (move through) the list until it finds the end and place the student in that spot. The first initialization statement is saying that we are allocating enough memory in the OS to hold onto a student. You may have seen the new statement when discussing or studying Dynamic Arrays. And finally the -> symbol does the exact same thing as the dot operator (my.name = "Matt") except adopts it into the object orientedness of structs and classes. Because not only are you accessing members of the structure but you're dealing with pointers if you're using VC++ Express or any VC++ you would get this error:



1> type is 'main::ListNode *'

1> did you intend to use '->' instead?





This means that because your manipulating a pointer variable you need to use the -> operator instead.

Okay now we have a newStudent to add to our list. Let's first check to make sure the list is empty:

if (!head)
   head = newStudent;



Pretty straight forward. "if (!head)" basically translates into "if (head == NULL)" and that indicates that head points to NULL and your list is empty, so it appends the new student after the head. Just a note to be careful when you talk about adding nodes to a list, when you place a node at the end it's called appending, and when you put a node into a list it's referred to as inserting. So what happens if you're putting a student into the classroom when there's already 20 students? Assuming that you're not concerned with alphabetical ordering you would need to modify the if statement above to include an else in which you would instruct the compiler to search the list for the end and place the student there. Lets see how this looks:

if(!head)
  head = newstudent;
else
{

  Student_ptr = head;
  
  while(Student_ptr -> next)
	 Student_ptr = Student_ptr -> next;

  Student_ptr->next = newStudent;
}




So what this code segment does is assigns that Student pointer from earlier to the location of the head pointer for the list, and since we've already mentioned that we have 20 students, we know the list is not empty so the while statement evaluates the value of Student_ptr->next which will either return a value (the location of the next node) or NULL and if it returns a value then Student_ptr is assigned that value until the while statement returns NULL in which case Student_ptr->next will be assigned as newStudent.

So lets look at what we've got so far, the following will be a non-OOP approach to this program.

#include <iostream>
#include <string> //not necessary if you use char arrays

using namespace std;

int main()

{
  struct Student
   {

	  string name; // or char name[] with the max number of characters allowed in a name
	  double gpa;
	  double cur_Hours;
	  Student *next;  //pointer to the next student
   };


	  Student *head;
		 head = NULL;   

   
	  Student *newStudent;
	  Student *Student_ptr;
			newStudent = new Student;
			newStudent->name = "Matt"
			newStudent->gpa = 3.5;
			newStudent->cur_Hours = 18.0;
			newStudent->next = NULL;

 

	if(!head)
	 head = newStudent;
   else
   {

	 Student_ptr = head;
  
	 while(Student_ptr -> next)
		Student_ptr = Student_ptr -> next;

	 Student_ptr->next = newStudent;
   }

return 0;

}



For now this program does nothing but build the list. Now what we're going to do is apply what we've just learned and ask the user to input the information for 2 students (this number can be changed for your own interest) and then we'll discuss how to display the list as is.

 string S_name;
 double S_GPA;
 double S_Hours;

for (int i = 0; i < 2; i++)

{
   cout << "what is the students name: ";
   cin >> S_name;

   cout << "what is "<< S_name << "'s gpa";
   cin >> S_GPA;

   cout << "How many hours is "<< S_name <<" enrolled in?";
   cin >> S_Hours;
}



Hopefully none of this needs much explanation, basically you declare three variables to get user input, and then you get that input from them. Now lets take this and apply it to our previous code.

Basically, this peice of code:


newStudent = new Student;
newStudent->name = "Matt"
newStudent->gpa = 3.5;
newStudent->cur_Hours = 18.0;
newStudent->next = NULL;



Becomes this peice of code:



newStudent = new Student;

newStudent->name = S_name;

newStudent->gpa = S_GPA;

newStudent->cur_Hours = S_Hours;

newStudent->next = NULL;



Also, when you put it all together, all of the code from getting the user input, all the way through appending the new student to the end of the list, all goes in between the brackets of the for statement like so:



string S_name;

double S_GPA;

double S_Hours;

for (int i = 0; i < 2; i++)

{

cout << "what is the students name: ";

cin >> S_name;

cout << "what is "<< S_name << "'s gpa: ";

cin >> S_GPA;

cout << "How many hours is "<< S_name <<" enrolled in?: ";

cin >> S_Hours;

 

Student *newStudent;

Student *Student_ptr;

newStudent = new Student;

newStudent->name = S_name;

newStudent->gpa = S_GPA;

newStudent->cur_Hours = S_Hours;

newStudent->next = NULL;

if(!head)

head = newStudent;

else

{

Student_ptr = head;

 

while(Student_ptr -> next)

Student_ptr = Student_ptr -> next;

Student_ptr->next = newStudent;

}

cout << endl;

}



I've added an end line after each entry to the list so that the output looks nicer. So now you've got a pretty good linked list going on here. So say you want to be able to display this list on the screen. Well basically all we have to do is traverse the entire list one node at a time (which we've done before) and print that node with all of it's data members associated with it. Lets take a look at what you're going to need:

1) a pointer to move through the list ( for simplicity let's declare a new one something like Display_ptr will work)
2) knowledge of how to move through the list
3) knowledge of how to access data stored in a node (-> operator)

lets look at some code:


Student *Display_ptr;
Display_ptr = head;

while (Display_ptr)
{
   cout << Display_ptr->name << endl;
   cout << Display_ptr->gpa<< endl;
   cout << Display_ptr->cur_Hours<<endl;

 

  Display_ptr = Display_ptr->next;
  cout << endl;
}




now this code travels through the list while Display_ptr is not equal to NULL and prints out all of the information associated with the node at that location. After displaying the information the pointer increments to the next student's record, and a new line is inserted.

SO that's all there is to creating, and displaying a typical linked list with user input. Next I would like to delve a little deeper into linked lists and explain some theoretical ideas behind custom linked lists (which can be very powerful and quite frustrating!) So take a break if you need one and come right back!


Okay, after taking a break from the basics we're ready to embark on a quest through the pleasure that is custom linked lists, home to all things annoying such as pointers and references to previous nodes as well as other types of references so lets get to it!

First let's talk about doubly linked lists. These are linked lists of the form:

[head]-> <-[prev|data|next]-> <-[prev|data|next]-> NULL



and the only difference between this type of linked list and the one that we just finished talking about is that not only do you need to keep track of the next node in the list but also the previous node. Often times this requires the use of two traversing pointers, not just one like the Student_ptr or Display_ptr that we used previously. Yet another type of custom linked list is called a circular linked list in which the last node in the list points to the front of the linked list. I personally have not done much work with this type of linked list, but let's try to come up with a way to look at these types of lists.
[head] -> [data|next] -> [data|next] -> [data|next]
				|												  |
			   [next|data] <-[next|data] <-[next|data]




From what it seems like, you would have to keep track of the front of the list somehow, either by using some mathematical manipulation of the number of nodes or if you know that a certain node is going to be the last node you can set it's next pointer to head which would allow it to refer to the first node in the list. Like i said I'm no expert on circular linked lists, what research i have done is not much so i encourage you to research them yourself and find out how to make them work in your applications.

Now let's talk about something that I have a personal interest in: C++ and Graphs (networks).
Anyone familiar with a class on Data Structures or Discrete Mathematics will understand what the term Graph Theory represents. It is a culmination of definitions and rules that define how to create networks of things (called sets) and how to determine the similarities between them. What we're going to do now is talk about one method of representing a graph (or network). It is called an Adjacency List. More specifically we'll be using Adjacency lists with a simple connected graph.

Let's define what a simple graph is:
"A graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices"
-Discrete Mathematics and its applications 6th ed. Rosen

Basically this is what it says:
If you have a graph G with vertices u and v then there is a unique edge e such that G(u,v) is the only connection that that edge makes. This says that it is possible to have the following pairings : G(u,v) or G(v,u). But it is impossible to have either of these: G(u,u) or G(v,v).

Now what we're building is an Adjacency list for a graph G. This is a list of each vertex along with each of the vertices that are adjacent (no more than one edge away) to that vertex.

Ex.
[Vertex] [Adjacent Vertices]
	 A			 C,B,E
	 B			 C
	 C			 A,B,E
	 D			 E
	 E			 A,C


If you draw this out on paper (which is best as it is hard to draw on the computer) you will see that the letters in the second column are exactly one edge away from the vertex in the left column.

Now our job is to create a linked list with this data so that it can be interpreted and analyzed later on in the form of an adjacency list.

The types of linked lists we'll be dealing with now look like this:

					[down_head]
					   |
[head]  -> [Vertex|pointer] -> etc.
	|				 |
  NULL		   [Edge]
					  |
					[Edge]
					  | 
					 NULL




Now each vertex will be the head of it's own list consisting of all of the edges associated with that vertex. So since we've already discussed how to create linked lists, let's see if we can make one that looks like this. But this time, we'll use the object oriented approach to make our code a little bit easier to read and understand later on for modification purposes.

Our header file will consist of the class declaration, our constructor, our struct for the linked list, and two functions 1) Build_Network() 2) Display() both of which are void type since they need not return anything. The header file will also contain the head pointers for our linked list as well as their initializations. So lets take a look:

#ifndef GRAPH_H  //This checks the preprocessor to see if GRAPH_H has been defined and if it hasnt then it defines it as follows.
#define GRAPH_H

using namespace std;

class Graph

{

 

   private:
  

	 struct ListNode

	 {

		string name;

		struct ListNode *next;	  //This creates the same ListNode structure for the next and down pointers each one will have a name, a next, and a down.

		struct ListNode *down;

	  };



	   ListNode *head;

	   ListNode *down_head;

 

	public:


	  Graph() //Constructor

	  {

		 head = NULL;	 //in-line initializations of head and down_head

		 down_head = NULL;

	  }

 

		 void Build_Network(); //This function will prompt the user for all of the information, as well as perform the necessary linked list operations

		 void Display();		  //This function will print out the linked list in a manner that is easily read.



};

 

#endif //Ends the definition of GRAPH_H




Pretty straight forward so far eh? Create the ListNode which will hold onto our linked list items (Vertices and Edges), initialize both of the head pointers to NULL so that they are empty lists and Define the two functions in the public area.

In order to build our graph (or network) we'll be using the same method that we used for the students, setup a for loop that continues for how ever many vertices that the user indicates. But there is one catch here, after each vertex, we need to get the number and name of each of the edges/vertices that are adjacent to that vertex. So what we'll do is setup a nested for loop so that after we get the information for the vertices we can get the number of edges/vertices that are adjacent to that vertex as well. So in your Graph.cpp file you'll want to write code similar to the following:


void Graph::Build_Network()

{

   ListNode *newNode;  //This is the new vertex

   ListNode *nodePtr;   //Traversing pointer

   ListNode *downPtr;  //Edge/Adjacent Vertex Traversing pointer


   int num_Nodes;

   string V_Name; 

 

	cout << "How many nodes in the graph?: ";

	cin >> num_Nodes; 

 

	 for(int i = 0; i<num_Nodes; i++)

	  {

		 cout << "What is the name of this vertex?: ";

		 cin >> V_Name;

		 newNode = new ListNode;

		 newNode->name = V_Name;

 

		 newNode->next = NULL;

		 newNode->down = NULL;

// Building the Vertex List

		 if(!head)

			head = newNode;

		 else

		 {

			nodePtr = head;

			while(nodePtr->next)

			nodePtr = nodePtr->next;

			nodePtr->next = newNode;

		   }


		   int num_Edges;


			cout << "How many Edges are connected to " << V_Name << "?: ";

			cin >> num_Edges;


		for(int j=0; j<num_Edges; j++)

		 {

			string E_Name;

			cout << "What is the name of edge "<< j+1 << "?: ";

			cin >> E_Name;


			ListNode *downNode;

			down_head = newNode->down;

			downNode = new ListNode;

			downNode->name = E_Name;

			downNode->down = NULL;

//Building the Adjacent Vertex List

			if(!down_head)

			{

			   newNode->down = downNode;

			   down_head = downNode;

			}

			else

			{

			   downPtr = down_head;


			   while(downPtr->down)

					 downPtr = downPtr->down;


			  downPtr->down = downNode;

			}

		 }

	   }

	 }




Basically that's all there is to building the Adjacency linked list. Nothing really new was added there except for the down_head and downPtr that turned each data member of the Vertex linked list into a linked list of its own. Now let's get to work on how to display a linked list that has this kind of data. Naturally you'll notice that you'll need to use more than one traversing pointer because of the manner in which we created the list.


Pretty much the same thing goes here as it did for building the list. Nest the display so that you display a vertex followed by each of it's adjacent vertices/edges until all data has been printed. The comments will explain what the function is doing.



void Graph::Display()

{

   ListNode *nodePtr; //Vertex traversing pointer

   ListNode *downPtr; // Adjacent list traversing pointer

   nodePtr = head; // set to the beginning of the list


	while(nodePtr)  //continue through all vertices

	{

		 downPtr = nodePtr->down; // using the fact that each vertex has an adjacent vertex set this equal to the first vertices down data member

		 cout << nodePtr->name << "->";

 

		 while(downPtr) // continue through all Adjacent edges/vertices

		 {

			cout << downPtr->name << "->";

			downPtr = downPtr->down; //Increment the Adjacency pointer

		 }


			cout << "NULL"<<endl;

			nodePtr = nodePtr->next; // Increment the Vertex pointer.

	  }

}


And now when you write the actual program all you need to do is define a graph (say Graph a) and using dot notation you can call the functions that are associated with data of type "Graph" just like so:

[code]
a.Build_Network() //This will call the function to build the network using an Adjacency list.
a.Display() //This will print the Adjacency List.



I hope that I can submit more on this topic later, Graph Theory is an area of interest to me, so I am hoping to implement this program into analyzing graphs for their properties as well. Guess you'll have to wait for part II for that information though.

Any questions or comments can be sent to me through private messages on D.I.C.

Is This A Good Question/Topic? 0
  • +

Replies To: C++ Linked Lists & Custom Linked Lists: Part 1

#2 Jayman  Icon User is offline

  • Student of Life
  • member icon

Reputation: 418
  • View blog
  • Posts: 9,532
  • Joined: 26-December 05

Posted 08 August 2007 - 05:41 AM

Very well written...I look forward to seeing Part 2. :)
Was This Post Helpful? 0
  • +
  • -

#3 mattman059  Icon User is offline

  • Epic Awesomeness
  • member icon

Reputation: 15
  • View blog
  • Posts: 538
  • Joined: 23-October 06

Posted 23 August 2007 - 07:01 PM

Sadly Part Two must be postponed due to the fact that classes have started back. But lucky for anyone out there who was actually looking forward to part II : I'm currently taking a data structures class in which 3 weeks is devoted to the graph structure! so i am HOPING by the end of october or november to have part II done. Sorry if this upsets anyone (heh..right, anyway). But I will get started on it ASAP.


Thanks.!
Was This Post Helpful? 0
  • +
  • -

#4 compufatwa  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 21-November 07

Posted 21 November 2007 - 07:31 AM

very nice , looking forward to read part two
Was This Post Helpful? 0
  • +
  • -

#5 brokensoul  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 02-November 07

Posted 06 December 2007 - 10:42 PM

wow, i take a deep breath wile scrolling down your code,
Nice representation and nice code , looking forward ......
newbie here :P :P :D

This post has been edited by brokensoul: 06 December 2007 - 10:45 PM

Was This Post Helpful? 0
  • +
  • -

#6 nirvanarupali  Icon User is offline

  • D.I.C Stomach
  • member icon

Reputation: 13
  • View blog
  • Posts: 1,119
  • Joined: 01-August 07

Posted 09 December 2007 - 11:46 PM

why there is no need to delete newStudent ?
Was This Post Helpful? 0
  • +
  • -

#7 mattman059  Icon User is offline

  • Epic Awesomeness
  • member icon

Reputation: 15
  • View blog
  • Posts: 538
  • Joined: 23-October 06

Posted 10 December 2007 - 05:56 AM

View Postnirvanarupali, on 10 Dec, 2007 - 12:46 AM, said:

why there is no need to delete newStudent ?


You could delete newStudent if you wanted to ( and if you were using a program that would stay open for a while you probably should) the only reason I didnt delete it was because i simply didnt think about it :P. Theres no other reason than my not paying attention haha. But you could delete it, or leave it depending on how your program will run. If your program was to stay open and you keep creating "newStudent" 's then you could possibly cause a memory leak, but the ammount of times youd have to use the "new" command to get that effect, especially in todays market with single sticks of ram with capacities into 4gb, I dont think it would be that big of a deal





PS. I've started my research for part 2, gotta finish up finals and then im on it ;D
Was This Post Helpful? 0
  • +
  • -

#8 mattman059  Icon User is offline

  • Epic Awesomeness
  • member icon

Reputation: 15
  • View blog
  • Posts: 538
  • Joined: 23-October 06

Posted 02 January 2008 - 09:57 PM

View Postmattman059, on 10 Dec, 2007 - 06:56 AM, said:

View Postnirvanarupali, on 10 Dec, 2007 - 12:46 AM, said:

why there is no need to delete newStudent ?


You could delete newStudent if you wanted to ( and if you were using a program that would stay open for a while you probably should) the only reason I didnt delete it was because i simply didnt think about it :P. Theres no other reason than my not paying attention haha. But you could delete it, or leave it depending on how your program will run. If your program was to stay open and you keep creating "newStudent" 's then you could possibly cause a memory leak, but the ammount of times youd have to use the "new" command to get that effect, especially in todays market with single sticks of ram with capacities into 4gb, I dont think it would be that big of a deal





PS. I've started my research for part 2, gotta finish up finals and then im on it ;D





As much as I regret to have to admit this, part 2 is postponed indefinatly...The research that I have done for part 2 ammounts to very little (though many hours were put into it)...This comes with my recent change of major to Business Info. Systems from CS...The challenges presented proved to be greater than I had anticipated. So i appologize to all who wanted a part 2. Anyone is absolutely more than welcome to take it upon them self to produce part 2.


Thanks.

= \
Was This Post Helpful? 0
  • +
  • -

#9 azkal  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 22-October 08

Posted 22 October 2008 - 07:47 PM

mattman059

hi, i was trying to run your Adjacency List program on Visual C++, but i was not able to run it.

I am new to C++, could you help me out, i want to execute the adjacency list program

Thank you.
Was This Post Helpful? 0
  • +
  • -

#10 mattman059  Icon User is offline

  • Epic Awesomeness
  • member icon

Reputation: 15
  • View blog
  • Posts: 538
  • Joined: 23-October 06

Posted 23 October 2008 - 05:14 AM

I would be glad to help you out

What compiler are you using? I created this code in Visual Studio 2005.
Was This Post Helpful? 0
  • +
  • -

#11 azkal  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 22-October 08

Posted 24 October 2008 - 02:53 PM

well i am using visual C++ 2008 Express Edition.

i want exactly the output that you are getting
with vertex and adjacency list.

thanks
Was This Post Helpful? 0
  • +
  • -

#12 snowg  Icon User is offline

  • New D.I.C Head

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

Posted 01 November 2008 - 03:10 AM

in case that istead of string name we had char name[] how would the following change?

newStudent->name = "Matt"
Was This Post Helpful? 0
  • +
  • -

#13 autumn_storm2216  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 04-August 09

Posted 07 August 2009 - 03:49 AM

how are you going to do the linked list if your using three structures as follows:
struct Student{
char fname[40];
char lname[40];
char mname[40];
char course[20];
char id[20];
int age;
int year;
};

struct node{
Student *item;
node *next;
};

struct subject{
node *head;
char name[20];
int size;
};

with the different functions such as:
bool enrol(subject&, Student);
bool drop(subject&,Student);
bool searchID(subject&, char[]);
...

can you help me??
this is my problem
Was This Post Helpful? 0
  • +
  • -

#14 memaine  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 03-September 09

Posted 03 September 2009 - 05:30 PM

:^: :bigsmile: that was great..!
unfortunately,i have to prepare for school as of this time...
i'll be right back this evening and continue reading...
please continue enlightening the amatuers...
like me, i ABSOLUTELY don't have any idea about this...
aside from linked list, i also have to study stacks and queues...
thank you so much!!!!! :bigsmile: :^:
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1