Free Web Hosting by Netfirms
Web Hosting by Netfirms | Free Domain Names by Netfirms

Lesson 8



Linked Lists
Linked lists are multiple blocks of data, like an array of structures or classes. Each block(struct,class) is linked to another with a pointer. You can implement as many pointers as you wish, you can have pointes pointing to the next block, the previous the top, the tail whatever you wish. Linked lists are created using dynamic memory (previous lesson). Creating and understanding a linked list for the first time takes time, patents and a logical way of thinking. To get an idea of a linked list in a physical represention, think of each block as being a small square piece of paper, which can have writing (data) on it. Now get many of these bits of paper, line them up 1 after the other on the ground. At the bottom of each is a pointer, this points to the next bit of paper (block), until the last block which points to null or 0. Each of these pointers are called a next node, a previous node is one that points backwords (to the block before it). Another common way of thinking of this is a train, each list is a seperate carrage, where the *Pointer in the example below is you.
Example

#include<conio.h>
#include<iostream.h>

struct List
{
	int data;
	List *next;			//A pointer to a list - will point to next list soon
};

void main()
{
	List *Pointer,*tail,*head;	//Pointer=what we access data with, tail is 1st list, head is last list
	Pointer=new List;		//Create a new List
	tail=Pointer;			//tail points to 1st List
	Pointer->data=5;		//Put some data into list 1 (first list)
	Pointer->next=new List;		//Make 1st lists pointer point to a new List (think logicaly, use paper example)
	Pointer=Pointer->next;		//Key line!  This makes pointer point to the 2nd list, so now we are in List 2
	Pointer->data=10;		//Put some data into list 2
	Pointer->next=new List;		//Create a 3rd List
	Pointer=Pointer->next;		//Point to 3rd list
	Pointer->data=15;		//Put some data into 3rd list
	Pointer->next=new List;		//Create a 4th list
	Pointer=Pointer->next;		//Point to 4th list, now we are inside list 4 with Pointer
	Pointer->data=20;		//Put some data into the 4th list
	Pointer->next=0;		//This is the last list, so make next = null or 0
	head=Pointer;			//Point to the head of the list - last one with head
	Pointer=tail;			//Go back to the start of the list again (list 1)
	while(Pointer->next!=0)		//while not at last list
	{
		cout << "Data is: " << Pointer->data << endl;	//Output lists data
		Pointer=Pointer->next;				//Go to next list - key line
	}
	cout << "Data is: " << Pointer->data << endl;	//Output final lists data, as the loop exits before the final list
	getch();
}
Yes this may be quite tricky first time, but it does get easier. Just try to use the paper analogy to master it.
1st I created a simple struct, I put a pointer in it (*next) which was a pointer to a list, and would point to the next list. Then in the main function I created 3 pointers - *Pointer, this is the main pointer as it is the 1 we use to access data with and travel through each list and link with, think pointer as youself when your in a train, you have to go through each link to get to the other carrage, with 1 exeption here I made a link directly to the engine (1st list - tail) so I could jump from the last carrage(4th list) to the engine(1st list), as I did not have previous links only next so I could only travel down the train carrages, not up. I had a tail pointer which pointed to the engine(1st list), and I had a head pointer which pointed to the last list (end carrage) or 4th list in this case. One thing that is not completed with this list and ill show you soon, is I have not deleted the lists again, as I am using dynamic memory I should delete my pointers (Lists) after use.

Now ill create a linked list which contains both next and previous pointers (these are called nodes). Also I will delete the lists when Ive finished with them, by tradition the last list you create(end one) is the 1st you delete, this is so your lists dont go walking off on you if you loose a link to them, like say in the list above, you deleted the 2nd list, then you would have lost the 3rd and 4th list, gone forever, that is bad. But since we are going to have a previous pointer in our next linked list, its not so important, but again its good to get into the habbit of deleting the last one first, then the 2nd to last then the 3rd to last ...... and so on.
Example

#include<conio.h>
#include<iostream.h>

struct List
{
	int data;
	List *next,*prev;			//Pointers to the next list and previous list
};

