October 29, 2012

Abstract Data Type

A data type is a collection of values and a set of operations on those values. That collection and these operations form a mathematical construct that may be implemented with the use of a particular hardware or software data structure. The term abstract data type (ADT) refers to the basic mathematical concept that defines the data type. We have discussed four different implementations of the list data structure. In case of implementation of the list with the use of an array, the size of the array gives difficulty if increased. To avoid this, we allocate memory dynamically for nodes before connecting these nodes with the help of pointers. For this purpose, we made a singly linked list and connected it with the next pointer to make a chain. Moving forward is easy but going back is a difficult task. To overcome this problem, we made a doubly linked list using prev and next pointers. With the help of these pointers, we can move forward and backward very easily. Now we face another problem that the prev pointer of first node and the next pointer of the last node are NULL. Therefore, we have to be careful in case of NULL pointers. To remove the NULL pointers, we made the circular link list by connecting the first and last node.
The program employing the list data structure is not concerned with its implementation. We do not care how the list is being implemented whether through an array, singly linked list, doubly linked list or circular linked list. It has been witnessed that in these four implementations of the list, the interface remained the same i.e. it implements the same methods like add, get, next, start and remove etc. This proves that with this encapsulation attained by making a class, we are not concerned with its internal implementation. The implementation of these abstract data types can be changed anytime. These abstract data types are implemented using classes in C++. If the list is implemented using arrays while not fulfilling the requirements, we can change the list implementation. It can be implemented with the use of singly-link list or doubly link list. As long as the interface is same, a programmer can change the internal implementation of the list and the program using this list will not be affected at all. This is the abstract data type (ADT). What we care about is the methods that are available for use, with the List ADT i.e. add, get, and remove etc methods. We have not studied enough examples to understand all the benefits of abstract data types. We will follow this theme while developing other ADT. We will publish the interface and keep the freedom to change the implementation of ADT without effecting users of the ADT. The C++ classes provide a programmer an ability to create such ADTs. What benefits can we get with the help of these ADTs and classes? When we develop an ADT or a class or factory then the users of this factory are independent of how this factory works internally. Suppose that we have ordered the car factory (car class) to produce a new car and it replies after a long time. If we ordered the remove method to remove one node and we are waiting and it keeps on working and working. Then we might think that its implementation is not correct. Although, we are not concerned with the internal implementation of this ADT yet it is necessary to see whether this ADT is useful for solving our problem or not. It should not become a bottleneck for us. If the method we are using is too much time consuming or it has some problem in terms of algorithm used. On one side, we only use the interfaces provided by these ADTs, classes, or factories as long as they do what they promise. We are not concerned with the internal details. On the other hand, we have to be careful that these factories or methods should not take too much time so that these will not be useful for the problem.
This distinction will always be there. Sometimes, the source code of classes is not provided. We will be provided libraries, as standard libraries are available with the compiler. These classes are in compiled form i.e. are in object form or in binary form. On opening these files, you will not see the C++ code, rather binary code. When you read the assembly language code, it will give some idea what this binary code is about. You can view the interface methods in the .h file. As an application programmer, you have to see that the ADTs being used are written in a better way. The point to be remembered here is that you should not worry about the internal implementation of these ADTs. If we want to change the internal implementation of the ADTs, it can be done without affecting the users of these ADTs. While writing a program, you should check its performance. If at some point, you feel that it is slow, check the ADTs used at that point. If some ADT is not working properly, you can ask the writer of the ADT to change the internal implementation of that ADT to ensure that it works properly.

 



Stack Implementation using array

Lets implement the stack using the arrays. The stack shown in the below diagram may be considered as an array. Here the array is shown vertically. We can implement the stack using array. The interface will remain as push and pop methods. The user of the stack does not need to know that the stack is internally implemented with the help of array. The worst case for insertion and deletion from an array may happen when we insert and delete from the beginning of the array. We have to shift elements to the right for insertion and left for removal of an element. We face the same problem while implementing the list with the use of the array. If we push and pop the elements from the start of the array for stack implementation, this problem will arise. In case of push, we have to shift the stack elements to the right. However, in case of pop, after removing the element, we have to shift the elements of stack that are in the array to the left. If we push the element at the end of the array, there is no need to shift any element. Similarly as the pop method removes the last element of the stack which is at the end of the array, no element is shifted. To insert and remove elements at the end of the array we need not to shift its elements. Best case for insert and delete is at the end of the array where there is no need to shift any element. We should implement push() and pop() by inserting and deleting at the end of an array.
clip_image001

