Inderprastha Engineering College, Ghaziabad

Data Structure
(KCS 301)

Course Outcome (CO) Blooms’s

Knowledge
Level (KL)

At the end of the course, students will be able to

CO1 Describe how arrays, linked lists, stacks, queues, tree and graphs are K1, K2
represented in memory used by the algorithms and their common
applications
CO2 Discuss the computational efficiency of the sorting and searching K2
algorithms.

CO3 Implementation of trees and graphs and perform various operations on K3

these data structure.

CO4 Understand the concept of recursion, application of recursion and its K4

implementation and removal of recursion.

CO5 Identify the alternative implementations of data structure with respect to its K5, K6
performance to solve real world problem.
UNIT 1
Introduction to Data structures
In computer terms, a data structure is a Specific way to store and organize data in a computer's
memory so that these data can be used efficiently later. Data may be arranged in many different ways
such as the logical or mathematical model for a particular organization of data is termed as a data
structure. The variety of a particular data model depends on the two factors -
Firstly, it must be loaded enough in structure to reflect the actual relationships of the data
with the real world object.
Secondly, the formation should be simple enough so that anyone can efficiently process
the data each time it is necessary.
Categories of Data Structure:

Data Structure

Primitive Non Primitive

Integer Array List Files

Float Character

Linear List Non Linear List

Stack Queue Graph Tree

The data structure can be sub divided into major types:

Linear Data Structure
Non-linear Data Structure
Linear Data Structure:
A data structure is said to be linear if its elements combine to form any specific order. There are
basically two techniques of representing such linear structure within memory.
First way is to provide the linear relationships among all the elements representedby means
of linear memory location. These linear structures are termed as arrays.
The second technique is to provide the linear relationship among all the elements
represented by using the concept of pointers or links. These linear structures are termed as linked
lists.
The common examples of linear data structure are:
Arrays
Queues
Stacks
Linked lists
Non linear Data Structure:
This structure is mostly used for representing data that contains a hierarchical relationship
among various elements.
Examples of Non Linear Data Structures are listed below:
Graphs
family of trees and
table of contents
Tree: In this case, data often contain a hierarchical relationship among various elements.
Basic Concepts: Introduction to Data Structures:
A data structure is a way of storing data in a computer so that it can be used efficiently and it will allow
the most efficient algorithm to be used. The choice of the data structure begins from the choice of an
abstract data type (ADT). A well-designed data structure allows a variety of critical operations to be
performed, using as few resources, both execution time and memory space, as possible. Data structure
introduction refers to a scheme for organizing data, or in other words it is an arrangement of data in
computer's memory in such a way that it could make the data quickly available to the processor for
required calculations.

A data structure should be seen as a logical concept that must address two fundamental concerns.

1. First, how the data will be stored, and

2. Second, what operations will be performed on it.
As data structure is a scheme for data organization so the functional definition of a data structure should
be independent of its implementation. The functional definition of a data structure is known as ADT
(Abstract Data Type) which is independent of implementation. The way in which the data is organized
affects the performance of a program for different tasks. Computer programmers decide which data
structures to use based on the nature of the data and the processes that need to be performed on that data.
Some of the more commonly used data structures include lists, arrays, stacks, queues, heaps, trees, and
graphs.

Classification of Data Structures:

Data structures can be classified as

Simple data structure

Compound data structure
Linear data structure
Non linear data structure

Simple Data Structure:

Simple data structure can be constructed with the help of primitive data structure. A primitive data structure
used to represent the standard data types of any one of the computer languages. Variables,arrays, pointers,
structures, unions, etc. are examples of primitive data structures.
Compound Data structure:
Compound data structure can be constructed with the help of any one of the primitive data structure and
it is having a specific functionality. It can be designed by user. It can be classified as

Linear data structure

Non-linear data structure
Linear Data Structure:
Linear data structures can be constructed as a continuous arrangement of data elements in the memory.
It can be constructed by using array data type. In the linear Data Structures the relationship of adjacency
is maintained between the data elements.

Operations applied on linear data structure:

The following list of operations applied on linear data structures

1. Add an element
2. Delete an element
3. Traverse
4. Sort the list of elements
5. Search for a data element
For example Stack, Queue, Tables, List, and Linked Lists.

Non-linear Data Structure:

Non-linear data structure can be constructed as a collection of randomly distributed set of data item joined
together by using a special pointer (tag). In non-linear Data structure the relationship of adjacency is not
maintained between the data items.

Operations applied on non-linear data structures:

The following list of operations applied on non-linear data structures.
1. Add elements
2. Delete elements
3. Display the elements
4. Sort the list of elements
5. Search for a data element
For example Tree, Decision tree, Graph and Forest

Abstract Data Type:

An abstract data type, sometimes abbreviated ADT, is a logical description of how we view the data and
the operations that are allowed without regard to how they will be implemented. This means thatwe
are concerned only with what data is representing and not with how it will eventually be constructed.By
providing this level of abstraction, we are creating an encapsulation around the data. The idea is that by
encapsulating the details of the implementation, we are hiding them from the user’s view. This is called
information hiding. The implementation of an abstract data type, often referred toas a data structure, will
require that we provide a physical view of the data using some collection of programmingconstructs and
primitive data types.

[Fig. 1.2: Abstract Data Type (ADT)]

