Classes and Object

The most important principle of object-oriented programming is Classes and Objects.

A Class is a group of things(objects) which have similar properties or behaviour. For example - "Fruit" is a class. Why? because the word "Fruit" does not specify a particular fruit but all the types of fruits. In real life there is nothing called a "fruit", which means that if you go to a fruit seller and tell him that - I want to buy a fruit - he will ask you to specify which fruit exactly do you want to buy. All the examples of a "fruit" like Orange, Banana, Apple or any other are instances of simply examples of "fruit", that's why they are called "Objects". Objects are found in real world not the class. Classes are simply created to refer to all the similar objects easily.

The method invoked by an object in response to a message is determined by the class of the receiver. All objects of a given class use the same method in response to similar messages. Apple is an instance of a category or class of Fruit i.e. Apple is an instance of a class of fruits. The term fruit represents a class or category of all fruits. We interact with instances of a class but the class determines the behaviour of instances.

We can tell a lot about how Apple will taste by understanding how fruits taste. We know, for example, that Apple, like most fruits will have juice and will taste sweet.

In the real world there is this distinction between classes and objects. Real-world objects share two characteristics: They all have state and behavior. For example, dogs have state (name, color, breed, hungry) and behavior (barking, fetching, wagging tail). Students have state (name, student number, courses they are registered for, gender) and behavior (take tests, attend courses, write tests, party).

Basics of Objects and Classes

We move now from the conceptual picture of objects and classes to a discussion of software classes and objects. Objects are closely related to classes. A class can contain variables and methods. If an object is also a collection of variables and methods, how do they differ from classes?

Objects and Classes

Objects

In object-oriented programming we create software objects that model real world objects.Software objects are modeled after real-world objects in that they too have state and behavior. A software object maintains its state in one or more variables. A variable is an item of data named by an identifier. A software object implements its behavior with methods. A method is a function associated with an object.

Definition: An object is a collection of variables and related methods. An object is also known as an instance. An instance refers to a particular object. For e.g. My car is an instance of a car—It refers to a particular car. Allen is an instance of a Student. The variables of an object are formally known as instance variables because they contain the state for a particular object or instance. In a running program, there may be many instances of an object. For e.g. there may be many Student objects. Each of these objects will have their own instance variables and each object may have different values stored in their instance variables. For e.g. each Student object will have a different number stored in its StudentNumber variable.

Object Orientation As a Paradigm

It is claimed that the problem-solving techniques used in object-oriented programming is very close to the way we day-to-day problems. This is why the use of Object Oriented techniques has become very useful and popular in modern day programming languages like Java, VC#.Net etc. Let's try to understand how Object Oriented programming is close to our daily life with the help of an example.

Suppose you wanted to send a gift to a friend named James who lives in another city.To solve this problem you simply walk to your nearest gift shop run by, lets say, Scott. You tell Scott the kind of gift you want to send to James, your budget, along with the address of James. Once you are done with these things, you can be sure that the gift will be delivered.

Now, lets examine the steps used to solve your problem.

• You first found an appropriate agent (Scott, in this example) and you passed to this agent a message containing a request.

• It is the responsibility of Scott to satisfy the request.

• There is some method (an algorithm or set of operations) used by Scott to do this.

• You do not need to know the particular methods used to satisfy the request—such information is hidden from view. Ofcourse, you do not want to know the details, but on investigation you may find that Scott delivered a slightly different message to another gift shop in the city where your friend James lives. That person then passes another message to a subordinate who makes the final arrangement.The gift, along with yet another message, is passed onto a delivery person and so on.

This leads to our first conceptual picture of object-oriented programming: An object-oriented program is structured as community of interacting agents called objects. Each object has a role to play. Each object provides a service or performs an action that is used by other members of the community.  Messages and Responsibilities Members of an object-oriented community make requests of each other.
The next important principle explains the use of messages to initiate action:

Action is initiated in object-oriented programming by the transmission of a message to an agent (an object) responsible for the actions. The message encodes the request for an action and is accompanied by any additional information (arguments/parameters) needed to carry out the request. The receiver is the object to whom the message is sent. If the receiver accepts the message, it accepts responsibility to carry out the indicated action. In response to a message, the receiver will perform some method to satisfy the request.

There are some important issues to point out here:

• The client sending the request need not know the means by which the request is carried out. In this we see the principle of information hiding.

• Another principle implicit in message passing is the idea of finding someone else to do the work i.e. reusing components that may have been written by someone else.

• The interpretation of the message is determined by the receiver and can vary with different receivers. For example, if you sent the message “deliver gift” to a friend, he will probably have understood what was required and gift would still have been delivered but the method he used would have been very different from that used by the person in the example.