In the above diagram, on the left side we have a stack. There are four elements in the stack i.e. 1, 7, 5 and 2. The element 1 is the extreme-most that means that it is inserted in the end whereas 7, 5, and 2 have been added before. As this is a LIFO structure so the element 1 should be popped first. On the right side we have an array with positions 0, 1, 2, 3 and so on. We have inserted the numbers 2, 5, 7 and 1. We have decided that the elements should be inserted at the end of the array. Therefore the most recent element i.e. 1 is at position 3. The top is the index representing the position of the most recent element. Now we will discuss the stack implementation in detail using array.
We have to choose a maximum size for the array. It is possible that the array may ‘fill-up’ if we push enough elements. Now more elements cannot be pushed. Now what should the user of the stack do? Internally, we have implemented the stack using array which can be full. To avoid this, we write isFull() method that will return a boolean value. If this method returns true, it means that the stack (array) is full and no more elements can be inserted. Therefore before calling the push(x), the user should call isFull() method. If isFull() returns false, it will depict that stack is not full and an element can be inserted. This method has become the part of the stack interface. So we have two more methods in our interface i.e. isEmpty() and isFull().
Now we will discuss the actual C++ code of these operations. These methods are part of stack class or stack factory. We have an array named A while current is its index. The code of pop() method is as:
 
int pop()
{
return A[current--];
}
In this method, the recent element is returned to the caller, reducing the size of the array by 1.
The code of push method is:
void push(int x)
{
A[++current] = x;
}

 
We know that ++current means that add one to the current and then use it. That also shows that element x should be inserted at current plus one position. Here we are not testing that this current index has increased from the array size or not. As discussed earlier that before using the push method, the user must call isFull() method. Similarly it is the responsibility of the user to call the isEmpty() method before calling the pop method. Therefore there is no if statement in the push and pop method.
The code of the top() method is:
 
int top()
{
return A[current];
}
This method returns the element at the current position. We are not changing the value of current here. We simply want to return the top element.
int isEmpty()
{
return ( current == -1 );
}
This method also tests the value of the current whether it is equal to -1 or not. Initially when the stack is created, the value of current will be -1. If the user calls the isEmpty() method before pushing any element, it will return true.
int isFull()
{
return ( current == size-1);
}


This method checks that the stack is full or not. The variable size shows the size of the array. If the current is equal to the size minus one, it means that the stack is full and we cannot insert any element in it.
We have determined the cost and benefit of all the data structures. Now we will see how much time these methods take. A quick examination shows that all the five operations take constant time. In case of list, the find method takes too much time as it has to traverse the list. Whereas the add and remove methods are relatively quick. The methods of stack are very simple. There is no complexity involved. We insert element at one side and also remove from that side not in the middle or some other place. Therefore we need not to carry out a lot of work. During the usage of the array, the stack methods push, pop, top, isFull and isEmpty all are constant time operations. There is not much difference of time between them.
The complete code of the program is:

/* Stack implementation using array */
#include <iostream.h>
/* The Stack class */
class Stack
{
public:
Stack() { size = 10; current = -1;} //constructor
int pop(){ return A[current--];} // The pop function
void push(int x){A[++current] = x;} // The push function
int top(){ return A[current];} // The top function
int isEmpty(){return ( current == -1 );} // Will return true when stack is empty
int isFull(){ return ( current == size-1);} // Will return true when stack is full
private:
int object; // The data element
int current; // Index of the array
int size; // max size of the array
int A[10]; // Array of 10 elements
};
// The main method
int main()
{
Stack stack; // creating a stack object
// pushing the 10 elements to the stack
for(int i = 0; i < 12; i++)
{
if(!stack.isFull()) // checking stack is full or not
stack.push(i); // push the element at the top
else
cout <<"\n Stack is full, can't insert new element";
}
// pop the elements at the stack
for (int i = 0; i < 12; i++)
{
if(!stack.isEmpty()) // checking stack is empty or not
cout << "\n The popped element = " << stack.pop();
else
cout <<"\n Stack is empty, can't pop";
}
}


