Datastructures Notes

Datastructures Notes

1. DATASTRUCTURE
SUBJECT CODE - 10CT22

PROGRAMME II YEAR BSc COMPUTER SCIENCE
BATCH 2021 – 2024 BATCH
SEMESTER SECOND


Sri. C. RANJITHKUMAR,
Assistant Professor,
Department of Computer Science,
Vivekananda College, Madurai

2. 1

FUNDAMENTAL OF DATA STRUCTURES
INTRODUCTION
A data structure is a specialized format of data for arranging and storing data so that any user can easily
access and worked within an appropriate data to run a program efficiently. Computer memory data can
be organized logically or mathematically, and this process is known as a data structure. In general,
selecting a particular format of data depends on two factors. The data must be rich enough to satisfy the
real relationships of the data in the real world. And on the other hand, the data structure should be so
simple that one can easily process the data when it needs to be used.
Data Structure can be defined as the group of data elements which provides an efficient way of storing
and organizing data in the computer so that it can be used efficiently. Some examples of Data Structures
are arrays, Linked List, Stack, Queue, etc. Data Structures are widely used in almost every aspect of
Computer Science i.e. operating system, compiler design, artificial intelligence, graphics and many more.
Data Structures are the main part of many computer science algorithms as they enable the programmers
to handle the data in an efficient way. It plays a vital role in enhancing the performance of a software or
a program as the main function of the software is to store and retrieve the user's data as fast as possible.
BASIC TERMINOLOGY
Data structures are the building blocks of any program or the software. Choosing the appropriate data
structure for a program is the most difficult task for a programmer. Following terminology is used as far
as data structures are concerned.
Data:
Data can be defined as an elementary value or the collection of values, for example, student's name and
its id are the data about the student.
Group Items:
Data items which have subordinate data items are called Group item, for example, name of a student can
have first name and the last name.
Record:
Record can be defined as the collection of various data items, for example, if we talk about the student
entity, then its name, address, course and marks can be grouped together to form the record for the
student.
File:
A File is a collection of various records of one type of entity, for example, if there are 60 employees in the
class, then there will be 20 records in the related file where each record contains the data about each
employee.

3. 2

Attribute and Entity:
An entity represents the class of certain objects. it contains various attributes. Each attribute represents
the particular property of that entity.
Field:
Field is a single elementary unit of information representing the attribute of an entity.
CHARACTERISTICS OF DATA STRUCTURES
Following are the characteristics of the data structures as follows:
 Linear: A linear describes data characteristics whether the data items are arranged in sequential
form like an array.
 Non-Linear: A Non-Linear data structure describes the characteristics of data items that are not
in sequential form like a tree, graph.
 Static: It is a static data structure that describes the size and structures of a collection of data
items associated with a memory location at compile time that are fixed. Example - Array.
 Homogenous: It is a characteristic of data structures representing whether the data type of all
elements is the same. Example- Array.
 Non-Homogenous: It is a characteristic of data structures representing whether the data type
elements may or may not be the same.
 Dynamic: It is a dynamic data structure that defines the shrinking and expanding of data items at
the run time or the program's execution. It is also related to the utilization of memory location
that can be changed at the program's run time. Example: Linked list.
It has some rules that define how the data items are related to each other.
It defines some rules to display the relationship between data items and how they interact with
each other.
It has some operations used to perform on data items like insertion, searching, deletion, etc.
It helps in reducing the usage of memory resources.
 Time Complexity: The execution time of a program in a data structure should be minimum as
possible.
 Space Complexity: The memory usage through all data items in a data structure should be less
possible.

OPERATIONS ON DATA STRUCTURE:

1) Traversing: Every data structure contains the set of data elements. Traversing the data structure
means visiting each element of the data structure in order to perform some specific operation like
searching or sorting.
Example: If we need to calculate the average of the marks obtained by a student in 6 different subject,
we need to traverse the complete array of marks and calculate the total sum, then we will divide that
sum by the number of subjects i.e. 6, in order to find the average.