void main()
{
	List *Pointer,*temp;			//Pointer is where you are currently at (which carrage).
	int loop=0;
	Pointer=new List;			//Create 1st list
	Pointer->prev=0;			//No previous list, so set it to 0
	Pointer->data=5;			//Put some data into 1st list
	while(loop<5)
	{
		Pointer->next=new List;		//Create new list and point to it with next
		Pointer->next->prev=Pointer;	//Point prev back 1, - 2nd list onwards, ie: 2nd to 1st, 3rd to 2nd.....
		Pointer=Pointer->next;		//Walk over to the 2nd carrage(list), then 3rd, 4th...
		Pointer->data=(5*(loop+2));	//Put some data in the list - goes up in 5's - 5,10,15,20...etc;
		loop++;
	}
	Pointer->next=0;			//final carrage, so does not point to next one
	while(Pointer->prev!=0)
	{
		cout << "Data is: " << Pointer->data << " which was in carrage(list): " << (Pointer->data/5) << endl;
		temp=Pointer;			//Temp will be the hero who sacrafices himself to cut the last carrage off
		Pointer=Pointer->prev;		//Walk back up 1 carrage
		delete temp;			//Drop off last carrage(temp rolls away)
	}
	cout << "Data is: " << Pointer->data << "  which was in carrage(list): " << (Pointer->data/5);
	delete Pointer;				//Delete engine (1st list);
	getch();
}
This linked list example had 2 nodes - next and previous so I could "walk" both ways through the carrages(lists). I then created exactly the same linked list as before, but I used a loop to create it, which meant I ended up creating 6 lists altogether. I assigned each one data values in increments of 5 upwords. When I had created and got to the last carrage, I used the pointer temp to point to the list which I was going to delete next, note - if I had used pointer for this, I would have lost the rest of the list! So I saved pointers life and made it walk(point) back up 1 carrage(list), and then deleted the last list (temp). Then I repeated this process until I got to the first list (engine). Then I deleted the final list which was the first one created.

File input/output
File I/O is using files to save or open data. I will teach you how to use text files in this lesson. Text files are made up of ASCII, for us to use textfiles we use the a new include file - #include<fstream.h> Then we create an instance of the file with a variable so we can input/output data to the file. If you want to write to a text file you use ofstream("filename");, or if you want to read you use istream("filename"); An example will make this simple.
Example

#include<conio.h>
#include<iostream.h>
#include<fstream.h>

void main()
{
	int Age;
	cout << "Please enter your age: ";
	cin >> Age;
	ofstream Data("Data.txt");		//Create an instance of the file Data.
	Data << Age;				//Send some data to the file.
	Data.close();				//Remember to close the file.
	getch();
}
This will create a text file in the local directory (where the source code is), Also it will by default over ride any file named Data.txt. You do not have to specify the data type that the variable Data is, as it is just used as a buffer, also it does not have to be called Data. This program will put the users age into the text file, try it, then find the file and open it. I then output age into the file using the << operator as that stands for output stream, ie output into text file, then after youve finished, you must remember to close the text file using - instance_name.close();
Now to read from a text file, we use istream instead of ofstream, and change the arrows from << to >> which means we are inputting data.
Example

#include<conio.h>
#include<iostream.h>
#include<fstream.h>

void main()
{
	int Age;
	ifstream Data("Data.txt");		//Create an instance of the file Data.
	Data >> Age;				//Recieve an integer from the file.
	Data.close();				//Remember to close the file.
	cout << "Age: " << Age;
	getch();
}
Now a handy way to remember istream, ofstream, fstream is by the 1st 2 letters - if stands for input file stream(get data from a file), of stands for output file stream(send data to file), and f stands for file stream which is the include file. Also to remember the arrows, just think of the cout << command, this means output so the arrows pointing left mean output, and right means input.

Now we may not want to over ride the file everytime we use files, so we can also use these inside the brackets of the file name like this -
Data("filename", ios::app); this will append (put after) the text we send to it at the end of the file.

File I/O definitions
OperatorDefinition
ios::appAppend - put data at end of file
ios::ateOpens the file, and allows additions everywhere
ios::truncDeletes everything in the file
ios::nocreateDoes not open the file if it is not created
ios::noreplaceDoes not do anything if the file is already there
ios::binaryIndicates the use of a binary file
ios::begGoes to the begining of the file
ios::endGoes to the end of the file
NothingIf you put nothing like above examples, it will create a new file and over ride old one


Example of using operators in files.

#include<conio.h>
#include<iostream.h>
#include<fstream.h>