The output of the program is:
Stack is full, can't insert new element
Stack is full, can't insert new element
The popped element = 9
The popped element = 8
The popped element = 7
The popped element = 6
The popped element = 5
The popped element = 4
The popped element = 3
The popped element = 2
The popped element = 1
The popped element = 0
Stack is empty, can't pop
Stack is empty, can't pop


However, a programmer finds the size-related problems in case of an array. What should we do when the array is full? We can avoid the size limitation of a stack implemented with an array by using a linked list to hold the stack elements.


Stacks

Let us discuss another important data structure i.e stack.  Some examples of stacks in real life are stack of books, stack of plates etc. We can add new items at the top of the stack or remove them from the top. We can only access the elements of the stack at the top. Following is the definition of stacks.
“Stack is a collection of elements arranged in a linear order”.
Let’s see an example to understand this. Suppose we have some video cassettes. We took one cassette and put it on the table. We get another cassette and put it on the top of first cassette. Now there are two cassettes on the table- one at the top of other. Now we take the third cassette and stack it on the two. Take the fourth cassette and stack it on the three cassettes.
Now if we want to take the cassette, we can get the fourth cassette which is at the top and remove it from the stack. Now we can remove the third cassette from the stack and so on. Suppose that we have fifty cassettes stacked on each other and want to access the first cassette that is at the bottom of the stack. What will happen? All the cassettes will fell down. It will not happen exactly the same in the computer. There may be some problem. It does not mean that our data structure is incorrect. As we see in the above example that the top most cassette will be removed first and the new cassette will be stacked at the top. The same example can be repeated with the books. In the daily life, we deal with the stacked goods very carefully.
Now we will discuss how to create a stack data structure or a factory, going to create stack object for us. What will be the attributes of this object? During the discussion on the list, we came to know that a programmer adds values in the list, removes values from the list and moves forward and backward. In case of a stack too, we want to add things and remove things. We will not move forward or backward in the stack. New items can be added or removed at the top only. We can not suggest the removal of the middle element of the stack.
Let’s talk about the interface methods of the stacks. Some important methods are:

Method Name Description
push(x) Insert x as the top element of the stack
pop() Remove the top element of the stack and return it.
top() Return the top element without removing it from the stack.

The push(x) method will take an element and insert it at the top of the stack. This element will become top element. The pop() method will remove the top element of the stock and return it to the calling program. The top() method returns the top-most stack element but does not remove it from the stack. The interface method names that we choose has special objective. In case of list, we have used add, remove, get, set as the suitable names. However, for stack, we are using push, pop and top. We can depict the activity from the method name like push means that we are placing an element on the top of the stack and pushing the other elements down.
The example of a hotel’s kitchen may help understand the concept of stacks in a comprehensive manner. In the kitchen, the plates are stacked in a cylinder having a spring on the bottom. When a waiter picks a plate, the spring moves up the other plates. This is a stack of plates. You will feel that you are pushing the plates in the cylinder and when you take a plate from the cylinder it pops the other plates. The top method is used to get the top- most element without removing it.
When you create classes, interfaces and methods, choose such names which depicts what these method are doing. These names should be suitable for that class or factory.
Let’s discuss the working of stack with the help of a diagram.

clip_image001
 
At the start, the stack is empty. First of all, we push the value 2 in the stack. As a result, the number 2 is placed in the stack. We have a top pointer that points at the top element. Then we said push(5). Now see how 2 and 5 are stacked. The number 5 is placed at the top of number 2 and the pointer top moves one step upward. Then we pushed the number 7 which is placed on the top and the number 2 and 5 are below. Similarly, we push number 1. The last figure in the first row shows the stacked values of the numbers- 1, 7, 5 and 2.