Algorithms: Structure and Properties of Algorithm:

An algorithm has the following structure

1. Input Step

2. Assignment Step

3. Decision Step

4. Repetitive Step

5. Output Step

An algorithm is endowed with the following properties:

1. Finiteness: An algorithm must terminate after a finite number of steps.

2. Definiteness: The steps of the algorithm must be precisely defined or unambiguously specified.

3. Generality: An algorithm must be generic enough to solve all problems of a particular class.

4. Effectiveness: the operations of the algorithm must be basic enough to be put down on pencil and
paper. They should not be too complex to warrant writing another algorithm for the operation.

5. Input-Output: The algorithm must have certain initial and precise inputs, and outputs that may be
generated both at its intermediate and final steps.

Different Approaches to Design an Algorithm:

An algorithm does not enforce a language or mode for its expression but only demands adherence to
itsproperties.
Practical Algorithm Design Issues:

1. To save time (Time Complexity): A program that runs faster is a better program.

2. To save space (Space Complexity): A program that saves space over a competing program isconsiderable
desirable.
Efficiency of Algorithms:

The performances of algorithms can be measured on the scales of time and space. The performance of
a program is the amount of computer memory and time needed to run a program. We use two approaches
to determine the performance of a program. One is analytical and the other is experimental. In
performance analysis we use analytical methods, while in performance measurement we conduct
experiments.

Time Complexity: The time complexity of an algorithm or a program is a function of the running time
of the algorithm or a program. In other words, it is the amount of computer time it needs to run to
completion.

Space Complexity: The space complexity of an algorithm or program is a function of the space needed
by the algorithm or program to run to completion.

The time complexity of an algorithm can be computed either by an empirical or theoretical approach.
The empirical or posteriori testing approach calls for implementing the complete algorithms and
executing them on a computer for various instances of the problem. The time taken by the execution of
the programs for various instances of the problem are noted and compared. The algorithm whose
implementation yields the least time is considered as the best among the candidate algorithmic solutions.

Analyzing Algorithms
Suppose M is an algorithm, and suppose n is the size of the input data. Clearly the complexity f(n) of M
increases as n increases. It is usually the rate of increase of f(n) with some standard functions. The most
common computing times are

O(1), O(log2 n), O(n), O(n log2 n), O(n2), O(n3), O(2n)
Example:
The total frequency counts of the program segments A, B and C given by 1, (3n+1) and (3n 2+3n+1)
respectively are expressed as O(1), O(n) and O(n2). These are referred to as the time complexities of the
program segments since they are indicative of the running times of the program segments. In a similar
manner space complexities of a program can also be expressed in terms of mathematical notations, which
is nothing but the amount of memory they require for their execution.
Asymptotic Notations:
It is often used to describe how the size of the input data affects an algorithm’s usage of computational
resources. Running time of an algorithm is described as a function of input size n for large n.

Big oh(O): Definition: f(n) = O(g(n)) (read as f of n is big oh of g of n) if there exist a positive integer
n0 and a positive number c such that |f(n)| ≤ c|g(n)| for all n ≥ n 0 . Here g(n) is the upper bound of the
function f(n).

Omega(Ω): Definition: f(n) = Ω(g(n)) ( read as f of n is omega of g of n), if there exists a positive integer n0

and a positive number c such that |f(n)| ≥ c |g(n)| for all n ≥ n0. Here g(n) is the lower bound of the function
f(n).

Theta(Θ): Definition: f(n) = Θ(g(n)) (read as f of n is theta of g of n), if there exists a positive integer
n0 and two positive constants c1 and c2 such that c1 |g(n)| ≤ |f(n)| ≤ c2 |g(n)| for all n ≥ n0. The function g(n)
is both an upper bound and a lower bound for the function f(n) for all values of n, n ≥ n0 .
Little oh(o): Definition: f(n) = O(g(n)) ( read as f of n is little oh of g of n), if f(n) = O(g(n)) and f(n) ≠
Ω(g(n)).

Time Complexity:

Time Complexities of various Algorithms:

Numerical Comparision of Different Algorithms:

S.No. log2n n nlog2n n2 n3 2n

1. 0 1 1 1 1 2

2. 1 2 2 4 8 4

3. 2 4 8 16 64 16

4. 3 8 24 64 512 256

5. 4 16 64 256 4096 65536

Reasons for analyzing algorithms:

1. To predict the resources that the algorithm requires
 Computational Time(CPU consumption).

 Memory Space(RAM consumption).

 Communication bandwidth consumption.

2. To predict the running time of an algorithm

 Total number of primitive operations executed.

7
The data structure that reflects this relationship is termed as rooted tree graph or a tree.
Graph: In this case, data sometimes hold a relationship between the pairs of elements which is not
necessarily following the hierarchical structure. Such data structure is termed as a Graph.

Array is a container which can hold a fix number of items and these items should be of the same
type. Most of the data structures make use of arrays to implement their algorithms. Following are
the important terms to understand the concept of Array.
Element − Each item stored in an array is called an element.
Index − Each location of an element in an array has a numerical index, which is used to
identify the element.
ArrayRepresentation:(Storage structure)
Arrays can be declared in various ways in different languages. For illustration, let's take C array
declaration.