• In object-oriented programming, behaviour is described in terms of responsibilities.

• Client’s requests for actions only indicates the desired outcome. The receivers are free to pursue any technique that achieves the desired outcomes.

• Thinking in this way allows greater independence between objects.

• Thus, objects have responsibilities that they are willing to fulfill on request. The collection of reponsibilities associated with an object is often called a protocol.

Programming Paradigms

Programming Paradigms

Object-oriented programming is one of several programming paradigms. Other programming paradigms include the imperative programming paradigm (as exemplified by languages such as Pascal or C), the logic programming paradigm (Prolog), and the functional programming paradigm (exemplified by languages such as ML, Haskell or Lisp). Logic and functional languages are said to be declarative languages. We use the word paradigm to mean “any example or model”. This usage of the word was popularized by the science historian Thomas Kuhn.He used the term to describe a set of theories, standards and methods that together represent a way of organising knowledge—a way of viewing the world. Thus a programming paradigm is a "way of conceptualizing what it means to perform computation and how tasks to be carried out on a computer should be structured and organized".
We can distinguish between two types of programming languages: Imperative languages and declarative languages. Imperative knowledge describes how-to knowledge while declarative knowledge is what-is knowledge. A program is ”declarative” if it describes what something is like, rather than how to create it. This is a different approach from traditional imperative programming languages such as Fortran, and C, which require the programmer to specify an algorithm to be run. In short, imperative programs make the algorithm explicit and leave the goal implicit, while declarative programs make the goal explicit and leave the algorithm implicit.
Imperative languages require you to write down a step-by-step recipe specifing how something is to be done. For example to calculate the factorial function in an imperative language we would write something like:
public int factorial(int n) {
int ans=1;
for (int i = 2; i <= n; i++){
ans = ans i;
}
return ans;
}
Here, we give a procedure (a set of steps) that when followed will produce the answer.
12

Functional programming
Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. Functional programming emphasizes the definition of functions, in contrast to procedural programming, which emphasizes the execution of sequential commands. The following is the factorial function written in a functional language called Lisp:
(defun factorial (n)
(if (<= n 1) 1 ( n (factorial (− n 1))))
)
Notice that it defines the factorial function rather than give the steps to calculate it.
The factorial of n is defined as 1 if n <= 1 else it is n factorial(n − 1)

Logic Programming
Prolog (PROgramming in LOGic) 2 is the most widely available language in the logic programming paradigm. It is based on the mathematical ideas of relations and logical inference. Prolog is a declarative language meaning that rather than describing how to compute a solution, a program consists of a data base of facts and logical relationships (rules) which describe the relationships which hold for the given application.
Rather then running a program to obtain a solution, the user asks a question. When asked a question, the run time system searches through the data base of facts and rules to determine (by logical deduction) the answer.
Logic programming was an attempt to make a programming language that enabled the expression of logic instead of carefully specified instructions on the computer. In the logic programming language Prolog you supply a database of facts and rules; you can then perform queries on the database.
The factorial function is written in prolog as two rules. Again, notice the declarative nature of the program.
fac(0,1).
fac(N,F) :− N > 0,
M is N − 1,
fac(M,Fm),
F is N * Fm.
To summarize:
• In procedural languages, everything is a procedure.
• In functional languages, everything is a function.
• In logic programming languages, everything is a logical expression (predicate).
• In object-oriented languages, everything is an object.

Object Oriented Programming

Oriented Programming
Introduction

Object Oriented Programming, also known as OOP, is a programming methodology in which a computer application is designed as things are in the real world. Object Oriented Programming (OOP) represents an attempt to make programs more closely model the way people think about and deal with the world. In the older styles of programming, a programmer who is faced with some problem must identify a computing task that needs to be performed in order to solve the problem. Programming then consists of finding a sequence of instructions that will accomplish that task. But at the heart of object-oriented programming, instead of tasks we find objects – entities that have behaviors, that hold information, and that can interact with one another. Programming consists of designing a set of objects that model the problem at hand.
With OOP, every object can handle data, get messages, and transfer messages to other objects. The objects will all act as independent units in their own right, and they will be responsible for carrying out a certain process. Software objects in the program can represent real or abstract entities in the problem domain. This is supposed to make the design of the program more natural and hence easier to get right and easier to understand.

What is Object Oriented Programming?
Object-Orientation is a set of tools and methods that enable software engineers to build reliable, user friendly, maintainable, well documented, reusable software systems that fulfills the requirements of its users. It is claimed that object-orientation provides software developers with new mind tools to use in solving a wide variety of problems. Object-orientation provides a new view of computation. A software system is seen as a community of objects that cooperate with with each other by passing messages in solving a problem.  An object-oriented programming language provides support for the following object oriented concepts:

1. Abstraction
2. Encapsulation
3. Inheritance
4. Polymophism
5.  Dynamic binding

Binary Sorted Tree : Source Code

1. #include
2. #include
3. #include
4. struct tree
5. {
6. int data;
7. tree *left;
8. tree *right;
9. }*root;
10.  
12. void main()
13. {
14. root=NULL;
15. int d;
16. void add();
17. void traverse(tree *);
18. tree* del(tree *,int);
19. int c;
20. do
21. {
22. printf("\nM A I N M E N U ");
23. printf("\n=====================");
24. printf("\n1. Add a node ");
25. printf("\n2. Display tree");
26. printf("\n3. Delete a node");
27. printf("\n4. Quit");
28. printf("\nSelect your choice ");
29. scanf("%d",&c);
30. if(c==1)
31. add();
32. else if(c==2)
33. traverse(root);
34. else if(c==3)
35. {
36. printf("\nEnter data to delete ");
37. scanf("%d",&d);
38. root=del(root,d);
39. }
40. }while(c!=4);
41. }
42.  
43. void add()
44. {
45. printf("\nAdd a node ");
46. tree *t,*prev;
47. tree *search(tree *,int);
48. t=(tree *)malloc(sizeof(tree));
49. printf("\nEnter data ");
50. scanf("%d",&t->data);
51. if(root==NULL)
52. {
53. root=t;
54. t->left=NULL;
55. t->right=NULL;
56. }
57. else
58. {
59. prev=search(root,t->data);
60. if(prev==NULL)
61. {
62. printf("\nNode already exists");
63. return;
64. }
65. else if(prev->data>t->data)
66. {
67. prev->left=t;
68. }
69. else
70. prev->right=t;
71. t->left=NULL;
72. t->right=NULL;
73. }
74. printf("\nNode Added ");
75. }
76.  
77. tree *search(tree *r,int d)
78. {
79. tree *prev;
80. while(r!=NULL)
81. {
82. if(r->data==d)
83. return NULL;
84. else if(r->data>d)
85. {
86. prev=r;
87. r=r->left;
88. }
89. else
90. {
91. prev=r;
92. r=r->right;
93. }
94. }
95. return prev;
96. }
97. void traverse(tree *r)
98. {
99. if(r==NULL)
100. return;
101. traverse(r->left);
102. printf("\n%d",r->data);
103. traverse(r->right);
104. }
105. tree *del(struct tree *root, int key)
106. {
107. tree *p,*p2;
108. if(!root)
109. return root;
110. if(root->data == key)
111. {
112. if(root->left == root->right){
113. free(root);
114. return NULL;
115. }
116. else if (root->left == NULL)
117. {
118. p = root->right;
119. free(root);
120. return p;
121. }
122. else if(root->right == NULL)
123. {
124. p = root->left;
125. free(root);
126. return p;
127. }
128. else
129. {
130. p2 = root->right;
131. p = root->right;
132. while(p->left)
133. p = p->left;
134. p->left = root->left;
135. free(root);
136. return p2;
137. }
138. }
139. if(root->data < key)
140. root->right = del(root->right, key);
141. else
142. root->left = del(root->left, key);
143. return root;
144. }

Binary Sorted Trees

A linked list,stack or a queue work fine for a small number of items, but when it comes to search for an item all the three data structures require a lot of time. Searching for an item's position requires comparing the value to be searched with each item in the list. Suppose there are 100 values in a linked list and the value that we want to find is stored in the last node, then it will take 100 comparisons to find the desired value.

Binary Sorted Tree

A binary sorted tree is a type of binary tree in which values are stored in respect to the root node. All the nodes having data less than the root's data are stored to the left of the root, while the nodes having a value more than the root's value are stored to the right of root. A binary tree can be used to store an ordered list of strings, or other items, in a way that makes both searching and insertion efficient. A binary tree used in this way is called a binary sort tree.

A binary sort tree has the following properties

For every node in the tree, the item in that node is greater than every item in the left subtree of that node, and it is less than or equal to all the items in the right subtree of that node. Take a look at the picture, you will see that all the nodes to the left of the root have smaller data while the right ones have larger data in comparison to the root.

The Advantage

Binary sorted trees offer a very useful advantage - When we traverse a binary sorted tree using the inorder method, all the values of the tree are accessed in ascending order. An inorder traversal of the tree will process the items in increasing order. For example, if an inorder traversal is used to print the items in the tree shown above, then the items will be in increasing order of their numerical value. The inorder traversal ensures that 1 will be printed before 2 and 2 will be printed before 3.Suppose that we want to search for a given item in a binary search tree. The item will be first compared with the root item of the tree. If they are equal,the search operation stops there. If the item we are searching for is less than the root item, then the value will be searched in the left subtree of the root ,the right subtree can be eliminated because it only contains items that are greater than or equal to the root. Similarly, if the item we are looking for is greater than the item in the root, then we only need to look in the right subtree. In either case, the same procedure can then be applied to search the subtree. Inserting a new item is similar: Start by searching the free for the position where the new item belongs. When that position is found, create a new node and attach it to the tree at that position.