Let’s pop the elements from the stack. The first figure of second row shows the pop operation. As a result, the number 1 is popped. Than again we push the number 21 on the stack. The number 7, 5, and 2 are already in the stack and number 21 is pushed at the top. If we pop now, the number 21 is popped. Now number 7 is at the top. If we pop again, the number 7 is popped. Pop again and the number 5 is popped and number 2 remains in the stack. Here with the help of this diagram, we are proving that the values are added at the top and removed at the top in a stack.

The last element to go into the stack is the first to come out. That is why, a stack is known as LIFO (Last In First Out) structure. We know that the last element pushed in the stack is at the top which is removed when we call pop. Let’s see some other scenarios. What happens if we call pop() while there is no element? One possible way-out is that we have isEmpty() function that returns true if stack is empty and false otherwise. This is a boolean function that returns false if there is no element in the stack. Otherwise, it will return true. The second option is this that when we call pop on an empty stack, it throws an exception. This is a concept of advanced C++. Exception is also a way to convey that some unusual condition has arisen or something has gone wrong. Suppose, if we have a division method and try to divide some number with zero. This method will throw ‘division by zero’ exception. Currently we will not throw an exception but use the isEmpty() method. The user who is employing the stack is responsible to call the isEmpty() method before calling the pop. Call the pop method if isEmpty() returns false . Otherwise, there will be a problem.
For stack implementation using array, look at this article. For stack implementation through linked list, click here.


Stack Implementation: Array or Linked List

Since both implementations support stack operations in constant time, we will see what are the possible reasons to prefer one implementation to the other.
- Allocating and de-allocating memory for list nodes does take more time than pre-allocated array. Memory allocation and de-allocation has cost in terms of time, especially, when your system is huge and handling a volume of requests. While comparing the stack implementation, using an array versus a linked list, it becomes important to consider this point carefully.
- List uses as much memory as required by the nodes. In contrast, array requires allocation ahead of time. In the previous bullet, the point was the time required for allocation and de-allocation of nodes at runtime as compared to one time allocation of an array. In this bullet, we are of the view that with this runtime allocation and de-allocation of nodes, we are also getting an advantage that list consumes only as much memory as required by the nodes of list. Instead of allocating a whole chunk of memory at one time as in case of array, we only allocate memory that is actually required so that the memory is available for other programs. For example, in case of implementing stack using array, you allocated array for 1000 elements but the stack, on average, are using 50 locations. So, on the average, 950 locations remain vacant. Therefore, in order to resolve this problem, linked list is handy.
- List pointers (head, next) require extra memory. Consider the manipulation of array elements. We can set and get the individual elements with the use of the array index; we don’t need to have additional elements or pointers to access them. But in case of linked list, within each node of the list, we have one pointer element called next, pointing to the next node of the list. Therefore, for 1000 nodes stack implemented using list, there will be 1000 extra pointer variables. Remember that stack is implemented using ‘singly-linked’ list. Otherwise, for doubly linked list, this overhead is also doubled as two pointer variables are stored within each node in that case.
- Array has an upper limit whereas list is limited by dynamic memory allocation. In other words, the linked list is only limited by the address space of the machine. We have already discussed this point at reasonable length in this lecture.

 Use of Stack