Arrays can be declared in various ways in different languages. For illustration, let's take C array
declaration.

As per the above illustration, following are the important points to be considered.
Index starts with 0.
Array length is 10 which means it can store 10 elements.
Each element can be accessed via its index. For example, we can fetch an element
at index 6 as 9.
BasicOperations
Following are the basic operations supported by an array.
Traverse − print all the array elements one by one.
Insertion − Adds an element at the given index.
Deletion − Deletes an element at the given index.
Search − Searches an element using the given index or by the value.
Update − Updates an element at the given index.
In C, when an array is initialized with size, then it assigns defaults values to its elements in
following order.
Insertion Operation
Insert operation is to insert one or more data elements into an array. Based on the requirement, a
new element can be added at the beginning, end, or any given index of array.
Here, we see a practical implementation of insertion operation, where we add data at the end of the
array −
Algorithm
Let LA be a Linear Array (unordered) with N elements and K is a positive integer such that
K<=N. Following is the algorithm where ITEM is inserted into the Kth position of LA
−
1. Start
2. Set J = N
3. Set N = N+1
4. Repeat steps 5 and 6 while J >= K
5. Set LA[J+1] = LA[J]
6. Set J = J-1
7. Set LA[K] = ITEM
8. Stop
Example
Following is the implementation of the above algorithm −

#include <stdio.h>