2) Insertion: Insertion can be defined as the process of adding the elements to the data structure at
any location.
If the size of data structure is n then we can only insert n-1 data elements into it.

4. 3


3) Deletion: The process of removing an element from the data structure is called Deletion. We can
delete an element from the data structure at any random location.
If we try to delete an element from an empty data structure then underflow occurs.

4) Searching: The process of finding the location of an element within the data structure is called
Searching. There are two algorithms to perform searching, Linear Search and Binary Search.

5) Sorting: The process of arranging the data structure in a specific order is known as Sorting. There
are many algorithms that can be used to perform sorting, for example, insertion sort, selection sort,
bubble sort, etc.

6) Merging: When two lists List A and List B of size M and N respectively, of similar type of elements,
clubbed or joined to produce the third list, List C of size (M+N), then this process is called merging

Merging: The Merge operation is used to join two or more sorted data elements to a data structure.

NEEDS OF THE DATA STRUCTURES:
Data is a basic fact or entity information that is used to calculate or manipulate. Two types of data are
used in a data structure, such as numerical data and alphanumeric data. These data structures specify the
nature of the data item undergoing some function. Integers and floating points are types of numeric data
types. The data can be single or a set of values that are organized in a particular fashion. The data
organization leads to memory that creates a logical relationship between data items and makes it
necessary to use data structures.

ADVANTAGES OF DATA STRUCTURES

There are some advantages of data structure:
1. Efficiency: The efficiency and organization of a program depend on the selection of the right data
structures. Suppose we want to search for a particular item from a collection of data records. In
that case, our data should be organized in linear like an array that helps to perform the sequential
search, such as element by element. However, it is efficient but more time consuming because
we need to arrange all elements and then search each element. Hence, we choose a better option
in a data structure, making the search process more efficient, like a binary search tree, selection
or hash tables.
2. Reusability: In the data structure, many operations make the programs reusable. For example,
when we write programs or implement a particular data structure, we can use it from any source
location or place to get the same results.
3. Abstraction: The data structure is maintained by the ADT, which provides different levels of
abstraction. The client can interact with data structures only through the interface.
The data structure helps to simplify the process of collection of data through the software
systems.
It is used to save collection data storage on a computer that can be used by various programs.
4. Processor speed:

5. 4

To handle very large amount of data, high speed processing is required, but as the data is growing
day by day to the billions of files per entity, processor may fail to deal with that much amount of
data.
5. Data Search:
Consider an inventory size of 106 items in a store, If our application needs to search for a particular
item, it needs to traverse 106 items every time, results in slowing down the search process.
6. Multiple requests:
If thousands of users are searching the data simultaneously on a web server, then there are the
chances that a very large server can be failed during that process
7. in order to solve the above problems, data structures are used. Data is organized to form a data
structure in such a way that all items are not required to be searched and required data can be
searched instantly.

DISADVANTAGES OF DATA STRUCTURES

1. A user who has deep knowledge about the functionality of the data structure can make changes
to it.
2. If there is an error in the data structure, an expert can detect the bug; The original user cannot
help themselves solve the problem and fix it.

Data Structure Classification:

6. 5

LINEAR DATA STRUCTURES:
A data structure is called linear if all of its elements are arranged in the linear order. In linear data
structures, the elements are stored in non-hierarchical way where each element has the successors and
predecessors except the first and last element.
Types of Linear Data Structures are given below:

Arrays: An array is a collection of similar type of data items and each data item is called an element of the
array. The data type of the element may be any valid data type like char, int, float or double.
The elements of array share the same variable name but each one carries a different index number known
as subscript. The array can be one dimensional, two dimensional or multidimensional.
The individual elements of the array age are:
age[0], age[1], age[2], age[3],......... age[98], age[99].

Linked List: Linked list is a linear data structure which is used to maintain a list in the memory. It can be
seen as the collection of nodes stored at non-contiguous memory locations. Each node of the list contains
a pointer to its adjacent node.