Searching and inserting are efficient operations on a binary search tree, provided that the tree is close to being balanced.

A binary tree is balanced if for each node, the left subtree of that node contains approximately the same number of nodes as the right subtree. In a perfectly balanced tree, the two numbers differ by at most one. Not all binary trees are balanced, but if the tree is created randomly, there is a high probability that the tree is approximately balanced. During a search of any binary sort tree, every comparison eliminates one of two subtrees from further consideration. If the tree is balanced, that means cutting the number of items still under consideration in half.

Binary Tree

A Binary tree is a data structure that stores the data hierarchically in the form of a tree. Each node of a binary tree has 2 pointers usually called left and right. Additionally , the nodes can contain other types of data. For example, a binary tree of integers could be made up of objects of the following type:

struct tree {

int item; // The data in this node.

tree * left; // Pointer to the left subtree.

tree * right; // Pointer to the right subtree.

}



Binary Tree



The top most node of a tree is called the "root" node. A tree always starts from the root. The left and right pointers in a TreeNode can point to one,two or no nodes. A node that points to another node is said to be the parent of that node, and the node it points to is called a child. In the given picture , for example, node 7 is the parent of node 6, and nodes 5 and 11 are children of node 6. Not every linked structure made up of tree nodes is a binary tree.

A binary tree must have the following properties: There is exactly one node in the tree which has no parent. This node is called the root of the tree. Every other node in the tree has exactly one parent. Finally, there can be no loops in a binary tree. That is, it is not possible to follow a chain of pointers starting at some node and arriving back at the same node. A node that has no children is called a leaf or a terminal node. A leaf node has both the left and right pointers as null. In the standard picture of a binary tree, the root node is shown at the top and the leaf nodes at the bottom.

Consider any node in a binary tree. Look at that node together with all its descendents (that is, its children, the children of its children, and so on). This set of nodes forms a binary tree, which is called a subtree of the original tree. For example, in the picture, nodes 7, 2, and 6 form a subtree. This subtree is called the left subtree of the root. Similarly, nodes 5 and 9 make up the right subtree of the root. We can consider any non-empty binary tree to be made up of a root node, a left subtree, and a right subtree. Either or both of the subtrees can be empty. This is a recursive definition, matching the recursive definition of the TreeNode class.

Traversing a binary tree

There are three methods by which a binary tree can be traversed :

1. Preorder : In this type of traversal the root nodes is processed first following by left and right nodes. For example, in the above picture, between 2, 7 and 5, the preorder method will read 2 first, followed by 7 and 5.
2. Postorder : In a postorder traversal, the left subtree is traversed, then the right subtree, and then the root node is processed. In this method of reading 7,5 and 2 will be printed.
3. Inorder : In an inorder traversal, the left subtree is traversed first, then the root node is processed, then the right subtree is traversed. The output for the same set of nodes will be 7,2 and 5.

Queue

A queue is a data structure that stores the data in a linear list which can be accessed in first-in, first-out order, also known as "FIFO". In a queue, the value that is added the first will be the first one to be removed. A data structure queue is similar to a real life queue. For example, in a queue outside a ticket booth, the person standing in the front will be the first one to get the ticket and move out of the queue. Similarly in a data structure queue, the first item placed on the queue is the first item retrieved, the second item put in is the second item retrieved, and so on. This is the only method of storage and retrieval in a queue, you can not randomly access any specific item in a queue.

Queues are similar to stacks in that a queue consists of a sequence of items, and there are restrictions about how items can be added to and removed from the list. However, a queue has two ends, called the front and the back of the queue. Items are always added to the queue at the back and removed from the front. The operations of adding and removing items are usually called enqueue and dequeue. An item that is added to the back of the queue will remain on the queue until all the items in front of it have been removed. This should sound familiar. A queue is like a "line" or "queue" of customers waiting for service. Customers are serviced in the order in which they arrive on the queue.Queues seem very natural because they occur so often in real life, but there are times when stacks are appropriate and even essential. For example, consider what happens when a routine calls a subroutine. The first routine is suspended while the subroutine is executed, and it will continue only when the subroutine returns. Now, suppose that the subroutine calls a second subroutine, and the second subroutine calls a third, and so on. Each subroutine is suspended while the subsequent subroutines are executed. The computer has to keep track of all the subroutines that are suspended. It does this with a stack.