main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3,
n = 5;int i = 0, j = n;
printf("The original array elements are
:\n"); for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}n=n+
1; while(j
>= k) {
LA[j+1] = LA[j];
j = j - 1;
}
LA[k] = item;
printf("The array elements after insertion
:\n"); for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
When we compile and execute the above program, it produces the following result −
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after insertion :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 10
LA[4] = 7
LA[5] = 8
DeletionOperation
Deletion refers to removing an existing element from the array and re-organizing all elements
of an array.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that
K<=N. Following is the algorithm to delete an element available at the Kth position of LA.

1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
Example
Following is the implementation of the above algorithm −

#include <stdio.h>

void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}

j = k;
while( j < n) {
LA[j-1] = LA[j];
j = j + 1;
}
n = n -1;
printf("The array elements after deletion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
When we compile and execute the above program, it produces the following result −
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after deletion :
LA[0] = 1
LA[1] = 3
LA[2] = 7
LA[3] = 8
SearchOperation
You can perform a search for an array element based on its value or its index.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that K<=N.
Following is the algorithm to find an element with a value of ITEM using sequential search.

1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop
Example
Following is the implementation of the above algorithm −

#include <stdio.h>

void main() {
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
while( j < n){
if( LA[j] == item ) {
break;
}
j = j + 1;
}
printf("Found element %d at position %d\n", item, j+1);
}
When we compile and execute the above program, it produces the following result −
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3
UpdateOperation
Update operation refers to updating an existing element from the array at a given index.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that
K<=N. Following is the algorithm to update an element available at the Kth position of LA.

1. Start
2. Set LA[K-1] = ITEM
3. Stop
Example

Following is the implementation of the above algorithm −

#include <stdio.h>

void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5, item = 10;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}

LA[k-1] = item;
printf("The array elements after updation :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
When we compile and execute the above program, it produces the following result −
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8

Sparse Matrix and its representations

A matrix is a two-dimensional data object made of m rows and n columns, therefore having total
m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix.
Why to use Sparse Matrix instead of simple matrix ?
 Storage: There are lesser non-zero elements than zeros and thus lesser memory
can be used to store only those elements.
 Computing time: Computing time can be saved by logically designing a data
structure traversing only non-zero elements..
Example: 0
0304
00570
00000
02600
Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the matrix
are of no use in most of the cases. So, instead of storing zeroes with non- zero elements, we only
store non-zero elements. This means storing non-zero elements with triples- (Row, Column,
value).
Sparse Matrix Representations can be done in many ways following are two common representations:
1. Array representation
2. Linked list representation
Method 1: Using Arrays
#include<stdio.h>
int main()
{
// Assume 4x5 sparse matrix int
sparseMatrix[4][5] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};

int size = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
size++;
int compactMatrix[3][size];
// Making of new matrix
int k = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
{
compactMatrix[0][k] = i;
compactMatrix[1][k] = j;
compactMatrix[2][k] = sparseMatrix[i][j];
k++;
}
for (int i=0; i<3; i++)
{
for (int j=0; j<size; j++)
printf("%d ", compactMatrix[i][j]);
printf("\n");
}
return 0;
}
LINKEDLISTS
Linked lists and arrays are similar since they both store collections of data. Array is the most common
data structure used to store collections of elements. Arrays are convenient to declare and provide the easy
syntax to access any element by its index number. Once the array is set up, access to any element is
convenient and fast.
The disadvantages of arrays are:
• The size of the array is fixed. Most often this size is specified at compile time. This makes the
programmers to allocate arrays, which seems "large enough" than required.
• Inserting new elements at the front is potentially expensive because existing elements need to be
shifted over to make room.
• Deleting an element from an array is not possible. Linked lists have their own strengths and
weaknesses, but they happen to be strong where arrays are weak.
 Generally array's allocates the memory for all its elements in one block whereas linked lists usean
entirely different strategy. Linked lists allocate memory for each element separately and only when
necessary.
Linked List Concepts:
A linked list is a non-sequential collection of data items. It is a dynamic data structure. For every data item
in a linked list, there is an associated pointer that would give the memory location of the next data item in
the linked list. The data items in the linked list are not in consecutive memory locations. They may be
anywhere, but the accessing of these data items is easier as each data item contains the address of the next
data item.
Advantages of linked lists:
Linked lists have many advantages. Some of the very important advantages are:
1. Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution of a
program.
2. Linked lists have efficient memory utilization. Here, memory is not preallocated. Memory is
allocated whenever it is required and it is de-allocated (removed) when it is no longer needed.
3. Insertion and Deletions are easier and efficient. Linked lists provide flexibility in inserting a data
item at a specified position and deletion of the data item from the given position.
4. Many complex applications can be easily carried out with linked lists.

Disadvantages of linked lists:

1. It consumes more space because every node requires a additional pointer to store address of the
next node.
2. Searching a particular element in list is difficult and also time consuming.
Types of Linked Lists:
Basically we can put linked lists into the following four items:
1. Single Linked List.
2. Double Linked List.
3. Circular Linked List.
4. Circular Double Linked List.
A single linked list is one in which all nodes are linked together in some sequential manner. Hence, it is
also called as linear linked list.
A double linked list is one in which all nodes are linked together by multiple links which helps in accessing
8
both the successor node (next node) and predecessor node (previous node) from any arbitrary node within
the list. Therefore each node in a double linked list has two link fields (pointers) to point to the left node
(previous) and the right node (next). This helps to traverse in forward direction and backward direction.
A circular linked list is one, which has no beginning and no end. A single linked list can be made a circular
linked list by simply storing address of the very first node in the link field of the last node.
A circular double linked list is one, which has both the successor pointer and predecessor pointer in the
circular manner.

Applications of linked list:

1. Linked lists are used to represent and manipulate polynomial. Polynomials are expression containing
terms with non zero coefficient and exponents. For example: P(x) = a0 Xn + a1 Xn-1 + …… + an-1
X + an
2. Represent very large numbers and operations of the large number such as addition, multiplication and
division.
3. Linked lists are to implement stack, queue, trees and graphs. 4. Implement the symbol table in compiler
construction.
Single Linked List:
9
A linked list allocates space for each element separately in its own block of memory called a "node". The
list gets an overall structure by using pointers to connect all its nodes together like the links in a chain. Each
node contains two fields; a "data" field to store whatever element, and a "next" field which is a pointer used
to link to the next node. Each node is allocated in the heap using malloc(), so the node memory continues
to exist until it is explicitly de-allocated using free(). The front of the list is a pointer tothe “start” node.

A single linked list

The beginning of the linked list is stored in a "start" pointer which points to the first node. The first node
contains a pointer to the second node. The second node contains a pointer to the third node, ... and so on.
The last node in the list has its next field set to NULL to mark the end of the list. Code can access any node
in the list by starting at the start and following the next pointers.
The start pointer is an ordinary local pointer variable, so it is drawn separately on the left top to show that
it is in the stack. The list nodes are drawn on the right to show that they are allocated in the heap.
The basic operations in a single linked list are:
• Creation.
• Insertion.
• Deletion.
• Traversing.
Creating a node for Single Linked List:
Creating a singly linked list starts with creating a node. Sufficient memory has to be allocated for creating
a node. The information is stored in the memory.

10
Insertion of a Node:
One of the most primitive operations that can be done in a singly linked list is the insertion of a node.
Memory is to be allocated for the new node (in a similar way that is done while creating a list) before
reading the data. The new node will contain empty data field and empty next field. The data field of the
new node is then stored with the information read from the user. The next field of the new node is assigned
to NULL. The new node can then be inserted at three different places namely:
• Inserting a node at the beginning.
• Inserting a node at the end.
• Inserting a node at intermediate position.

 Inserting a node at the beginning.

 Inserting a node at the end:

 Inserting a node into the single linked list at a specified intermediate position other than
beginning and end.

11
Deletion of a node:
Another primitive operation that can be done in a singly linked list is the deletion of a node. Memory is
to be released for the node to be deleted. A node can be deleted from the list from three different places
namely.
• Deleting a node at the beginning.
• Deleting a node at the end.
• Deleting a node at intermediate position.
Deleting a node at the beginning:

Deleting a node at the end:

Deleting a node at Intermediate position:

The following steps are followed, to delete a node from an intermediate position in the list (List must
contain more than two node).

Traversal and displaying a list (Left to Right):

To display the information, you have to traverse (move) a linked list, node by node from the first node,
until the end of the list is reached.
Traversing a list involves the following steps:
• Assign the address of start pointer to a temp pointer.
• Display the information from the data field of each node. The function traverse () is used for traversing
and displaying the information stored in the list from left to right.
12
Using a header node:
A header node is a special dummy node found at the front of the list. The use of header node is an alternative
to remove the first node in a list. For example, the picture below shows how the list with data 10, 20 and 30
would be represented using a linked list without and with a header node:

Note that if your linked lists do include a header node, there is no need for the special case code given above
for the remove operation; node n can never be the first node in the list, so there is no need to check for that
case. Similarly, having a header node can simplify the code that adds a node before a given node n.
Note that if you do decide to use a header node, you must remember to initialize an empty list to contain
one (dummy) node, you must remember not to include the header node in the count of "real" nodes in the
list.
It is also useful when information other than that found in each node of the list is needed. For example,
imagine an application in which the number of items in a list is often calculated. In a standard linked list,
the list function to count the number of nodes has to traverse the entire list every time. However, if the
current length is maintained in a header node, that information can be obtained very quickly. 3.5. Array
based linked lists: Another alternative is to allocate the nodes in blocks. In fact, if you know the
maximum size of a list a head of time, you can pre-allocate the nodes in a single array. The result is a hybrid
structure – an array based linked list.
shows an example of null terminated single linked list where all the nodes are allocated contiguously in
an array.

13
Double Linked List: A double linked list is a two-way list in which all nodes will have two links. This
helps in accessing both successor node and predecessor node from the given node position. It provides bi-
directional traversing. Each node contains three fields:
 Left link.
 Data.
 Right link.
The left link points to the predecessor node and the right link points to the successor node. The data field
stores the required data.
Many applications require searching forward and backward thru nodes of a list. For example searching for
a name in a telephone directory would need forward and backward scanning thru a region of the wholelist.
The basic operations in a double linked list are:
 Creation.
 Insertion.
 Deletion.
 Traversing.
A double linked list is shown in figure

The beginning of the double linked list is stored in a "start" pointer which points to the first node. The
first node‟s left link and last node‟s right link is set to NULL.
Creating a node for Double Linked List:
Creating a double linked list starts with creating a node. Sufficient memory has to be allocated for
creating a node. The information is stored in the memory.
Double Linked List with 3 nodes:

Inserting a node at the beginning:

14
Inserting a node at the end:

Inserting a node at an intermediate position:

Deleting a node at the beginning:

15
Deleting a node at the end:

Deleting a node at Intermediate position:

Traversal and displaying a list (Left to Right):

To display the information, you have to traverse the list, node by node from the first node, until the end
of the list is reached. The function traverse_left_right() is used for traversing and displaying the information
stored in the list from left to right.
Traversal and displaying a list (Right to Left):
To display the information from right to left, you have to traverse the list, node by node from the first node,
until the end of the list is reached. The function traverse_right_left() is used for traversing and displaying
the information stored in the list from right to left.
Circular Single Linked List:
It is just a single linked list in which the link field of the last node points back to the address of the first
node. A circular linked list has no beginning and no end. It is necessary to establish a special pointer called
start pointer always pointing to the first node of the list. Circular linked lists are frequently used instead of
ordinary linked list because many operations are much easier to implement. In circular linked list no null
pointers are used, hence all pointers contain valid address.
Creating a circular single Linked List with „n‟ number of nodes:

The basic operations in a circular single linked list are:

• Creation.
• Insertion.

16
• Deletion.
• Traversing.
Inserting a node at the beginning:

Inserting a node at the end:

Deleting a node at the beginning:

Deleting a node at the end:

17
Circular Double Linked List:
A circular double linked list has both successor pointer and predecessor pointer in circular manner. The
objective behind considering circular double linked list is to simplify the insertion and deletion operations
performed on double linked list. In circular double linked list the right link of the right most node points
back to the start node and left link of the first node points to the last node.
A circular double linked list is shown in figure

Creating a Circular Double Linked List with „n‟ number of nodes

The basic operations in a circular double linked list are:
• Creation.
• Insertion.
• Deletion.
• Traversing.

Inserting a node at the beginning:

Inserting a node at the end:

18
Inserting a node at an intermediate position:

Deleting a node at the beginning:

Deleting a node at the end:

Deleting a node at Intermediate position:

19
Comparison of Linked List Variations:
The major disadvantage of doubly linked lists (over singly linked lists) is that they require more space
(every node has two pointer fields instead of one). Also, the code to manipulate doubly linked lists needs
to maintain the prev fields as well as the next fields; the more fields that have to be maintained, the more
chance there is for errors.
The major advantage of doubly linked lists is that they make some operations (like the removal of a given
node, or a right-to-left traversal of the list) more efficient.
The major advantage of circular lists (over non-circular lists) is that they eliminate some extra-case code
for some operations (like deleting last node). Also, some applications lead naturally to circular list
representations. For example, a computer network might best be modeled using a circular list.
Polynomials:
A polynomial is of the form: i n i ∑ ci
Where, ci is the coefficient of the ith term and
n is the degree of the polynomial
Some examples are:
5x2 + 3x + 1
12x3 – 4x
5x4 – 8x3 + 2x2 + 4x1 + 9x0
It is not necessary to write terms of the polynomials in decreasing order of degree. In other
words the two polynomials 1 + x and x + 1 are equivalent.

The computer implementation requires implementing polynomials as a list of pairs of coefficient and
exponent. Each of these pairs will constitute a structure, so a polynomial will be represented as a list of
structures.
A linked list structure that represents polynomials 5x4 – 8x3 + 2x2 + 4x1 + 9x0

20
Addition of Polynomials:
To add two polynomials we need to scan them once. If we find terms with the same exponent in the two
polynomials, then we add the coefficients; otherwise, we copy the term of larger exponent into the sum and
go on. When we reach at the end of one of the polynomial, then remaining part of the other is copied into
the sum.
To add two polynomials follow the following steps:
• Read two polynomials
• Add them.
• Display the resultant polynomial.

21
LINKED LIST
A linked list is a sequence of data structures, which are connected together via links. Linked List
is a sequence of links which contains items. Each link contains a connection to another link.
Linked list is the second most-used data structure after array. Following are the important terms
to understand the concept of Linked List.
Link − Each link of a linked list can store a data called an element.
Next − Each link of a linked list contains a link to the next link called Next.
LinkedList − A Linked List contains the connection link to the first link called First.
Linked ListRepresentation
Linked list can be visualized as a chain of nodes, where every node points to the next node.

As per the above illustration, following are the important points to be considered.
Linked List contains a link element called first.
Each link carries a data field(s) and a link field called next.
Each link is linked with its next link using its next link.
Last link carries a link as null to mark the end of the list.
TypesofLinked List
Following are the various types of linked list.
Simple Linked List − Item navigation is forward only.
Doubly Linked List − Items can be navigated forward and backward.
Circular Linked List − Last item contains link of the first element as next and the
first element has a link to the last element as previous.
BasicOperations
Following are the basic operations supported by a list.
Insertion − Adds an element at the beginning of the list.
Deletion − Deletes an element at the beginning of the list.
Display − Displays the complete list.
Search − Searches an element using the given key.
Delete − Deletes an element using the given key.
Insertion Operation
Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams
here. First, create a node using the same structure and find the location whereit has to be inserted.
Imagine that we are inserting a node B (NewNode), between A (LeftNode)
and C (RightNode). Then point B.next to C −
NewNode.next −> RightNode;
It should look like this −

Now, the next node at the left should point to the new node.
LeftNode.next −> NewNode;

This will put the new node in the middle of the two. The new list should look like this −

TargetNode.next −> NULL;

Similar steps should be taken if the node is being inserted at the beginning of the list.
While inserting it at the end, the second last node of the list should point to the new node and
the new node will point to NULL.

DeletionOperation
Deletion is also a more than one step process. We shall learn with pictorial representation. First,
locate the target node to be removed, by using searching algorithms.

LeftNode.next −> TargetNode.next;

The left (previous) node of the target node now should point to the next node of the target node −
This will remove the link that was pointing to the target node. Now, using the following code, we
will remove what the target node is pointing at.
We need to use the deleted node. We can keep that in memory otherwise we can simply
deallocate memory and wipe off the target node completely.

ReverseOperation
This operation is a thorough one. We need to make the last node to be pointed by the head node
and reverse the whole linked list.

First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point
to its previous node −

We have to make sure that the last node is not the lost node. So we'll have some temp node, which
looks like the head node pointing to the last node. Now, we shall make all left side nodes point to
their previous nodes one by one.

Except the node (first node) pointed by the head node, all nodes should point to their predecessor,
making them their new successor. The first node will point to NULL.

We'll make the head node point to the new first node by using the temp node.

The linked list is now reversed.

Program:
#include <stdio.h> #include
<string.h> #include <stdlib.h>
#include <stdbool.h>

struct node { int data; int

key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;

//display the list

void printList() {
struct node *ptr = head;
printf("\n[ ");

//start from the beginning

while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data); ptr
= ptr->next;
}

printf(" ]");
}

