October 28, 2012

Josephus Problem in Data Structure

Now we will see an example where circular link list is very useful. This is Josephus Problem. Consider there are 10 persons. They would like to choose a leader. The way they decide is that all 10 sit in a circle. They start a count with person 1 and go in clockwise direction and skip 3. Person 4 reached is eliminated. The count starts with the fifth and the next person to go is the fourth in count. Eventually, a single person remains.
You might ask why someone has to choose a leader in this way. There are some historical stories attached to it. This problem is also studied in mathematics. Let’s see diagrammatically.

clip_image001
 
We have ten numbers representing the ten persons who are in a circle. The value of M shows the count. As the value of M is three, the count will be three. N represents the number of persons. Now we start counting clockwise. After counting up to three, we have the number four. The number four is eliminated and put in the eliminated column.

Eliminated
clip_image002
After eliminating the number four, we will start our counting from number five. Counting up to three, we have number eight which is eliminated and so on.

clip_image003
The process is continued and In the end, only number five will remain intact.

clip_image004
 
If we have ten persons (N = 10) in a circle and eliminate after counting up to three (M = 3). If we start our count from one, who will be the leader? We have studied this earlier and know that the person who is sitting at the fifth position will become the leader.
Suppose if the value of N is 300 or 400 and the value of M is 5 or 10. Now who will be the leader? This is a mathematical problem where we can change the values of N and M. There is a formula where the values of N, M are allotted. You can calculate who should become the leader. Here we will not solve it mathematically. Rather, it will be tackled as a computer problem. If you analyze the pictures shown above, it gets clear that this can be solved with the circular link list. We arrange these numbers in a circularly-linked list, point the head pointer at the starting number and after calling the next method for three times, we will reach the node which is to be removed. We will use the remove method to remove the node. Then the next method is called thrice from there and the node is removed. We will continue this till we have only one node.
We are not concerned with the NULL pointers, internal to link list. However, if you want to solve this problem and choose the best data structure, then circular link list is the best option. We can also use the list to solve this.
Let’s see the code of the program by which we can solve this problem. The code is as under:

/*This program solves the Josephus Problem */
#include <iostream.h>
#include "CList.cpp" //contains the circularly-linked list definition
// The main method
void main(int argc, char *argv[])
{
CList list; // creating an object of list
int i, N=10, M=3;
for(i=1; i <= N; i++ ) list.add(i); // initializing the list with values
list.start(); // pointing the pointers at the start of the list
// counting upto M times and removing the element
while( list.length() > 1 ) {
for(i=1; i <= M; i++ ) list.next();
cout << "remove: " << list.get() << endl;
list.remove();
}
cout << "leader is: " << list.get() << endl; //displaying the remaining node
}


We have included the “CList.cpp”. It means that we are using the circularly-linked list. In the main method, CList is called to create a circular link list as CList list; After this, we assign the values to N and M. We have used for loop to add the nodes in the list. When this loop finishes, we have ten nodes in the list having values from 1 to 10. But here a programmer may not pay attention to the internal details of the list. We have created a list and stored ten numbers in it. Then we moved the pointers of the list at the start of the list using the start method. It means that the pointers are pointing at the position from where we want to start the counting of the list.
There is a while loop that will continue executing until only one node is left in the list. Inside this loop, we have a for loop. It will execute from 1 to M. It has only one statement i.e. list.next(). This will move the pointer forward three times (as the value of M is 3). Now the current pointer is at the 4th node. We called the remove method. Before removing the node. Again we come into the while loop, now the length of the list is 9. The ‘for loop’ will be executed. Now the list.next() is not starting from the start. It will start from the position where the current pointer is pointing. The current pointer is pointing at the next node to the node deleted. The count will start again. The list.next() will be called for three times. The current pointer will point at the 8th node. Again the remove method will be called and the current pointer moved to the next node and so on. The nodes will be deleted one by one until the length of the list is greater than one. When the length of the list is one, the while loop will be terminated. Now only one node is left in the list i.e. the leader. We will display its value using the get method.
We can change the values of M and N. Similarly, these values can be read from the file or can use the command line arguments to get values. There are many variations of this problem. One variation is that the value of M keeps on changing. Sometimes, it is 3, sometimes 4 or 5 and so on. Due to this, it will become difficult to think that who will become leader. Make a picture in your mind that ten persons are sitting in a circle. Every time the value of M is incremented by one. Now try to ascertain which position you should sit to get chosen as a leader.
The code of the program is given below.