To undestand how a queue works, consider two functions: add( ) and remove( ). The add( ) function places an item in the queue, and remove( ) removes the first item from the queue and returns its value.

Action                                                                         Contents of Queue

add(A)                                                                                     A

add(B)                                                                                   A B

add(C)                                                                                 A B C

remove( ) returns                                                                  A B C

add(D)                                                                                 B C D

remove( ) returns                                                                 B C D

remove( ) returns                                                                  C D

Stack : Source Code

#include

#include

#include

struct stack
{
int data;

stack *next;

}*top; // top will point to the first node of the stack

void main()
{
top=NULL;
void push();
void pop();
void display();
int c;
do
{
printf("\nStack Operations");
printf("\n1. Push (add) ");
printf("\n2. Display");
printf("\n3. Pop (remove)");
printf("\n4. Exit");
printf("\nSelect your choice ");
scanf("%d",&c);
if(c==1)
push();
else if(c==2)
display();
else if(c==3)
pop();
}while(c!=4);
}
void push()
{
stack *s;
s=(stack *)malloc(sizeof(stack));
printf("\nEnter data ");
scanf("%d",&s->data);
if(top==NULL)
{
top=s; // pushing node to the stack
s->;next=NULL;
}
else
{
s->;next=top;
top=s;
}

printf("\nNode Pushed...");
}

void display()
{
stack *ptr;
for(ptr=top;(ptr);ptr=ptr->next)
{
printf("\n%d",ptr->data);
}
}

void pop()
{
stack *temp;
if(top==NULL)
{
printf("\nStack Underflow(no values found)");
return;
}
else
{
temp=top;
top=top->next;
printf("\nPopped Value : %d",temp->data);
free(temp);
}

}

Data Structure : Stack

A stack is a data structure in which nodes are added vertically one over the other. To understand it better, consider a stack of books. Because each book is heavy and they are stacked, you can really only do one of three things:

A stack of books

1. Look at the surface of the top book
2. Take the top book off the stack
3. Put a new book on top of the stack

A Data Structure Stack

In programming, a stack is a container that holds other variables (much like an array). However, whereas an array lets you access and modify elements in any order you wish, a stack is more limited. The operations that can be performed on a stack are identical to the ones above:

1) Look at the top item on the stack (usually done via a function called top())
2) Take the top item off of the stack (done via a function called pop())
3) Put a new item on top of the stack (done via a function called push())


Since it has restrictions regarding insertion and deletion of nodes it is also called "restricted" or "closed ended linked list".  A stack is a last in, first out (LIFO) data structure. If you put a new book on top of the stack, anybody who takes a book from the stack will take the book you just pushed on first. This means that the element which will be added last will be the first one to be removed. As items are pushed onto a stack, the stack grows larger — as items are popped off, the stack grows smaller.Whenever a new element is added to stack the existing elements are pushed a step downwards, similarly when items are removed from the top all the elements are shifted a step upwards. Therefore insertion and deletion in a stack are also called "push" and "pop" respectively.  The push operation adds an item to the top of the stack, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the stack, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty stack.
  The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition: therefore, the lower elements are those that have been on the stack the longest.

Advantages and Disadvantages:

1. Memory allocated on the stack stays in scope as long as it is on the stack. It is destroyed when it is popped off the stack.
2. All memory allocated on the stack is known at compile time. Consequently, this memory can be accessed directly through a variable.
3. Because the stack is relatively small, it is generally not a good idea to do anything that eats up lots of stack space. This includes allocating large arrays, structures, and classes, as well as heavy recursion.

Application of Stack
Stacks can be used to evaluate postfix expressions. An ordinary mathematical expression such as 2+(15-12)*17 is called an infix expression. In an infix expression, an operator comes in between its two operands, as in "2 + 2". In a postfix expression, an operator comes after its two operands, as in "2 2 +". The infix expression "2+(15-12)*17" would be written in postfix form as "2 15 12 - 17 * +". The "-" operator in this expression applies to the two operands that precede it, namely "15" and "12". The "*" operator applies to the two operands that precede it, namely "15 12 -" and "17". And the "+" operator applies to "2" and "15 12 - 17 *". These are the same computations that are done in the original infix expression.