//insert link at the first location void

insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));

link->key = key;
link->data = data;

//point it to old first node

link->next = head;

//point first to new first node

head = link;
}

//delete first item

struct node* deleteFirst() {

//save reference to first link struct

node *tempLink = head;

//mark next to first link as first head

= head->next;

//return the deleted link

return tempLink;
}

//is list empty bool

isEmpty() {
return head == NULL;
}

int length() {
int length = 0;
struct node *current;

for(current = head; current != NULL; current = current->next) {

length++;
}

return length;
}

//find a link with given key struct

node* find(int key) {

//start from the first link struct

node* current = head;

//if list is empty if(head

== NULL) {
return NULL;
}

//navigate through list

while(current->key != key) {
//if it is last node
if(current->next == NULL) {
return NULL;
} else {
//go to next link
current = current->next;
}
}
//if data found, return the current Link return
current;
}

//delete a link with given key

struct node* delete(int key) {

//start from the first link struct

node* current = head;
struct node* previous = NULL;

//if list is empty if(head

== NULL) {
return NULL;
}

//navigate through list

while(current->key != key) {
//if it is last node
if(current->next == NULL) {
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link current
= current->next;
}
}

//found a match, update the link

if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link previous-
>next = current->next;
}

return current;
}
*head_ref = prev;
}