void main()
{
	int Number;
	char Key;
	ofstream Data("Data.txt",ios::app);			//Set up file, put new data at end of file
	cout << "Press Esc to exit or any key to continue." << endl;	
	Key=getch();
	while(Key!=27)
	{
		cout << "Please enter a number: ";
		cin >> Number;
		Data << Number << endl;				//Put number into file
		cout << "Press Esc to exit or any key to continue." << endl;
		Key=getch();
	}
	Data.close();
}
Now open up the file Data.txt and see whats in it.

Now say if you wanted to use more than 1 attribute to a file, like adding nocreate as well as app, you use the | symbol, just a verticle line on the keyboard, put this between each attribute to add more, eg: ifstream Data("Data.txt",ios::app|ios::nocreate); This will open the file only if it exists and then append text to the end of the file.

Binary Files
Binary files tend to be a bit more usefull than text files, as they are reliable and store numbers more effeciently.
To set up a binary file, you just need to add the attribute: ios::binary to the file instance. eg: ofstream Data("Data.bin",ios::binary); this lets the computer know that you are dealing with a binary file not a default text file. Now reading and writing is simple but different to a text file. To read you use
instance_name.read((char *)Buffer,datasize); The instance name is what you put for it, ie: Data, then you put a .read after it as this is a class member function, then you always put a (char *) first in the brackets, this keeps the data read in chunks of 1 byte, then you put the address of the array(buffer) or variable you wish to read your data into, remember arrays address is same as writing array name without the brackets, then you put how much data you wish to read in (in bytes) from the file. To write data to a binary file is very similar, you just put:
instance_name.write((char *)Buffer,datasize); the only thing that changes is you put write instead of read and the buffer is obviously going to be writtin to the file, with the amount of data to be writting from the buffer also specified. A full example of this:

Example - Binary files
#include <conio.h>
#include <iostream.h>
#include <fstream.h>

void main()
{
	char Buffer[50];
	char Buffer2[50];
	int Size;					//String length (1 char = 1 byte)

	cout << "Type in some text: ";
	cin.getline(Buffer,50);
	Size = strlen(Buffer);

	ofstream Dataout("Data.bin",ios::binary);		//Put your text into the binary file
	Dataout.write((char *)Buffer,Size);
	Dataout.close();
	
	ifstream Datain("Data.bin",ios::binary);		//Read your text from the binary file
	Datain.read((char *)Buffer2,Size);
	Datain.close();

	cout << "\n\nYou typed in: " << Buffer2 << "\n\nPress any key to continue.";
	getch();
}
Now open up the file Data.bin (where the .exe file is) and read whats inside (should be your text you typed in). The cin.getline(Buffer,30); is a way to stop buffer overflows and your program crashing if the user enters more characters than the array size permits, so this will take in a maximum of 30 chars and store them in the array Buffer, and will disregard any more than the first 30 chars entered.

To randomly seek around a binary file, you have some extra functions to use. These are: seekg(byte value); and tellg(); The seekg(byte value); is used to go to a certain byte in the binary file, eg to go to the 50th byte you can use: Data.seekg(50); this will move the file pointer 50 bytes along the file. The tellg(); function returns an int value of how many bytes the file pointer is into the file, ie: it would return 50 if you had just used the above seekg(50);.
A usefull example of both would be:

#include <conio.h>
#include <iostream.h>
#include <fstream.h>

void main()
{
	int Filesize;

	ifstream Data("Test.bin",ios::binary|ios::beg);
	if(Data.good())				//Check if file opened succesfully
	{
		Data.seekg(ios::end);			//Go to end of file
		Filesize = Data.tellg();		//Get how many bytes into the file we are
		Data.seekg(ios::beg);			//Go back to beggining of file
		Data.close();

		cout << "The file Test.bin is " << Filesize << " bytes.";
	}
	else
	{
		cout << "Error opening file Test.bin";
	}

	getch();
}
This would put the file size (in bytes) into the variable Filesize. Also the line if(Data.good()) is a way of checking if the file opened succesfully, ie: if the file is not in the local directory to the executable than it will not be found and will not open, or if the file is corrupt it will not open etc. Tbe use of ios::beg is accepted by c as a numeric form so is valid as a function parameter, as is ios::end.

If you feel you got the hang of all this, try the Quiz - Click here


Back Home Next