#include "CList.cpp"
void main(int argc, char *argv[])
{
CList list;
int i, N=10, M=3;
for(i=1; i <= N; i++ ) list.add(i);
list.start();
while( list.length() > 1 ) {
for(i=1; i <= M; i++ ) list.next();
cout << "remove: " << list.get() << endl;
list.remove();
}
cout << "leader is: " << list.get() << endl;
}












In the program, we include the file of the class CList and create its object i.e. list. Then we solve the problem by using the add, start, length, next, remove and get methods of the class CList.
In the program, we have included already-defined data structure CList. After defining its different methods, we have an interface of Clist. There is no need to be worry about the nature of the list i.e. whether it is linked list, doubly linked list or an array. For us, it is only a list to be manipulated according to our requirement. You will see that a programmer may use different methods of the list object to solve the problem. We add elements to the list by a simple call of add method and go to the first element of the list by start method. Here, the length method is used in the condition of the while loop. Then we remove elements from the list and use the next, get and remove methods during this process. We get the current element by using the get method, then remove it by calling the remove method and then go to the next element by the method next. This way, all the elements are removed from the list except one element, called the leader. This one element remains there as we execute the while loop one less than the length of the list.
In singly linked list, the ‘next’ returns false when it reaches to the last node due to the fact that the next field of the last node is set to NULL. But in a circularly linked list there is no NULL. It will be there only when there is no node in the list.




October 27, 2012

Methods of Linked List

Earlier we discussed the methods of linked list. These methods form the interface of the link list. For further elucidation of these techniques, we will talk about the start method that has the following code.

// position currentNode and lastCurrentNode at first element
void start() {
lastCurrentNode = headNode;
currentNode = headNode;
};


There are two statements in this method. We assign the value of headNode to both lastCurrentNode and currentNode. These two pointers point at different nodes of the list. Here we have pointed both of these pointers at the start of the list. On calling some other method like next, these pointers will move forward. As we can move in the singly-linked list in one direction, these pointers cannot go behind headNode.
We will now see how a node can be removed from the link list. We use the method remove for this purpose.

void remove() {
if( currentNode != NULL && currentNode != headNode) {
(step 1) lastCurrentNode->setNext(currentNode->getNext());
(step 2) delete currentNode;
(step 3) currentNode = lastCurrentNode->getNext();
(step 4) size--;
}
};


clip_image001
 
Suppose that the currentNode is pointing at the location that contains the value 6. A request for the removal of the node is made. Resultantly, the node pointed by currentNode should be removed. For this purpose, at first, the next pointer of the node with value 2 (the node pointed by the lastCurrentNode pointer), that is before the node with value 6, bypasses the node with value 6. It is, now pointing to the node with value 8. The code of the first step is as:

lastCurrentNode->setNext(currentNode->getNext());

What does the statement currentNode->getNext() do? The currentNode is pointing to the node with value 6 while the next of this node is pointing to the node with value 8. That is the next pointer of node with value 6 contains the address of the node with value 8. The statement lastCurrentNode->setNext(currentNode->getNext()) will set the next pointer of the node pointed by the lastCurrentNode to the node with value 8. So the next pointer of the node with value 2 is pointing to the node with value 8.
clip_image002
 
You see that the next pointer of the node having data element 2 contains the address of the node having data element 8. The node with value 6 has been disconnected from the chain while the node with value 2 is connected to the node with the value 8.
The code of the next step is:
delete currentNode;
You already know, in case of allocation of the memory with the help of the new keyword, the delete statement releases this memory which returns the memory to the system. Pictorially it can be represented as:
clip_image003
In the next step, we have moved the currentNode to point the next node. The code is:

currentNode = lastCurrentNode->getNext();

In the fourth step, the size of the list has been reduced by 1 after the deletion of one node i.e.
size--;
clip_image004
The next method is length() that simply returns the size of the list. The code is as follows:

// returns the size of the list
int length()
{
return size;
};
The private data members of the list are:
private:
int size; // contains the size of the list
Node *headNode; // points to the first node of the list
Node *currentNode, // current node
Node *lastCurrentNode; // last current node


The list class completed just now, can be termed as list factory. We have included all the required methods in it. We may employ more methods if required. A programmer can get the size of the list, add or remove nodes in it besides moving the pointers.

Example of list usage
Now let’s see how we use the link list. Here is an example showing the use of list:

/* A simple example showing the use of link list */
#include <iostream>
#include <stdlib.h>
#include "List.cpp" // This contains the definition of List class
// main method
int main(int argc, char *argv[])
{
List list; // creating a list object
// adding values to the list
list.add(5);
list.add(13);
list.add(4);
list.add(8);
list.add(24);
list.add(48);
list.add(12);
// calling the start method of the list
list.start();
// printing all the elements of the list
while (list.next())
cout << "List Element: "<< list.get()<<endl;
}