void main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("Original List: ");

//print list
printList();

while(!isEmpty()) {
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}

printf("\nList after deleting all items: ");

printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("\nRestored List: ");

printList();
printf("\n");

struct node *foundLink = find(4);

if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data); printf("\n");
void sort() {

int i, j, k, tempKey, tempData;

struct node *current;
struct node *next;

int size = length(); k

= size ;
for ( i = 0 ; i < size - 1 ; i++, k-- ) {
current = head;
next = head->next;

for ( j = 1 ; j < k ; j++ ) {

if ( current->data > next->data ) {

tempData = current->data;
current->data = next->data; next-
>data = tempData;

tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}

current = current->next;
next = next->next;
}
}
}

void reverse(struct node** head_ref) {

struct node* prev = NULL;
struct node* current = *head_ref; struct
node* next;

while (current != NULL) {

next = current->next;
current->next = prev;
prev = current;
current = next;
}
} else {
printf("Element not found.");
}

delete(4);
printf("List after deleting an item: ");
printList();
printf("\n");
foundLink = find(4);

if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}

printf("\n");
sort();

printf("List after sorting the data: ");

printList();

reverse(&head);
printf("\nList after reversing the data: ");
printList();
}
If we compile and run the above program, it will produce the following result −
Output
Original List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Deleted value:(6,56)
Deleted value:(5,40)
Deleted value:(4,1)
Deleted value:(3,30)
Deleted value:(2,20)
Deleted value:(1,10)
List after deleting all items:
[]
Restored List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Element found: (4,1)
List after deleting an item:
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
Element not found.
List after sorting the data:
[ (1,10) (2,20) (3,30) (5,40) (6,56) ]
List after reversing the data:
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]