Examples of uses of stack include- traversing and evaluating prefix, infix and postfix expressions.
Consider the expression A+B: we think of applying the operator “+” to the operands A and B. We have been writing this kind of expressions right from our primary classes. There are few important things to consider here:
Firstly, + operator requires two operators or in other words “+” is a binary operator.
Secondly, in the expression A+B, the one operand A is on left of the operator while the other operand B is on the right side. This kind of expressions where the operator is present between two operands called infix expressions. We take the meanings of this expression as to add both operands A and B.
There are two other ways of writing expressions:
- We could write +AB, the operator is written before the operands A and B. These kinds of expressions are called Prefix Expressions.
- We can also write it as AB+, the operator is written after the operands A and B. This expression is called Postfix expression.
The prefixes pre and post refer to the position of the operator with respect to the two operands.
Consider another expression in infix form: A + B * C. It consists of three operands A, B, C and two operator +,* . We know that multiplication () is done before addition (+), therefore, this expression is actually interpreted as: A + (B * C). The interpretation is because of the precedence of multiplication (*) over addition (+). The precedence can be changed in an expression by using the parenthesis. We will discuss it a bit later.
Let’s see, how can we convert the infix expression A + (B * C) into the postfix form. Firstly, we will convert the multiplication to postfix form as: A + (B C *). Secondly, we will convert addition to postfix as: A (B C *) + and finally it will lead to the resultant postfix expression i.e. : A B C * +. Let’s convert the expression (A + B) * C to postfix. You might have noticed that to overcome the precedence of multiplication operator (*) we have used parenthesis around A + B because we want to perform addition operation first before multiplication.
(A + B) * C infix form
(A B +) * C convert addition
(A B +) C * convert multiplication
A B + C * postfix form
These expressions may seem to be difficult to understand and evaluate at first. But this is one way of writing and evaluating expressions. As we are normally used to infix form, this postfix form might be little confusing. If a programmer knows the algorithm, there is nothing complicated and even one can evaluate the expression manually.

Technorati Tags: ,,,,,,,

October 28, 2012

Introduction to Packet Tracer



Packet Tracer is a protocol simulator developed at Cisco Systems. Packet Tracer (PT) is a powerful and dynamic tool that displays the various protocols used in networking, in either Real Time or Simulation mode. This includes layer 2 protocols such as Ethernet and PPP, layer 3 protocols such as IP, ICMP, and ARP, and layer 4 protocols such as TCP and UDP. Routing protocols can also be traced. Packet Tracer is a supplement to and not a replacement for experience with real equipment. Students are encouraged to compare the results obtained from Packet Tracer network models with the behavior of real equipment.

Creating a New Topology in Packet Tracer
Start Packet Tracer

clip_image002

Choosing Devices and Connections
We will begin building our network topology by selecting devices and the media in which to connect them. Several types of devices and network connections can be used. For this lab we will keep it simple by using End Devices, Switches, Hubs, and Connections.
Single click on each group of devices and connections to display the various choices. When we select a device in the left panel, in the right panel we see all the listed devices of that type.


clip_image005
clip_image008


Single click on the End Devices.
clip_image017[1]

Single click on the Generic host.

clip_image017[2]

Move the cursor into topology area. You will notice it turns into a plus “+” sign.
clip_image026

Single click in the topology area and it copies the device.

 
clip_image028 clip_image030


Add three more hosts.
clip_image032

Adding a Hub

Select a hub, by clicking once on Hubs and once on a Generic hub.

 
clip_image011[1] clip_image035 clip_image037


Add the hub by moving the plus sign “+” below PC0 and PC1 and click once.
clip_image039 clip_image041


Connect PC0 to Hub0 by first choosing Connections.

clip_image015[1]

Click once on the Copper Straight-through cable.

clip_image043

Perform the following steps to connect PC0 to Hub0:
  1. Click once on PC0
  2. Choose FastEthernet
  3. Drag the cursor to Hub0
  4. Click once on Hub0 and choose Port 0
  5. Notice the green link lights on both the PC0 Ethernet NIC and the Hub0 Port 0 showing that the link is active.
1 2 3 4 5
clip_image045 clip_image047 clip_image049 clip_image051 clip_image053