The output of the program is:

List Element: 5
List Element: 13
List Element: 4
List Element: 8
List Element: 24
List Element: 48
List Element: 12


Let’s discuss the code of the above program. We have included the standard libraries besides having the “List.cpp” file. Usually we do not include .cpp files. Rather, the .h files are included. Whenever you write a class, two files will be created i.e. .h (header file containing the interface of the class) and .cpp (implementation file). Here for the sake of explanation, we have combined the two files into “List.cpp” file. At the start of the main method, we have created a list object as:
List list;
Here the default constructor will be called. If you understand the concept of factory, then it is not difficult to know that we have asked the List factory to create a List object and named it as list. After creating the object, nodes have been added to it. We have added the elements with data values 5, 13, 4, 8, 24, 48 and 12. Later, the start() method of list is called that will position the currentNode and lastCurrentNode at the start of the list. Now there is no need to worry about the implementation of the List. Rather, we will use the interface of the List. So the start method will take us to the start of the list and internally, it may be array or link list or some other implementation. Then there is a while loop that calls the next() method of the List. It moves the pointer ahead and returns a boolean value i.e. true or false. When we reach at the end of the list, the next() method will return false. In the while loop we have a cout statement that prints the value of the list elements, employing the get() method. The loop will continue till the next() method returns true. When the pointers reach at the end of the list the next() will return false. Here the loop will come to an end.
Please keep in mind that list is a very important data structure that will be used in the entire programming courses.

Analysis of Link List
As stated earlier, we will be going to analyze each data structure. We will see whether it is useful or not. We will see its cost and benefit with respect to time and memory. Let us analyze the link list which we have created with the dynamic memory allocation in a chain form.

Add
For the addition purposes, we simply insert the new node after the current node. So ‘add’ is a one-step operation. We insert a new node after the current node in the chain. For this, we have to change two or three pointers while changing the values of some pointer variables. However, there is no need of traversing too much in the list. In case of an array, if we have to add an element in the centre of the array, the space for it is created at first. For this, all the elements that are after the current pointer in the array, should be shifted one place to the right. Suppose if we have to insert the element in the start of the array, all the elements to the right one spot are shifted. However, for the link list, it is not something relevant. In link lists, we can create a new node very easily where the current pointer is pointing. We have to adjust two or three pointers. Its cost, in terms of CPU time or computing time, is not much as compared to the one with the use of arrays.

Remove
Remove is also a one-step operation. The node before and after the node to be removed is connected to each other. Update the current pointer. Then the node to be removed is deleted. As a result, the node to be removed is deleted. Very little work is needed in this case. If you compare it with arrays, for the deletion of an element from the array, space is created. To fill this space, all the right elements are shifted one spot left. If the array size is two thousand or three thousand, we need to run a loop for all these elements to shift them to left.

Find
The worst-case in find is that we may have to search the entire list. In find, we have to search some particular element say x. If found, the currentNode pointer is moved at that node. As there is no order in the list, we have to start search from the beginning of the list. We have to check the value of each node and compare it with x (value to be searched). If found, it returns true and points the currentNode pointer at that node otherwise return false. Suppose that x is not in the list, in this case, we have to search the list from start to end and return false. This is the worst case scenario. Though time gets wasted, yet we find the answer that x is not in the list. If we compare this with array, it will be the same. We don’t know whether x is in the array or not. So we have to search the complete array. In case of finding it, we will remember that position and will return true. What is the average case? x can be found at the first position , in the middle or at the end of the list. So on average, we have to search half of the list.

Back
In the back method, we move the current pointer one position back. Moving the current pointer back, one requires traversing the list from the start until the node whose next pointer points to current node. Our link list is singly linked list i.e. we can move in one direction from start towards end. Suppose our currentNode pointer and lastCurrentNode are somewhere in the middle of the list. Now we want to move one node back. If we have the pointer of lastCurrentNode, it will be easy. We will assign the value of lastCurrentNode to currentNode. But how can we move the lastCurrentNode one step back. We don’t have the pointer of previous node. So the solution for this is to go at the start of the list and traverse the list till the time you reach the node before the lastCurrentNode is pointing. That will be the node whose next pointer contains the value lastCurrentNode. If the currentNode and the lastCurrentNode are at the end of the list, we have to traverse the whole list. Therefore back operation is not a one step operation. We not only need a loop here but also require time.


Linked List Implementation

In order to use linked memory, we usually define a structure, called linked list. To form a linked list, at first, we define a node. A node comprises two fields. i.e. the object field that holds the actual list element and the next that holds the starting location of the next node. 