Now, suppose that we want to process the expression "2 15 12 - 17 * +", from left to right, and find its value. The first item we encounter is the 2, but what can we do with it? At this point, we don't know what operator, if any, will be applied to the 2 or what the other operand might be. We have to remember the 2 for later processing. We do this by pushing it onto a stack. Moving on to the next item, we see a 15, which is pushed onto the stack on top of the 2. Then the 12 is added to the stack. Now, we come to the operator, "-". This operation applies to the two operands that preceded it in the expression. We have saved those two operands on the stack. So, to process the "-" operator, we pop two numbers from the stack, 12 and 15, and compute 15 - 12 to get the answer 3. This 3 will be used for later processing, so we push it onto the stack, on top of the 2, which is still waiting there. The next item in the expression is a 17, which is processed by pushing it onto the stack, on top of the 3. To process the next item, "*", we pop two numbers from the stack. The numbers are 17 and the 3 that represents the value of "15 12 -". These numbers are multiplied, and the result, 51 is pushed onto the stack. The next item in the expression is a "+" operator, which is processed by popping 51 and 2 from the stack, adding them, and pushing the result, 53, onto the stack. Finally, we've come to the end of the expression. The number on the stack is the value of the entire expression, so all we have to do is pop the answer from the stack, and we are done! The value of the expression is 53.

Introduction to C

The C programming language was devised in the early 1970s by Dennis M. Ritchie an employee from Bell Labs (AT&T).

In the 1960s Ritchie worked, with several other employees of Bell Labs (AT&T), on a project called Multics. The goal of the project was to develop an operating system for a large computer that could be used by a thousand users. In 1969 AT&T (Bell Labs) withdrew from the project, because the project could not produce an economically useful system. So the employees of Bell Labs (AT&T) had to search for another project to work on (mainly Dennis M. Ritchie and Ken Thompson).

Ken Thompson began to work on the development of a new file system. He wrote, a version of the new file system for the DEC PDP-7, in assembler. (The new file system was also used for the game Space Travel). Soon they began to make improvements and add expansions. (They used there knowledge from the Multics project to add improvements). After a while a complete system was born. Brian W. Kernighan called the system UNIX, a sarcastic reference to Multics. The whole system was still written in assembly code. Besides assembler and Fortran, UNIX also had an interpreter for the programming language B. ( The B language is derived directly from Martin Richards BCPL). The language B was developed in 1969-70 by Ken Thompson. In the early days computer code was written in assembly code. To perform a specific task, you had to write many pages of code. A high-level language like B made it possible to write the same task in just a few lines of code. The language B was used for further development of the UNIX system. Because of the high-level of the B language, code could be produced much faster, then in assembly.

A drawback of the B language was that it did not know data-types. (Everything was expressed in machine words). Another functionality that the B language did not provide was the use of “structures”. The lag of these things formed the reason for Dennis M. Ritchie to develop the programming language C. So in 1971-73 Dennis M. Ritchie turned the B language into the C language, keeping most of the language B syntax while adding data-types and many other changes. The C language had a powerful mix of high-level functionality and the detailed features required to program an operating system. Therefore many of the UNIX components were eventually rewritten in C (the Unix kernel itself was rewritten in 1973 on a DEC PDP-11).

The programming language C was written down, by Kernighan and Ritchie, in a now classic book called “The C Programming Language, 1st edition”. (Kernighan has said that he had no part in the design of the C language: “It’s entirely Dennis Ritchie’s work”. But he is the author of the famous “Hello, World” program and many other UNIX programs).

For years the book “The C Programming Language, 1st edition” was the standard on the language C. In 1983 a committee was formed by the American National Standards Institute (ANSI) to develop a modern definition for the programming language C (ANSI X3J11). In 1988 they delivered the final standard definition ANSI C. (The standard was based on the book from K&R 1st ed.). The standard ANSI C made little changes on the original design of the C language. (They had to make sure that old programs still worked with the new standard). Later on, the ANSI C standard was adopted by the International Standards Organization (ISO). The correct term should there fore be ISO C, but everybody still calls it ANSI C.

Circular Linked List : Source Code

#include
#include

#include

struct vehicle
{

int veh_no;
vehicle *next;

}*end;

void main()
{
void add_node();
void add_beg();
void add_after();
void traverse();
void del();

int ch;
end=NULL;
while(ch!=6)
{
printf("\n1. Add Node");
printf("\n2. Add a node at the begining");
printf("\n3. Add after a node");
printf("\n4. Display all nodes");
printf("\n5. Delete a node");
printf("\n6. Quit");
printf("\nSelect your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1: add_node();
break;
case 2: add_beg();
           break;
case 3: add_after();
         break;
case 4: traverse();
break;
case 5: if(end == NULL)
{
printf("The vehicle list is empty");
}
else
del();
break;
case 6:
exit(0);
default:
printf("Wrong choice\n");
}
}
}
void add_node()
{
vehicle *q,*ptr;
int num;
ptr= (vehicle *)malloc(sizeof(vehicle));
printf("Enter the vehicle no : ");
scanf("%d",&num);
ptr->veh_no = num;
if(end == NULL)
{
end = ptr;
ptr->next = end;
}
else
{
ptr->next = end->next;  end->next = ptr;
end = ptr;
}
}