Repeat the steps above for PC1 connecting it to Port 1 on Hub0. (The actual hub port you choose does not matter.
clip_image055

Adding a Switch

Select a switch, by clicking once on Switches and once on a 2950-24 switch.

 
clip_image008[1] clip_image058 clip_image060


Add the switch by moving the plus sign “+” below PC2 and PC3 and click once.

 
clip_image062 clip_image064


Connect PC2 to Hub0 by first choosing Connections.

clip_image015[2]

Click once on the Copper Straight-through cable

clip_image043[1]

Perform the following steps to connect PC2 to Switch0:
  1. Click once on PC2
  2. Choose FastEthernet
  3. Drag the cursor to Switch0
  4. Click once on Switch0 and choose FastEthernet0/1
  5. Notice the green link lights on PC2 Ethernet NIC and amber light Switch0 FastEthernet0/1 port. The switch port is temporarily not forwarding frames, while it goes through the stages for the Spanning Tree Protocol (STP) process.
  6. After a about 30 seconds the amber light will change to green indicating that the port has entered the forwarding stage. Frames can now forwarded out the switch port.
1 2 3 4 5 6
clip_image066 clip_image068 clip_image070 clip_image072 clip_image074 clip_image076

Repeat the steps above for PC3 connecting it to Port 3 on Switch0 on port FastEtherent0/2. (The actual switch port you choose does not matter.)
clip_image078

Move the cursor over the link light to view the port number. Fa means FastEthernet, 100 Mbps Ethernet.
clip_image080

After you successfully create the topology like here,

Be sure you are in Realtime mode.
clip_image108
Select the Add Simple PDU tool used to ping devices.
clip_image110

Click once on PC0, then once on PC3.
The PDU Last Status should show as Successful.
clip_image118

For a detailed successful topology creation and traffic flow, click here.


Variation of Linked List

In this tutorial we are going to discuss some variations of linked list.

Doubly-linked List
If you look at single link list, the chain is seen formed in a way that every node has a field next that point to the next node. This continues till the last node where we set the next to NULL i.e. the end of the list. There is a headNode pointer that points to the start of the list. We have seen that moving forward is easy in single link list but going back is difficult. For moving backward, we have to go at the start of the list and begin from there. Do you need a list in which one has to move back or forward or at the start or in the end very often? If so, we have to use double link list.
In doubly-link list, a programmer uses two pointers in the node, i.e. one to point to next node and the other to point to the previous node. Now our node factory will create a node with three parts.

clip_image005
First part is prev i.e. the pointer pointing to the previous node, second part is element, containing the data to be inserted in the list. The third part is next pointer that points to the next node of the list. The objective of prev is to store the address of the previous node.
Let’s discuss the code of the node of the doubly-link list. This node factory will create nodes, each having two pointers. The interface methods are same as used in singly link list. The additional methods are getPrev and setPrev. The method getPrev returns the address of the previous node. Thus its return type is Node*. The setPrev method sets the prev pointer. If we have to assign some address to prev pointer, we will call this method. Following is the code of the doubly-linked list node.

/* this is the doubly-linked list class, it uses the next and prev pointers */
class Node {
public:
int get() { return object; }; // returns the value of the element
void set(int object) { this->object = object; }; // set the value of the element
Node* getNext() { return nextNode; }; // get the address of the next node
void setNext(Node* nextNode) // set the address of the next node
{ this->nextNode = nextNode; };
Node* getPrev() { return prevNode; }; // get the address of the prev node
void setPrev(Node* prevNode) // set the address of the prev node
{ this->prevNode = prevNode; };
private:
int object; // it stores the actual value of the element
Node* nextNode; // this points to the next node
Node* prevNode; // this points to the previous node
};


Most of the methods are same as those in singly linked list. A new pointer prevNode is added and the methods to get and set its value i.e. getPrev and setPrev. Now we will use this node factory to create nodes.
You have to be very cautious while adding or removing a node in a doubly linked list. The order in which pointers are reorganized is important. Let’s have a pictorial view of doubly-link list. The diagram can help us understand where the prevNode and nextNode are pointing.

clip_image006
 
This is a doubly link list. The arrows pointing towards right side are representing nextNode while those pointing towards left side are representing prevNode. Suppose we are at the last node i.e. the node with value 1. In case of going back, we usually take the help of prevNode pointer. So we can go to the previous node i.e. the node with value 7 and then to the node with value 8 and so on. In this way, we can traverse the list from the end to start. We can move forward or backward in doubly-link list very easily. We have developed this facility for the users to move in the list easily.
Let’s discuss other methods of the doubly-linked list. Suppose we have created a new node from the factory with value 9. We will request the node factory to create a new object using new keyword. The newly created node contains three fields i.e. object, prevNode and nextNode. We will store 9 into object and connect this new node in the chain. Let’s see how the pointers are manipulated to do that. Consider the above diagram, the current is pointing at the node with value 6. The new node will be inserted between the node with value 6 and the one with value 8.
In the first step, we assign the address of the node with value 8 to the nextNode of the new node.
newNode->setNext( current->getNext() );

clip_image007
In the next step, a programmer points the prevNode of the newNode to the node with value 6.
newNode->setprev( current );

clip_image008
In the third step, we will set the previous node with value 8 to point to the newNode.
(current->getNext())->setPrev(newNode);
clip_image009
Now the prevNode of the node with value 8 is pointing to the node with value 9.
In the fourth step, the nextNode of the node with value 6 is pointing to the newNode i.e. the node with value 9. Point the current to the newNode and add one to the size of the list.
current->setNext( newNode );
current = newNode;
size++;
clip_image010
Now the newNode has been inserted between node with value 6 and node with value 8.

Circularly-linked lists

Let’s talk about circularly linked list. The next field in the last node in a singly-linked list is set to NULL. The same is the case in the doubly-linked list. Moving along a singly-linked list has to be done in a watchful manner. Doubly-linked lists have two NULL pointers i.e. prev in the first node and next in the last node. A way around this potential hazard is to link the last node with the first node in the list to create a circularly-linked list.
The next method in the singly-linked list or doubly-linked list moves the current pointer to the next node and every time it checks whether the next pointer is NULL or not. Similarly the back method in the double-linked list has to be employed carefully if the current is pointing the first node. In this case, the prev pointer is pointing to NULL. If we do not take care of this, the current will be pointing to NULL. So if we try to access the NULL pointer, it will result in an error. To avoid this, we can make a circularly linked list.
We have a list with five elements. We have connected the last node with the first node. It means that the next of the last node is pointing towards the first node.

clip_image011
The same list has been shown in a circular shape.

clip_image012
 
You have noticed that there is no such node whose next field is NULL. What is the benefit of this? If you use the next or back methods that move the current pointer, it will never point to NULL. It may be the case that you keep on circulating in the list. To avoid this, we get help from the head node. If we move the head node in the circularly linked list, it will not be certain to say where it was pointing in the start. Its advantages depend on its use. If we do not have to move too much in the list and have no problem checking the NULL, there is little need a circularly-linked list. But this facility is available to us.
In this example, we made a circular linked list from a singly link list. In a singly link list we move in one direction. We point the next pointer of the last node to the first node. We can do the same with the doubly-linked list. The prev pointer of the first node will point to the last node and the next pointer of the last node will point to the first node. If you arrange all the nodes in a circle, one of the pointers (i.e. next pointer) will move in clockwise direction while the prev pointers in anti-clockwise direction. With the help of these pointers, you can move in the clockwise direction or anti-clockwise direction. Head node pointer will remain at its position. You don’t need to change it. If there is a need to remove the node pointed by head node than you have to move the head pointer to other node. Now we don’t have any NULL pointer in the doubly-linked list. We will not get any exception due to NULL pointers.


Benefits of using circular list

While solving the Josephus problem, it was witnessed that the usage of circular linked list helped us make the solution trivial. We had to just write a code of some lines that solved the whole problem. In the program, we included the class CList (which is of our data structure i.e. circular linked list) and used all of its methods according to the requirements. There was no problem regarding the working of the methods. We just called these methods and their definition in the class CList worked well.

Now we will see what happens if we solve the Josephus problem by using an array instead of the class in our program. In this case, we have to define an array and write code to move back and forth in the array and to remove different elements properly in a particular order. A programmer needs to be very careful while doing this, to reach the solution of the problem. Thus our code becomes very complex and difficult for someone to understand and modify it. Moreover we cannot use this code in some other problem. There is no need to be worried whether an array, singly linked list, doubly linked list is used or circular linked list being employed internally in implementing the list in defining the class of list data type. We only want that it should create objects of list. The usage of the class of a data structure simplifies the code of the program. We can also use this class wherever needed in other programs. This shows that the choice of appropriate data structures can simplify an algorithm. It can make the algorithm much faster and efficient.


C program to Read From a File

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