object next

A chain of these nodes forms a linked list. Now let’s consider our previous list, used with an array i.e . 2, 6, 8, 7, 1. Following is the figure which represents the list stored as a linked list. This diagram just represents the linked list. In the memory, different nodes may occur at different locations but the next part of each node contains the address of the next node. Thus it forms a chain of nodes which we call a linked list.
While using an array we knew that the array started from index 1that means the first element of the list is at index 1. Similarly in the linked list we need to know the starting point of the list. For this purpose, we have a pointer head that points to the first node of the list. If we don’t use head, it will not be possible to know the starting position of the list. We also have a pointer current to point to the current node of the list. We need this pointer to add or remove current node from the list. Here in the linked list, the current is a pointer and not an index as we used while using an array. The next field of the last node points to nothing .It is the end of the list. We place the memory address NULL in the last node. NULL is an invalid address and is inaccessible.
Now again consider the list 2, 6, 8, 7, 1. The previous figure represents this list as a linked list. In this linked list, the head points to 2, 2 points to 6, 6 points to 8, 8 points to 7 and 7 points to 1. Moreover we have the current position at element 8.
This linked list is stored in the memory. The following diagram depicts the process through which this linked list is stored in the memory. 

There are two parts of this figure. On the left is the linked list chain that is actually the conceptual view of the linked list and on the right is the linked list inside the computer memory. Right part is a snapshot of the computer memory with memory addresses from 1051 to 1065. The head pointer is pointing to the first element in the linked list. Note that head itself is present in the memory at address 1062. It is actually a pointer containing the memory address 1054. Each node in the above linked list has two parts i.e. the data part of the node and the pointer to the next node. The first node of the linked list pointed by the head pointer is stored at memory address 1054. We can see the data element 2 present at that address. The second part of the first node contains the memory address 1051. So the second linked list’s node starts at memory address 1051. We can use its pointer part to reach the third node of the list and in this way, we can traverse the whole list. The last node contains 1 in its data part and 0 in its pointer part. 0 indicates that it is not pointing to any node and it is the last node of the linked list. 

Linked List Operations



The linked list data structure provides operations to work on the nodes inside the list.
The first operation we are going to discuss here is to create a new node in the memory. The Add(9) is used to create a new node in the memory at the current position to hold ‘9’. You must remember while working with arrays, to add an element at the current position that all the elements after the current position were shifted to the right and then the element was added to the empty slot.
Here, we are talking about the internal representation of the list using linked list. Its interface will remain the same as in case of arrays.
We can create a new node in the following manner in the add() operation of the linked list with code in C++:
Node *   newNode   =   new   Node(9);
The first part of the statement that is on the left of the assignment is declaring a variable pointer of type Node. It may also be written as Node   * newNode. On the right of this statement, the new operator is used to create a new Node object as new  Node(9). This is one way in C++ to create objects of classes. The name of the class is provided with the new operator that causes the constructor of the class to be called. The constructor of a class has the same name as the class and as this a function, parameters can also be passed to it. In this case, the constructor of the Node class is called and ‘9’ is passed to it as an int parameter.
Hence, the whole statement means:
“Call the constructor of the Node class and pass it ‘9’ as a parameter. After constructing the object in memory, give me the starting memory address of the object. That address will be stored in the pointer variable newNode.”
To create an object of int type in the same manner, we can write as:
int *   i   =   new   int ;
Previously, we used the same technique to allocate memory for an array of int as:
int *   i   =   new   int [10] ;
Now after the node has been created, how the node is fit into the chain of the linked list.
Fig 2. Insertion of new Node into the linked list

d

In the above figure, there is a linked list that contains five nodes with data elements as 2, 6, 8, 7 and 1. The current pointer is pointing to the node with element as 8. We want to insert a new node with data element 9. This new node will be inserted at the current position (the position where the current pointer is pointing to). This insertion operation is performed in a step by step fashion.
- The first step is to point next pointer of the new node (with data element as 9) to the node with data element as 7.
- The second step is to point the next pointer of the node with data element 8 to the node the new node with data element 9.
- The third step is to change the current pointer to point to the new node.
Now, the updated linked list has nodes with data elements as 2, 6, 8, 9, 7 and 1. The list size has become 6.

 

Linked List Using C++

/* The Node class */

class Node
{
public:
int get() { return object; };
void set(int object) { this->object = object; };
Node * getNext() { return nextNode; };
void setNext(Node * nextNode) { this->nextNode = nextNode; };
private:
int object;
Node * nextNode;
};