void add_beg()
{
vehicle *ptr;
int num;
printf("Enter the vehicle no : ");
scanf("%d",&num);
ptr =(vehicle *) malloc(sizeof(struct vehicle));
ptr->veh_no = num;
ptr->next = end->next;
end->next = ptr;
}

void add_after()
{
vehicle *ptr,*q;
int i,num,idx;
printf("Enter the vehicle no : ");
scanf("%d",&num);
printf("Enter the index no. after which you want to add the vehicle : ");
scanf("%d",&idx);
q = end->next;
for(i=0; i < idx-1; i++)
{
q = q->next;
if(q == end->next)
{
printf("There are less than %d elements\n",idx);
return;
}
}
ptr = (vehicle *)malloc(sizeof(vehicle) );
ptr->next = q->next;
ptr->veh_no = num;
q->next = ptr;
if(q==end)
end=ptr;
}

void del()
{
int num;
vehicle *ptr,*q;
printf("Enter the vehicle number that you want to delete : ");
scanf("%d",&num);
if( end->next == end && end->veh_no == num)
{
ptr = end;
end = NULL;
free(ptr);
return;
}
q = end->next;
if(q->veh_no == num)
{
ptr = q;
end->next = q->next;
free(ptr);
return;
}
while(q->next != end)
{
if(q->next->veh_no == num)
{
ptr = q->next;
q->next = ptr->next;
free(ptr);
printf("%d Vehicle Record deleted\n",num);
return;
}
q = q->next;
}
if(q->next->veh_no == num)
{
ptr = q->next;
q->next = end->next;
free(ptr);
end = q;
return;
}
printf("\nVehicle no %d does not exists",num);
}

void traverse()
{
vehicle *q;
if(end == NULL)
{
printf("No Vehicles Found");
return;
}
q = end->next;
printf("List is :\n");
while(q != end)
{
printf("%d ", q->veh_no);
q = q->next;
}
printf("%d\n",end->veh_no);
}

Circular Linked List

A circular linked list is a type of linked list in which the last node of the list points back to the first node. In single or double linked list the last node contains a NULL pointer since there is no next node, whereas in a circular linked list the "next" pointer of the last node contains the address of the first node. Therefore it is called a circular linked list. A circular linked has a "start" node, but no "end" node. In a Circular Linked List all the nodes are linked in continuous circle. Whatever operations are possible using singly linked lists, all those operations can be performed using circular lists also. A circular list can be used as a stack, queue or a deque.

It can be both Singly or doubly linked list. In a circular linked list elements can be added to the back of the list and removed from the front in constant time.Both types of circularly-linked lists benefit from the ability to traverse the full list beginning at any given node. This avoids the necessity of storing first Node and last node, but we need a special representation for the empty list, such as a last node variable which points to some node in the list or is null if it's empty. This representation significantly simplifies adding and removing nodes with a non-empty list, but empty lists are then a special case.Circular linked lists are most useful for describing naturally circular structures,and have the advantage of being able to traverse the list starting at any point. They also allow quick access to the first and last records through a single pointer (the address of the last element).

Double Linked List : Source Code

#include
#include
#include
struct viewer
{
int seatno;
char vname[20];
char address[30];
viewer *next;
viewer *prior;
}*start,*end; // To point to the first and last node respectively.