Stack: Stack is a linear list in which insertion and deletions are allowed only at one end, called top.
A stack is an abstract data type (ADT), can be implemented in most of the programming languages. It is
named as stack because it behaves like a real-world stack, for example: - piles of plates or deck of cards
etc.

Queue: Queue is a linear list in which elements can be inserted only at one end called rear and deleted
only at the other end called front.
It is an abstract data structure, similar to stack. Queue is opened at both end therefore it follows First-In-
First-Out (FIFO) methodology for storing the data items.

NON LINEAR DATA STRUCTURES:
This data structure does not form a sequence i.e. each item or element is connected with two or more
other items in a non-linear arrangement. The data elements are not arranged in sequential structure.
Types of Non Linear Data Structures are given below:

Trees: Trees are multilevel data structures with a hierarchical relationship among its elements known as
nodes. The bottommost nodes in the herierchy are called leaf node while the topmost node is called root
node. Each node contains pointers to point adjacent nodes.
Tree data structure is based on the parent-child relationship among the nodes. Each node in the tree can
have more than one children except the leaf nodes whereas each node can have atmost one parent except
the root node. Trees can be classfied into many categories which will be discussed later in this tutorial.

Graphs: Graphs can be defined as the pictorial representation of the set of elements (represented by
vertices) connected by the links known as edges. A graph is different from tree in the sense that a graph
can have cycle while the tree can not have the one.

7. 6

LINEAR ARRAY
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.
Array Representation
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.
BASIC OPERATIONS:
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.

8. 7

 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.
Data Type Default Value
bool false
char 0
int 0
float 0.0
double 0.0f
void
wchar_t 0
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 Array be a linear unordered array of MAX elements.
Example
Result
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 K
th
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

9. 8

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

10. 9

LA[2] = 5
LA[3] = 10
LA[4] = 7
LA[5] = 8

Deletion Operation:
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 K
th
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;

11. 10

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
Search Operation:
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

12. 11

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
Update Operation:
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 K
th
position of LA.

13. 12

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

14. 13

BINARY SEARCH:
Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm
works on the principle of divide and conquer. For this algorithm to work properly, the data collection
should be in the sorted form.
Binary search looks for a particular item by comparing the middle most item of the collection. If a match
occurs, then the index of item is returned. If the middle item is greater than the item, then the item is
searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-
array to the right of the middle item. This process continues on the sub-array as well until the size of the
sub-array reduces to zero.
How Binary Search Works?
For a binary search to work, it is mandatory for the target array to be sorted. We shall learn the process
of binary search with a pictorial example. The following is our sorted array and let us assume that we
need to search the location of value 31 using binary search.

First, we shall determine half of the array by using this formula −
mid = low + (high - low) / 2
Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Now we compare the value stored at location 4, with the value being searched, i.e. 31. We find that the
value at location 4 is 27, which is not a match. As the value is greater than 27 and we have a sorted
array, so we also know that the target value must be in the upper portion of the array.

We change our low to mid + 1 and find the new mid value again.
low = mid + 1
mid = low + (high - low) / 2

15. 14

Our new mid is 7 now. We compare the value stored at location 7 with our target value 31.

The value stored at location 7 is not a match, rather it is more than what we are looking for. So, the
value must be in the lower part from this location.

Hence, we calculate the mid again. This time it is 5.

We compare the value stored at location 5 with our target value. We find that it is a match.

We conclude that the target value 31 is stored at location 5.
Binary search halves the searchable items and thus reduces the count of comparisons to be made to
very less numbers.
Pseudocode:
The pseudocode of binary search algorithms should look like this −
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched

Set lowerBound = 1
Set upperBound = n

16. 15

while x not found
if upperBound < lowerBound
EXIT: x does not exists.

set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

if A[midPoint] < x
set lowerBound = midPoint + 1

if A[midPoint] > x
set upperBound = midPoint - 1

if A[midPoint] = x
EXIT: x found at location midPoint
end while