Whenever, we write a class, it begins with the word class followed by the class-name and the body of the class enclosed within curly braces. In the body, we write its public variables, methods and then private variables and methods, this is normally the sequence.
If there is no code to write inside the constructor function of a class, we need not to declare it ourselves as the compiler automatically creates a default constructor for us. Similarly, if there is nothing to be done by the destructor of the class, it will be better not to write it explicitly. Rather, the compiler writes it automatically. Remember, the default constructor and destructor do nothing as these are the function without any code statements inside.
Let’s start with the data members first. These are given at the bottom of the class body with the scope mentioned as private. These data members are actually two parts of a linked list’s node. First variable is object of type int, present there to store the data part of the node. The second variable is nextNode, which is a pointer to an object of type Node. It has the address of the next element of the linked list.
The very first public function given at the top is get(). We have written its code within the class Node. It returns back the value of the variable object i.e. of the type of int.
When we write class in C++, normally, we make two files (.h and .cpp) for a class. The .h file contains the declarations of public and private members of that class. The public methods are essentially the interface of the class to be employed by the users of this class. The .cpp file contains the implementation for the class methods that has the actual code. This is usually the way that we write two files for one class. But this is not mandatory. In the code given above, we have only one file .cpp, instead of separating into two files. As the class methods are very small, so their code is written within the body of the class. This facilitates us in carrying on discussion. Thus instead of talking about two files, we will only refer to one file. On the other hand, compiler takes these functions differently that are called inline functions. The compiler replaces the code of these inline functions wherever the call to them is made.
The second method in the above-mentioned class is set() that accepts a parameter of type int while returning back nothing. The accepted parameter is assigned to the internal data member object. Notice the use of this pointer while assigning the value to the internal data member. It is used whenever an object wants to talk to its own members.
The next method is getNext() which returns a pointer to an object of type Node lying somewhere in the memory. It returns nextNode i.e. a pointer to an object of type Node. As discussed above, nextNode contains the address of next node in the linked list.
The last method of the class is setNext() that accepts a pointer of type Node, further assigned to nextNode data member of the object. This method is used to connect the next node of the linked list with the current object. It is passed an address of the next node in the linked list.
Let’s discuss a little bit about classes. A very good analogy of a class is a factory. Think about a car factory. On the placement of order, it provides us with the number of vehicles we ordered for. Similarly, you can see number of other factories in your daily-life that manufacture the specific products.
Let’s take this analogy in C++ language. Suppose, we want to make a factory in C++. By the way, what is our Node class? It is actually a factory that creates nodes. When we want to make a new node, a new operator is used. By using new operator with the Node class, actually, we send an order to Node factory, to make as many as nodes for us.
So we have a good analogy, to think about a class as a factory. The products that are made by the factory have their own characteristics. For example, a car made by an automobile factory has an engine, wheels, steering and seats etc. These variables inside a class are called state variables. Now the kinds of operations this car can do are the methods of its class. A car can be driven, engine can be started, gears can be shifted and an accelerator can be pressed to run it faster.
Similarly, the Node class creates nodes, where every node has two-state variables i.e. object and nextNode. We have already seen its operations in the above code. We use new to create new object or an array of new objects, stored in memory.
Let’s see the code below.