void main()
{
start=NULL;
end=NULL;
void add();
void traverse(); // from start to end
void rtraverse(); // from end to start
void search();
void del();
int c;
do
{
printf("\nDOUBLE LINKED LIST - MAIN MENU");
printf("\n1. Add a node");
printf("\n2. Print all nodes");
printf("\n3. Print Reverse");
printf("\n4. Search");
printf("\n5. Delete");
printf("\n6. Quit");
printf("\nSelect your choice ");
scanf("%d",&c);
if(c==1)
add();
else if (c==2)
traverse();
else if(c==3)
rtraverse();
else if(c==4)
search();
else if(c==5)
del();
}while(c!=6);
}
void add()
{
clrscr();
viewer *v;
printf("\n A D D  A  N O D E ");
v=(viewer *)malloc(sizeof(viewer));
printf("\nEnter Seat No ");
scanf("%d",&v->seatno);
fflush(stdin);
printf("\nEnter Name ");
gets(v->vname);
fflush(stdin);
printf("\nEnter Address ");
gets(v->address);
if(start==NULL)
{
start=v;
end=v;
v->next=NULL;
v->prior=NULL;
}
else
{
v->prior=end;
end->next=v;
v->next=NULL;
end=v;
}

}
void traverse()
{
clrscr();
viewer *v;
if(start==NULL)
{
printf("\nNo Nodes Added Yet...");
return;
}
for(v=start;(v);v=v->next)
{
printf("\nSeat No. : %d",v->seatno);
printf("\nName of the viewer : %s",v->vname);
printf("\nAddress of the viewer : %s",v->address);
printf("\n---------------------------");
}
printf("\nEnd of list");
printf("\nPress enter to continue..");
getch();
clrscr();
}
void rtraverse()
{
viewer *v;
for(v=end;(v);v=v->prior)
{
printf("\nSeat No. : %d",v->seatno);
printf("\nName of the viewer : %s",v->vname);
printf("\nAddress of the viewer : %s",v->address);
printf("\n---------------------------");
}
}
void search()
{
clrscr();
printf("\nSearch a node");
int sno,flag;
char ch;
viewer *v;
if(start==NULL)
{
printf("\nNo Node Found");
return;
}
printf("\nEnter Seat No To Search : ");
scanf("%d",&sno);
for(v=start;(v);v=v->next)
{
if(v->seatno==sno)
{
flag=1;
printf("\nSeat no Found");
printf("\n=============");
printf("\nSeat No.: %d",v->seatno);
printf("\nName of the viewer : %s",v->vname);
printf("\nAddress of the viewer : %s",v->address);
fflush(stdin);
printf("\nDo you want to modify the data? : ");
scanf("%c",&ch);
if(ch=='y'  || ch=='Y')
{
printf("\nEnter New seat no "); // overwriting the data
scanf("%d",&v->seatno);
fflush(stdin);
printf("\nEnter New Name ");
gets(v->vname);
fflush(stdin);
printf("\nEnter new Address ");
gets(v->address);
printf("\nRecord Updated !!");
}
}


}


if(flag!=1)
printf("\nSeat no %d not found",sno);
}
void del()
{
clrscr();
printf("\nDelete a node");
viewer *v,*prev;
int sno,flag;
char ch;
if(start==NULL)
{
printf("\nNo node Found");
return;
}
printf("\nEnter Seat no To Delete : ");
scanf("%d",&sno);
for(v=start;(v);v=v->next)
{
if(v->seatno==sno)
{
flag=1;
printf("\nSeat no. Found");
printf("\n=============");
printf("\nSeat no : %d",v->seatno);
printf("\nName of the viewer : %s",v->vname);
printf("\nAddress of the viewe : %s",v->address);
fflush(stdin);
printf("\nDo you want to delete the node? : ");
scanf("%c",&ch);
if(ch=='y' || ch=='Y')
{
if(v->next==NULL)
{prev->next=NULL;
end=prev;
}
else if(v==start)
{
start=v->next;
start->prior=NULL;
}
else
{
v->prior->next=v->next;
v->next->prior=v->prior;
}
free (v);
printf("\nNode Deleted");
}
}
prev=v;
}
if(flag!=1)
printf("\nSeat no %d not found",sno);
}

Double Linked List

A double linked list is a linked list in which a node is divided into three parts - previous, data and next. The data part contains the data to be stored, while the previous and next part contain the address of the previous and next node respectively.

A double linked list is different from a single linked list in the following ways:

1.  A node in a single linked list keeps track only of the next node, while a double linked list node not only stores the address of the next node but also of the previous node. The first and the last nodes of the list contains a "NULL" in their previous and next part since there is no node to which they can point.
2. In a single list a pointer called "start" or "head" points to the first node, but in a double linked list apart from "start", there is one more pointer called "end" which points to the last node of the list.
3. A double linked list can be read both ways - from start to end and from end to start.

Advantages
The primary advantage of a doubly linked list is that given a node in the list, one can navigate easily in either direction. This can be very useful, for example, if the list is storing strings, where the strings are lines in a text file (e.g., a text editor). One might store the "current line'' that the user is on with a pointer to the appropriate node; if the user moves the cursor to the next or previous line, a single pointer operation can restore the current line to its proper value. Or, if the user moves back 10 lines, for example, one can perform 10 pointer operations (follow the chain) to get to the right line. For either of these operations, if the list is singly linked, one must start at the head of the list and traverse until the proper point is reached. This can be very inefficient for large lists.

Disadvantages

The disadvantage of doubly linked lists are

1. Each node requires an extra pointer, therefore more memory is required.
2. The insertion or deletion of a node takes a bit longer since there are more pointers to update.

 This is how a double linked list looks like.

Double Linked List

Operations on a double linked list.

Operations that can be performed on a double linked list are similar to those of single linked list. The only additional task that can be performed on a double linked list is that a double linked list can be traveresed both ways.

1. Insertion (At the beginning, end or middle)
2. Deletion
3. Traversal (From start to end)
4. Reverse Traversal (From end to start)
5. Search