end procedure

SORTING
Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to
arrange data in a particular order. Most common orders are in numerical or lexicographical
order.
The importance of sorting lies in the fact that data searching can be optimized to a very high
level, if data is stored in a sorted manner. Sorting is also used to represent data in more readable
formats. Following are some of the examples of sorting in real-life scenarios −
 Telephone Directory − The telephone directory stores the telephone numbers of people sorted by
their names, so that the names can be searched easily.
 Dictionary − The dictionary stores words in an alphabetical order so that searching of any word
becomes easy.

In-place Sorting and Not-in-place Sorting:
Sorting algorithms may require some extra space for comparison and temporary storage of few
data elements. These algorithms do not require any extra space and sorting is said to happen
in-place, or for example, within the array itself. This is called in-place sorting. Bubble sort is an
example of in-place sorting.
However, in some sorting algorithms, the program requires space which is more than or equal
to the elements being sorted. Sorting which uses equal or more space is called not-in-place
sorting. Merge-sort is an example of not-in-place sorting.

17. 16

Stable and Not Stable Sorting:
If a sorting algorithm, after sorting the contents, does not change the sequence of similar
content in which they appear, it is called stable sorting.

If a sorting algorithm, after sorting the contents, changes the sequence of similar content in
which they appear, it is called unstable sorting.

Stability of an algorithm matters when we wish to maintain the sequence of original elements,
like in a tuple for example.

Adaptive and Non-Adaptive Sorting Algorithm
A sorting algorithm is said to be adaptive, if it takes advantage of already 'sorted' elements in
the list that is to be sorted. That is, while sorting if the source list has some element already
sorted, adaptive algorithms will take this into account and will try not to re-order them.
A non-adaptive algorithm is one which does not take into account the elements which are
already sorted. They try to force every single element to be re-ordered to confirm their
sortedness.

18. 17

Important Terms:
Some terms are generally coined while discussing sorting techniques, here is a brief introduction
to them −
Increasing Order
A sequence of values is said to be in increasing order, if the successive element is greater than
the previous one. For example, 1, 3, 4, 6, 8, 9 are in increasing order, as every next element is
greater than the previous element.
Decreasing Order
A sequence of values is said to be in decreasing order, if the successive element is less than the
current one. For example, 9, 8, 6, 4, 3, 1 are in decreasing order, as every next element is less
than the previous element.
Non-Increasing Order
A sequence of values is said to be in non-increasing order, if the successive element is less than
or equal to its previous element in the sequence. This order occurs when the sequence contains
duplicate values. For example, 9, 8, 6, 3, 3, 1 are in non-increasing order, as every next element
is less than or equal to (in case of 3) but not greater than any previous element.
Non-Decreasing Order
A sequence of values is said to be in non-decreasing order, if the successive element is greater
than or equal to its previous element in the sequence. This order occurs when the sequence
contains duplicate values. For example, 1, 3, 3, 6, 8, 9 are in non-decreasing order, as every next
element is greater than or equal to (in case of 3) but not less than the previous one.
----------------------
STACK
1. Stack is an ordered list in which, insertion and deletion can be performed only at one end that is
called top.
2. Stack is a recursive data structure having pointer to its top element.
3. Stacks are sometimes called as Last-In-First-Out (LIFO) lists i.e. the element which is inserted
first in the stack, will be deleted last from the stack.

Applications of Stack
1. Recursion
2. Expression evaluations and conversions
3. Parsing
4. Browsers
5. Editors
6. Tree Traversals

19. 18


OPERATIONS ON STACK:
There are various operations which can be performed on stack.


1. Push : Adding an element onto the stack



2. Pop : Removing an element from the stack



3. Peek : Look all the elements of stack without removing them.

20. 19

How the stack grows?
Scenario 1: Stack is empty
The stack is called empty if it doesn't contain any element inside it. At this stage, the value of variable
top is -1.


Scenario 2: Stack is not empty
Value of top will get increased by 1 every time when we add any element to the stack. In the following
stack, After adding first element, top = 2.