Polynomial List
A polynomial p(x) is the expression in variable x which is in the form (axn + bxn-1 + …. + jx+ k),
where a, b, c …., k fall in the category of real numbers and 'n' is non negative integer, which
is called the degree of polynomial.
An important characteristics of polynomial is that each term in the polynomial expression
consists of two parts:
one is the coefficient
other is the exponent
Example:
10x2 + 26x, here 10 and 26 are coefficients and 2, 1 are its exponential value. Points to
keep in Mind while working with Polynomials:
The sign of each coefficient and exponent is stored within the coefficient and the
exponent itself
Additional terms having equal exponent is possible one
The storage allocation for each term in the polynomial must be done in
ascending and descending order of their exponent

Representation of Polynomial
Polynomial can be represented in the various ways. These are:
By the use of arrays
By the use of Linked List
Representation of Polynomials using Arrays
There may arise some situation where you need to evaluate many polynomial expressions and
perform basic arithmetic operations like: addition and subtraction with those numbers. For this you
will have to get a way to represent those polynomials. The simple way is to represent a polynomial
with degree 'n' and store the coefficient of n+1 terms of the polynomial in array. So every array
element will consists of two values:
Coefficient and
Exponent
Representation of Polynomial Using Linked Lists
A polynomial can be thought of as an ordered list of non zero terms. Each non zero term is a
two tuple which holds two pieces of information:

The exponent part

The coefficient part
Adding two polynomials using Linked List
Given two polynomial numbers represented by a linked list. Write a function that add these lists
means add the coefficients who have same variable powers.
Example:

Input:
1st number = 5x^2 + 4x^1 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^2 + 9x^1 + 7x^0
Input:
1st number = 5x^3 + 4x^2 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^3 + 4x^2 + 5x^1 + 7x^0
struct Node
{
int coeff;
int pow;
struct Node *next;
};

void create_node(int x, int y, struct Node **temp)

{
struct Node *r, *z;
z = *temp;
if(z == NULL)
{
r =(struct Node*)malloc(sizeof(struct Node));
r->coeff = x;
r->pow = y;
*temp = r;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
else
{
r->coeff = x;
r->pow = y;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
}
void polyadd(struct Node *poly1, struct Node *poly2, struct Node *poly)
{
while(poly1->next && poly2->next)
{
if(poly1->pow > poly2->pow)
{
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
poly1 = poly1->next;
}
else if(poly1->pow < poly2->pow)
{
poly->pow = poly2->pow;
poly->coeff = poly2->coeff;
poly2 = poly2->next;
}
else
{
poly->pow = poly1->pow;
poly->coeff = poly1->coeff+poly2->coeff;
poly1 = poly1->next;
poly2 = poly2->next;
}
poly->next = (struct Node *)malloc(sizeof(struct Node));
poly = poly->next;
poly->next = NULL;
}
while(poly1->next || poly2->next)
{
if(poly1->next)
{
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
poly1 = poly1->next;
}
if(poly2->next)
{
poly->pow = poly2->pow;
poly->coeff = poly2->coeff;
poly2 = poly2->next;
}
poly->next = (struct Node *)malloc(sizeof(struct Node));
poly = poly->next;
poly->next = NULL;
}
}
void show(struct Node *node)
{
while(node->next != NULL)
{
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if(node->next != NULL)
printf(" + ");
}
}
int main()
{
struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;
// Create first list of 5x^2 + 4x^1 + 2x^0
create_node(5,2,&poly1);
create_node(4,1,&poly1);
create_node(2,0,&poly1);
// Create second list of 5x^1 + 5x^0
create_node(5,1,&poly2);
create_node(5,0,&poly2);
printf("1st Number: ");
show(poly1);
printf("\n2nd Number: ");
show(poly2);
poly = (struct Node *)malloc(sizeof(struct Node));
// Function add two polynomial numbers
polyadd(poly1, poly2, poly);
// Display resultant List
printf("\nAdded polynomial: ");
show(poly);
return 0;
}
Output:

1st Number: 5x^2 + 4x^1 + 2x^0

2nd Number: 5x^1 + 5x^0
Added polynomial: 5x^2 + 9x^1 + 7x^0

Doubly Linked List

A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together
with next pointer and data which are there in singly linked list.

Following is representation of a DLL node in C language.

/* Node of a doubly linked list */
struct Node {
int data;
struct Node* next; // Pointer to next node in DLL struct
Node* prev; // Pointer to previous node in DLL
};
Following are advantages/disadvantages of doubly linked list over singly linked list.
Advantages over singly linked list
1) A DLL can be traversed in both forward and backward direction.
2) The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
3) We can quickly insert a new node before a given node.
In singly linked list, to delete a node, pointer to the previous node is needed. To get this
previous node, sometimes the list is traversed. In DLL, we can get the previous node using
previous pointer.
Disadvantages over singly linked list
1) Every node of DLL Require extra space for an previous pointer. It is possible to
implement DLL with single pointer though
2) All operations require an extra pointer previous to be maintained. For example, in insertion,
we need to modify previous pointers together with next pointers. For example in following
functions for insertions at different positions, we need 1 or 2 extra steps to set previous pointer.
Insertion
A node can be added in four ways
1) At the front of the DLL
2) After a given node.
3) At the end of the DLL
4) Before a given node.
1) Add a node at the front: (A 5 steps process)
The new node is always added before the head of the given Linked List. And newly added node
becomes the new head of DLL. For example if the given Linked List is 10152025 and we add an
item 5 at the front, then the Linked List becomes 510152025. Let us call the function that adds at
the front of the list is push(). The push() must receivea pointer to the head pointer, because push
must change the head pointer to point to thenew node