/* List class */
#include <stdlib.h>
#include "Node.cpp"
class List
{
public:
// Constructor
List() {
headNode = new Node();
headNode->setNext(NULL);
currentNode = NULL;
size = 0;
}


We are creating a list factory here employed to create list objects. Remember the list operations; add, remove, next, back and start etc. Let’s see the above class declaration code in detail.
There are two include statements at the start. The first line is to include a standard library stdlib.h while the second line includes the Node class file Node.cpp. This Node class is used to create nodes that form a List object. So this List factory will order Node class to create new nodes. The List class itself carries out the chain management of these Node objects.
We have written our own constructor of List class as the default constructor is not sufficient enough to serve the purpose. The List constructor is parameterless. The very first step it is doing internally is that it is asking Node class to create a new node and assigning the starting address of the new Node’s object to the headNode data member. In the second statement, we are calling setNext() method of the Node class for the object pointed to by the headNode pointer. This call is to set the nextNode data member to NULL, i.e. Node’s object pointed to by the headNode pointer is not pointing to any further Node. The next statement is to set the currentNode pointer to NULL. So at the moment, we have initialized the currentNode pointer to NULL that is not pointing to any Node object. The next statement is to initialize the size data member to 0 indicating that there is no node present in the list. All this processing is done inside the constructor of List class, as we want all this done when a list object is created. Considering the analogy of car factory, the constructor function can perform certain tasks: The oil is poured into the engine, the tyres are filled-in with air etc.
Let’s see the add method of the List class:

/* add() class method */
void add (int addObject)
{
1. Node * newNode = new Node();
2. newNode->set(addObject);
3. if( currentNode != NULL )
4. {
5. newNode->setNext(currentNode->getNext());
6. currentNode->setNext( newNode );
7. lastCurrentNode = currentNode;
8. currentNode = newNode;
9. }
10. else
11. {
12. newNode->setNext(NULL);
13. headNode->setNext(newNode);
14. lastCurrentNode = headNode;
15. currentNode = newNode;
16. }
17. size ++;
}



The interface or signatures of add() method is similar to the one discussed in case of an array. This method takes the object to be added as a parameter. The implementation of this add() method is a bit longer as the method is being implemented for linked list. In the first statement, a new Node object is created with its address stored in the newNode pointer variable. The second statement is to call set() method of the Node object pointed to by the newNode pointer. You can note the way the method is called. A pointer variable is at the left most side then an arrow sign (->), then the name of the method with appropriate arguments within parenthesis. It is followed by the if-statement that checks the currentNode is not NULL to perform certain operations inside the if-code block. Inside the if-statement, at line 5, the nextNode pointer of the new node is being set to the nextNode of the object pointed to by the currentNode pointer. In order to understand the statements given in this code properly, consider the fig 2 above, where we added a node in the linked list. We have done step 1 at line5. At line 6, we are performing the second step by setting the newNode in the nextNode pointer of the object pointed to by the currentNode. At line 7, we are saving the current position (address) of the currentNode pointer in the pointer variable lastCurrentNode, which might be useful for backward traversing. Although, the fig 1 (left part) indicates movement in one direction from left to right but the lastCurrentNode pointer node can be used by the back() member function to traverse one position back from right to left. At line 8, the currentNode pointer is assigned the address of the object pointed to by newNode. This way, a new node is added in already existent linked list.
Line 10 is start of the else part of if-statement. This is executed if the currentNode is NULL. It means that there is no node present in the list previously and first node is going to be added. At line 12, we are setting the nextNode pointer of the object pointed to by newNode pointer. The nextNode is being set to NULL by calling the setNext() method. Then at line 13, we point the head pointer (headNode) to this new node pointed to by newNode pointer. Note that headNode is pointing to a node that is there despite the fact that the size of the linked list is 0. Actually, we have allocated a Node object for headNode pointer. Although, we don’t need a Node object here, yet it will be helpful when we perform other operations like remove() and find().

At line 14, the headNode address is being assigned to lastCurrentNode. At line 15, currentNode pointer is assigned the address of newNode. At the end i.e. at line 17, the size of the list is incremented by 1.

r

Fig 3. Add operation of linked list

Following is the crux of this add() operation :

Firstly, it will make a new node by calling Node class constructor. Insert the value e.g. 2. of the node into the node by calling the set method. Now if the list already exists (has some elements inside or its size is non-zero), it will insert the node after the current position. If the list does not already exist, this node is added as the first element inside the list.
Let’s try to add few more elements into the above linked list in the figure. The following are the lines of code to be executed to add nodes with values 8, 7 and 1 into the linked list.
list.add(8); list.add(7); list.add(1);

rr
Fig 4. More Nodes added into linked list

Now we will see the remaining methods of the linked list. The get() method of the List class is given below
/* get() class method */
int get()
{
if (currentNode != NULL)
return currentNode->get();
}


This method firstly confirms that the currentNode pointer is not NULL. If it is not NULL, then it must be pointing to some Node object as inside the constructor of the List class, we have initialized this pointer variable to NULL. That indicates that the currentNode is NULL when there is no element inside the list. However, when a Node object is added into it, it starts pointing to it. So, this get() returns the address of the node pointed to by the currentNode pointer.
Further, we have another method given below:

/* next() class method */
bool next()
{
1. if (currentNode == NULL) return false;
2.
3. lastCurrentNode = currentNode;
4. currentNode = currentNode->getNext();
5. return true;
};



This is next() method, used to advance the currentNode pointer to the next node inside the linked list. At line 1, the currentNode is being checked to confirm that there are some elements present in the list to advance further. At line 1, the method is returning false if there is no element present in the list. At line 3, it is storing the value of the currentNode pointer into the lastCurrentNode. At line 4, currentNode is calling the getNext() method to get the address of next node to be stored in the currentNode pointer to advance the currentNode pointer to the next element. At line 5, it returns true indicating the method is successful in moving to the next node.

Example Program

Given below is the full source code of the example program. You can copy, paste and compile it right away. In order to understand the linked list concept fully, it is highly desirable that you understand and practice with the below code.

#include <iostream.h>
#include <stdlib.h>
/* The Node class */
class Node
{
public:
int get() { return object; };
void set(int object) { this->object = object; };
Node * getNext() { return nextNode; };
void setNext(Node * nextNode) { this->nextNode = nextNode; };
private:
int object;
Node * nextNode;
};
/* The List class */
class List
{
public:
List();
void add (int addObject);
int get();
bool next();
friend void traverse(List list);
friend List addNodes();
private:
int size;
Node * headNode;
Node * currentNode;
Node * lastCurrentNode;
};
/* Constructor */
List::List()
{
headNode = new Node();
headNode->setNext(NULL);
currentNode = NULL;
lastCurrentNode = NULL;
size = 0;
}
/* add() class method */
void List::add (int addObject)
{
Node * newNode = new Node();
newNode->set(addObject);
if( currentNode != NULL )
{
newNode->setNext(currentNode->getNext());
currentNode->setNext( newNode );
lastCurrentNode = currentNode;
currentNode = newNode;
}
else
{
newNode->setNext(NULL);
headNode->setNext(newNode);
lastCurrentNode = headNode;
currentNode = newNode;
}
size ++;
}
/* get() class method */
int List::get()
{
if (currentNode != NULL)
return currentNode->get();
}
/* next() class method */
bool List::next()
{
if (currentNode == NULL) return false;
lastCurrentNode = currentNode;
currentNode = currentNode->getNext();
if (currentNode == NULL || size == 0)
return false;
else
return true;
}
/* Friend function to traverse linked list */
void traverse(List list)
{
Node* savedCurrentNode = list.currentNode;
list.currentNode = list.headNode;
for(int i = 1; list.next(); i++)
{
cout << "\n Element " << i << " " << list.get();
}
list.currentNode = savedCurrentNode;
}
/* Friend function to add Nodes into the list */
List addNodes()
{
List list;
list.add(2);
list.add(6);
list.add(8);
list.add(7);
list.add(1);
cout << "\n List size = " << list.size <<'\n';
return list;
}
main()
{
List list = addNodes();
traverse(list);
}



The output of the example program is as follows:

List size = 5
Element 1 2
Element 2 6
Element 3 8
Element 4 7
Element 5 1






October 26, 2012

DNS on packet tracer:

Here in this tutorial, we are going to set a dns (domain name system) server and a dhcp server. And then from our PC we will use dns service.
1
Server 0 in the above topology is our dhcp server and Server 1 is our dns server.
a

Set up IP on server 0.
 2
Set up DHCP on server 0.
3
Set up IP on server 1.
4
Now, go to PC and select DHCP.
6
Go to Web Browser and enter Server 0 ip address. You can access the website of the server.
7
Now, let us set DNS on server 1.
9
Now, again go to PC and in the web browser enter the name that you set in DNS.
 8
Voila, we have done it. Now, in this tutorial, router is additional and we can use it if required, Set the IP of the interface. Though i do not recommend to use this GUI panel for this.
i

To see how to make a router DHCP server. Click here. You can also achieve DNS by using single sever by supplying the Server with the same IP and DNS address. Try it.

DHCP on Packet tracer through Server

We are going to apply DHCP on server and PCs will be assigned IP addresses through DHCP.
serv1
Open the server and go to the Desktop tab, click IP Configuration and enter the IP address.
2
Now, go to the Config tab.
3
And go to the DHCP
4
i. Enter IP for default Gateway.
ii. Start IP address
iii.. Maximum number of Users.
iv. Click Save.
6
Now, click on any PC that is attached to the server, go to IP configuration and select DHCP. You will see that DHCP will successfully assign IP address to the PC
7
Now, if we go back to server and assign DNS Server address and then go to any PC and select DHCP.
9 
It will also assign DNS to the PC as well.   
 10  
We can also open the website of the server through any PC by going to the Web Browser option and entering the IP address of the server.
11
And we can ping the server by going to the PC’s command prompt and entering server’s IP address.
12

October 22, 2012

DHCP on packet tracer

This tutorial is about how to configure dhcp on cisco router in packet tracer. The Dynamic Host Configuration Protocol (DHCP) is a network protocol that is used to configure network devices. DHCP allows a computer to join an IP-based network without having a pre-configured IP address. DHCP is a protocol that assigns unique IP addresses to devices, then releases and renews these addresses as devices leave and re-join the network. 
Internet Service Providers (ISPs) usually use DHCP to allow customers to join the Internet with minimum effort. The DHCP server maintains a database of available IP addresses and configuration information. When it receives a request from a client, the DHCP server determines the network to which the DHCP client is connected, and then allocates an IP address. DHCP servers typically grant IP addresses to clients only for a limited interval.

Lets apply DHCP on packet tracer.
First, let us make a topology with one router on which we will apply DHCP and several client PCs. More like this one,

Untitled

Now, we will apply DHCP on the router.
The commands in sequence are as follows.


cli actual

In the following command “ip dhcp pool cisco”, we are creating a  pool for DHCP called cisco. cisco is the name here and we can name it whatever we want.
Similarly, in the command “default-router “ we are telling the DHCP about the default route to follow.
Notice, after we exit from DHCP mode, we are excluding some IP addresses by applying this command “ip dhcp excluded-addresses x-x”, where x is the starting and ending IP address respectively. We are basically reserving some IPs for our use. It can be used to attach printers, or assign it to some specific users for security purposes. You can also give dns address in dhcp by using the following command.
dns-server 192.168.1.15.

Now, open the PC.

image

Click on IP Configuration

image

Select from Static to DHCP

image

And after DHCP request is completed you will see the following screen.

image

Now, after applying some IPs in sequence, DHCP will skip the IPs that we have excluded from our DHCP pool.

image

That is all, we have applied DHCP on packet tracer.



October 20, 2012

EIGRP on Packet Tracer

Hi everyone, today we are going to apply Enhanced Interior Gate Way Routing Protocol (EIGRP) on packet tracer.  Here are the basic set of commands that we can apply on router CLI mode in order to apply EIGRP on router.

clip_image002

Also, look at some additional commands.

clip_image002[7]

Now, we are going to apply EIGRP on the following topology.

eigrp diagram

Now, after successfully applying IP addresses like in this topology, we will apply following commands.
Router(config)#router eigrp 10
Router(config-router)#network 192.168.1.0
Router(config-router)#network 192.168.2.0
Router(config-router)#exit

Apply the above set of commands on both routers like this.

eigrp 1

And eigrp protocol has been applied on this topology. Notice the following command.
router eigrp 10
This number ‘10' is the process ID.







October 19, 2012

RIP Version 2 on Packet Tracer

There is no big difference between RIP version 1 and version 2 when we are applying them in packet tracer. In order to apply RIP version 2 on packet tracer. we will just have to add the following command. We will follow the same example that we used in RIP version 1 in this article.

rip

Router(config)# router rip
Router(config-router)# network 192.168.1.0
Router(config-router)# network 192.168.2.0
Router(config-router)# version 2
Router(config-router)#exit

You see there is just the addition of one statement i.e. “version 2”. The rest is the same. We will apply the above set of commands on both routers i.e. Router 3 and Router 2 ,used in the topology above which is also used in this article, above and bingo, we have applied RIP V2 on packet tracer.
Just make sure that the protocol is applied as an additional step and cannot replace the basic steps i.e. we have to assign IP addresses to the router’s interfaces and PCs and also change the state of the interfaces from down to UP like in this article and then we will go ahead and apply Protocol.


RIP on Packet Tracer

Main Commands
clip_image002
You need to advertise only the classful network number, not a subnet.
Explanation:
Lets apply RIP protocol on the following topology.


Now, we will follow the steps as mentioned in detail in the following article. i.e.
i. We will assign IP addresses to all the fast Ethernet and serial interfaces respectively.
ii We will change the state of the interfaces from down to UP.
Then, after we are done with the basic step. We will apply RIP protocol commands on both routers.

Configuration of Router 0 i.e. configuring both serial and fastethernet interfaces.


Configurations of R1


Assigning IP address to PC0


Assigning IP address to PC1





R1
In order to apply protocol RIP, we will write the following set of commands.

Router(config)# router rip
Router(config-router)# network 192.168.1.0
Router(config-router)# network 192.168.2.0
Router(config-router)# network 192.168.3.0
Router(config-router)#exit


R2:
In order to apply protocol RIP, we will write the following set of commands on R2 as well.

Router(config)# router rip
Router(config-router)# network 192.168.1.0
Router(config-router)# network 192.168.2.0
Router(config-router)# network 192.168.3.0
Router(config-router)#exit









Write all the commands in the same fashion as in the above screen shots and voila, we are done with RIP protocol. Another important thing here is that we will add all the networks that we are using in our topology. Here in this particular example i am just using two networks x.x.1.0 and x.x.2.0 so thats why i have added these two network addresses to the RIP protocol.

Now, you can check it. Traffic is enabled and you can easily send data from PC0 to PC1.





C program to Read From a File

#include <stdio.h> #include <stdlib.h> void main() {     FILE *fptr;     char filename[15];     char ch;   ...