Scenario 3: Deletion of an element
Value of top will get decreased by 1 whenever an element is deleted from the stack.
In the following stack, after deleting 10 from the stack, top = 1.

21. 20

Top and its value :
Top position Status of stack
-1 Empty
0 Only one element in the stack
N-1 Stack is full
N Overflow

ARRAY IMPLEMENTATION OF STACK:
In array implementation, the stack is formed by using the array. All the operations regarding the stack
are performed using arrays. Lets see how each operation can be implemented on the stack using array
data structure.
Adding An Element Onto The Stack (Push Operation):
Adding an element into the top of the stack is referred to as push operation. Push operation involves
following two steps.
1. Increment the variable Top so that it can now refere to the next memory location.
2. Add element at the position of incremented top. This is referred to as adding new element at
the top of the stack.
Stack is overflown when we try to insert an element into a completely filled stack therefore, our main
function must always avoid stack overflow condition.
Algorithm:
1. begin
2. if top = n then stack full
3. top = top + 1
4. stack (top) : = item;
5. end
Time Complexity: o(1)
Implementation of push algorithm in C language
1. void push (int val,int n) //n is size of the stack
2. {
3. if (top == n )
4. printf("\n Overflow");
5. else
6. {
7. top = top +1;

22. 21

8. stack[top] = val;
9. }
10. }

Deletion Of An Element From A Stack (Pop Operation):
Deletion of an element from the top of the stack is called pop operation. The value of the variable top
will be incremented by 1 whenever an item is deleted from the stack. The top most element of the stack
is stored in an another variable and then the top is decremented by 1. the operation returns the deleted
value that was stored in another variable as the result.
The underflow condition occurs when we try to delete an element from an already empty stack.
Algorithm :
1. begin
2. if top = 0 then stack empty;
3. item := stack(top);
4. top = top - 1;
5. end;
Time Complexity : o(1)
Implementation of POP algorithm using C language
1. int pop ()
2. {
3. if(top == -1)
4. {
5. printf("Underflow");
6. return 0;
7. }
8. else
9. {
10. return stack[top - - ];
11. }
12. }

Visiting Each Element Of The Stack (Peek Operation):
Peek operation involves returning the element which is present at the top of the stack without deleting
it. Underflow condition can occur if we try to return the top element in an already empty stack.
Algorithm :
PEEK (STACK, TOP)
1. Begin
2. if top = -1 then stack empty
3. item = stack[top]

23. 22

4. return item
5. End
Time complexity: o(n)
Implementation of Peek algorithm in C language
1. int peek()
2. {
3. if (top == -1)
4. {
5. printf("Underflow");
6. return 0;
7. }
8. else
9. {
10. return stack [top];
11. }
12. }
LINKED LIST IMPLEMENTATION OF STACK:
Instead of using array, we can also use linked list to implement stack. Linked list allocates the memory
dynamically. However, time complexity in both the scenario is same for all the operations i.e. push, pop
and peek.
In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each
node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the
space left in the memory heap is not enough to create a node.

The top most node in the stack always contains null in its address field. Lets discuss the way
in which, each operation is performed in linked list implementation of stack.
Adding A Node To The Stack (Push Operation):
Adding a node to the stack is referred to as push operation. Pushing an element to a stack
in linked list implementation is different from that of an array implementation. In order to
push an element onto the stack, the following steps are involved.

24. 23

1. Create a node first and allocate memory to it.
2. If the list is empty then the item is to be pushed as the start node of the list. This
includes assigning value to the data part of the node and assign null to the address
part of the node.
3. If there are some nodes in the list already, then we have to add the new element in
the beginning of the list (to not violate the property of the stack). For this purpose,
assign the address of the starting element to the address field of the new node and
make the new node, the starting node of the list.
Time Complexity : o(1)