2) Add a node after a given node.: (A 7 steps process)

We are given pointer to a node as prev_node, and the new node is inserted after the given node.

3) Add a node at the end: (7 steps process)

The new node is always added after the last node of the given Linked List. For example if the given
DLL is 510152025 and we add an item 30 at the end, then the DLL becomes51015202530. Since
a Linked List is typically represented by the head of it, we have to traverse the list till end and then
change the next of last node to new node.

4) Add a node before a given node:

Steps
Let the pointer to this given node be next_node and the data of the new node to be addedas new_data.
1. Check if the next_node is NULL or not. If it’s NULL, return from the functionbecause any
new node can not be added before a NULL
2. Allocate memory for the new node, let it be called new_node
3. Set new_node->data = new_data
4. Set the previous pointer of this new_node as the previous node of the next_node,
new_node->prev = next_node->prev
5. Set the previous pointer of the next_node as the new_node, next_node->prev = new_node
6. Set the next pointer of this new_node as the next_node, new_node->next = next_node;
7. If the previous node of the new_node is not NULL, then set the next pointer of this
previous node as new_node, new_node->prev->next = new_node

Circular Linked List

Circular linked list is a linked list where all nodes are connected to form a circle. There isno NULL
at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

Advantages of Circular Linked Lists:

1) Any node can be a starting point. We can traverse the whole list by starting from any point. We
just need to stop when the first visited node is visited again.
2) Useful for implementation of queue. Unlike this implementation, we don’t need to maintain
two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last
inserted node and front can always be obtained as next of last.
3) Circular lists are useful in applications to repeatedly go around the list. For example, when
multiple applications are running on a PC, it is common for the operating system to put the running
applications on a list and then to cycle through them, giving each of them a slice of time to execute,
and then making them wait while the CPU is given to another application. It is convenient for the
operating system to use a circular list so thatwhen it reaches the end of the list it can cycle around
to the front of the list.
4) Circular Doubly Linked Lists are used for implementation of advanced data structures like
Fibonacci Heap.
After insertion,

Suppose 12 need to be insert after node having value 10,

After searching and insertion,

Memory Allocation-
Whenever a new node is created, memory is allocated by the system. This memory is taken from
list of those memory locations which are free i.e. not allocated. This list is called AVAIL List.
Similarly, whenever a node is deleted, the deleted space becomes reusable and is added to the list
of unused space i.e. to AVAIL List. This unused space can be used in future for memory allocation.
Memory allocation is of two types-
1. Static Memory Allocation
2. Dynamic Memory Allocation

1. Static Memory Allocation:

When memory is allocated during compilation time, it is called ‘Static Memory Allocation’.
This memory is fixed and cannot be increased or decreased after allocation. If more memory is
allocated than requirement, then memory is wasted. If less memory is allocated than
requirement, then program will not run successfully. Soexact memory requirements must be
known in advance.
2. Dynamic Memory Allocation:
When memory is allocated during run/execution time, it is called ‘Dynamic Memory
Allocation’. This memory is not fixed and is allocated according to our requirements. Thus in
it there is no wastage of memory. So there is no need to know exact memory requirements in
advance.
Garbage Collection-
Whenever a node is deleted, some memory space becomes reusable. This memory space should be
available for future use. One way to do this is to immediately insert the free space into availability
list. But this method may be time consuming for the operating system. So another method is used
which is called ‘Garbage Collection’. This method is described below: In this method the OS
collects the deleted space time to time onto the availability list. This process happens in two steps.
In first step, the OS goes through all the lists and tags all those cells which are currently being used.
In the second step, the OS goes through all the lists again and collects untagged space and adds this
collected space to availability list. The garbage collection may occur when small amount of free
space is left in the system or no free space is left in the system or when CPU is idle and has time to
do the garbage collection.
Compaction
One preferable solution to garbage collection is compaction. The process of
moving all marked nodes to one end of memory and all available memory to other end is called
compaction. Algorithm which performs compaction is called compacting algorithm.