C implementation :
1. void push ()
2. {
3. int val;
4. struct node *ptr =(struct node*)malloc(sizeof(struct node));

25. 24

5. if(ptr == NULL)
6. {
7. printf("not able to push the element");
8. }
9. else
10. {
11. printf("Enter the value");
12. scanf("%d",&val);
13. if(head==NULL)
14. {
15. ptr->val = val;
16. ptr -> next = NULL;
17. head=ptr;
18. }
19. else
20. {
21. ptr->val = val;
22. ptr->next = head;
23. head=ptr;

24. }
25. printf("Item pushed");

26. }
27. }

Deleting A Node From The Stack (POP Operation):
Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the linked
list implementation of stack is different from that in the array implementation. In order to pop an
element from the stack, we need to follow the following steps :
1) Check for the underflow condition: The underflow condition occurs when we try to pop from an
already empty stack. The stack will be empty if the head pointer of the list points to null.
2) Adjust the head pointer accordingly: In stack, the elements are popped only from one end,
therefore, the value stored in the head pointer must be deleted and the node must be freed.
The next node of the head node now becomes the head node.
Time Complexity : o(n)
C implementation
1. void pop()
2. {
3. int item;
4. struct node *ptr;
5. if (head == NULL)
6. {

26. 25

7. printf("Underflow");
8. }
9. else
10. {
11. item = head->val;
12. ptr = head;
13. head = head->next;
14. free(ptr);
15. printf("Item popped");

16. }
17. }

Display The Nodes (Traversing):
Displaying all the nodes of a stack needs traversing all the nodes of the linked list organized in the form
of stack. For this purpose, we need to follow the following steps.
 Copy the head pointer into a temporary pointer.
 Move the temporary pointer through all the nodes of the list and print the value field attached
to every node.
Time Complexity : o(n)
C Implementation
1. void display()
2. {
3. int i;
4. struct node *ptr;
5. ptr=head;
6. if(ptr == NULL)
7. {
8. printf("Stack is empty\n");
9. }
10. else
11. {
12. printf("Printing Stack elements \n");
13. while(ptr!=NULL)
14. {
15. printf("%d\n",ptr->val);
16. ptr = ptr->next;
17. }
18. }
19. }

27. 26

Queue
1. A queue can be defined as an ordered list which enables insert operations to be performed at one end
called REAR and delete operations to be performed at another end called FRONT.
2. Queue is referred to be as First In First Out list.
3. For example, people waiting in line for a rail ticket form a queue,

Applications of Queue
Due to the fact that queue performs actions on first in first out basis which is quite fair for the ordering
of actions. There are various applications of queues discussed as below.
1. Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
2. Queues are used in asynchronous transfer of data (where data is not being transferred at the
same rate between two processes) for eg. pipes, file IO, sockets.
3. Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.
4. Queue are used to maintain the play list in media players in order to add and remove the songs
from the play-list.
5. Queues are used in operating systems for handling interrupts

Complexity
Data
Structure
Time Complexity Space
Complexity

Average Worst Worst
Access Search Insertion Deletion Access Search Insertion Deletion

Queue θ(n) θ(n) θ(1) θ(1) O(n) O(n) O(1) O(1) O(n)

28. 27

Give any two uses of a data structure?
List the attributes of a Linear Array?
Give any two examples for Non Linear Non primitive data structure?
Define a Stack?
Give the formula to find the mid value of an array in binary search?
Give the use of Pop( ) in a stack?
List the types of sorting algorithms?
Brief a note on data structure organization?
Summarize the representation of Linear Arrays in memory?
Critically analyze given below table with values and fill in the values where question marks given?
FIELD VALUES
Size of the stack 6
Maximum Value of the Stack Top 5
Minimum Value of Stack Top ?
Value of Top whcn Stack is Empty ?
Value of Top when the stack is Full ?

Summarize the representation of Stack in memory?
Discuss about Polish notations?
Compare and analyze the insertion and deletion operations of Linear Arrays with a suitable
algorithms and a program in C for each operation?
Explain the bubble sort and write a program in C to implement bubble sort?