1.Data Structure: Data structure is the 4.

The ADT is a useful guideline to

way of organizing and storing data in a implementers and a useful tool to
computer system so that it can be used programmers who wish to use the data
efficiently. Advantages of Data type correctly. 5.Implementation
Structures:1.Data structure allows details hiding.
easier processing of data. 2.It allows
7. TYPES OF DATA STRUCTURES:
information stored on disk very
1. Linear Data Structure: A data
efficiently. 3.Data structures are
structure is said to be linear if its
necessary for designing an efficient
elements form a sequence or a linear
algorithm. 4.Data structure is a secure
list. In this type of data structures,
way of storage of data. 5.Data
elements are accessed in sequential
structures allows processing of data on
order but it is not compulsory to store
software system. Applications:
all elements sequentially. 2.Non-Linear
1.Process Scheduling, 2.Simulation,
Data Structure: A data structure is said
3.Compiler Design, 4.Games.
to be non-linear if its elements form a
2. Data is defined as, raw facts and hierarchical classification where, data
figures before they have been items appear at various levels. In non-
processed. linear data structures, every data
element may have more than one
3.Data Types: A data type is a
predecessor as well as successor.
collection of values along with a set of
operations defined on those values. 8. Difference between Linear and
Non-linear Data Structures:
4. User-Defined Data Types: Those
*Linear Data Structures: A data
data types which are defined by the
structure is said to be linear if its
user as per his/her requirements are
elements form a sequence or a linear
called as user-defined data types.
list. 2.In linear data structures, data
5. Data Object: A data object is elements are organized sequentially.
characterized by a set of attributes. 3.They are easy to implement in the
One of the most important of which is computer’s memory. 4.Linear data
the data type. structures are organized in a way
similar to how the computer’s memory
6. Abstract Data Type (ADT): “a
is organized. 5.Eg: Array, Linked List,
mathematical model of the data
Stack and Queue.
objects that make up a data type as
Non-linear Data Structures: 1.A data
well as the functions that operates on
structure is said to be non-linear if its
these objects”. Advantages of ADT:
every data item is attached to several
1.ADT is reusable and ensures robust
other data items in a way of reflecting
data structure. 2.Encapsulation
relationships. 2.In non-linear data
ensures that data cannot be corrupted.
structures, a data element are not
3.It reduces coding efforts.
organized sequentially. running time. It is measure of the
3.They are difficult to implement in the average amount of time required for
computer’s memory as compared to the algorithm to complete.
implementing linear data structures.
12. Array: An array is a finite ordered
4.Non-linear data structures are
collection of homogeneous data
organized in a different way than the
elements which provides random
computer’s memory.5.Eg: Tree, Graph.
access to the elements. Advantages of
9.Space Complexity: can be defined Arrays: 1.Arrays helps to arrange the
as, “total amount of computer memory data (sorting) items in particular order
required by an algorithm to complete (ascending/descending). 2.Data items
its execution is called as space searching is faster using arrays.
complexity of that algorithm ”. 3.Arrays saves the memory space.
4.Arrays permit efficient random
10. Time Complexity: can be defined
access in constant time O(1).
as, “the total amount of time required
5. Ordered lists such as polynomials
by an algorithm to complete its
are most efficiently handled using
execution."
arrays. Applications of Arrays: 1.Array
11. Asymptotic Notations: Asymptotic can be used for Sorting Elements.
notation of an algorithm is a 2.Array can be used in CPU Scheduling.
mathematical representation of its 3.Array can be used in Recursive
complexity. Asymptotic notations Function. 4.Array can perform Matrix
represent the efficiency and Operation.
performance of an algorithm in a
13. Types of Arrays:
systematic and meaningful manner.
1.Single Dimensional Array/One
1.Big-Oh Notation (O): Big-Oh notation
Dimensional Array: The simplex form
is used to define the upper bound of
of an array is one-dimensional array.
an algorithm in terms of Time
One-dimensional array or linear array
Complexity. Big-Oh notation always
requires only one index to access an
indicates the maximum time required
element. The general form/syntax of
by an algorithm for all input values.
declaration of 1D Arrays is given below:
2.Big-Omega Notation (Ω): Big -
data_type variable_name[size]; .
Omega notation is used to define the
2.Two Dimensional Array: An array
lower bound of an algorithm in terms
with two subscripts is known as two
of Time Complexity. That means Big -
dimensional array. Two dimensional
Omega notation always indicates the
arrays also known as double dimension
minimum time required by an
arrays. data_type array_name
algorithm for all input values.
[row_size] [col_size]; .
3.Big-Theta Notation (θ): Big θ is the
3.Multi-dimensional Array: An array of
formal method of expressing the
arrays is called as multi-dimensional
average bound of an algorithm’s
array. In simple words, an array created 20. Difference between Linear and
with more than one dimension (size) is Binary Search:
called as multi-dimensional array. Linear Search: 1.Sequential approach.
2.Sorted and unsorted list of elements.
14. Operations on Arrays: 1.Insertion,
3.Search time is O(n). 4.Speed It
2.Deletion, 3.Searching, 4.Sorting,
slower than binary search. 5.Searching
6.Traversal.
in small list.
15. SEARCHING: Searching is a Binary Search: 1.Divide and conquer
technique of finding an element from approach. 2.Works only on sorted list
the given data list or set of the of elements. 3.Search time is O(log n).
elements like an array, list, or trees. It 4.Binary search is quicker/faster than
is a technique to find out an element in linear search. 5.Searching in large list.
a sorted or unsorted list.
21. SORTING: Sorting refers to the
16. Linear Search or Sequential process of the process of arranging a
Search: Linear search, also called as list of elements in a particular order.
orderly search or sequential search, 1.Internal Sorting: If all the data that
because every key element is searched is to be sorted can be accommodated
from first element in an array i.e., a[0] at a time in memory is called internal
to last element in an array i.e a[n-1]. sorting. 2.External Sorting: External
Advantages: 1.The linear search is sorting large amount of data requires
simple: It is very easy to understand external or secondary memory. This
and implement. 2.It does not require process uses external memory such as
the data in the array to be stored in Hard Disk, floppy, tape etc.
any particular order.
22. SORTING METHODS:
17. Sentinel Search: Sentinel search is Bubble Sort: In this sorting method,
a similar to the linear search where the the list is divided into two sub-lists
number of comparisons is reduced as sorted and unsorted. The smallest
compared to a traditional linear search. element is bubbled from unsorted sub-
list. After moving the smallest
18. Probability Search: In the
elements, the imaginary wall moves
probability search, the data in the array
one element ahead. The bubble sort
are arranged with the most probable
was originally written to bubble up the
search elements at the beginning of
highest element in the list. But there is
the array and the least probable at the
no difference whether highest / lowest
end.
element is bubbled. This method is
19. Binary Search: The binary search easy to understand but time
starts by testing the data in the middle consuming. In this type, two successive
element of the array. This determines elements are compared and swapping
target is whether in the first half or is done.
second half.
Insertion Sort: In insertion sort the 24. Difference Array and Linked List
element is inserted at an appropriate Array: 1. Array is a collection of
place. Here the array is divided into elements of similar data type.
two parts sorted and unsorted sub- 2.Elements are stored in contiguous
array. In each pass, the first element of memory location or consecutive
unsorted sub array is picked up and manner in the memory. 3.Array can be
moved into the sorted sub array by 1-dimensional, 2-dimensional or
inserting it in suitable position. multidimensional. 4.Size of the array is
Selection Sort: In selection sort, the fixed must be known in advance.
smallest element is exchanged with the 5.Array is an static data structure.
first element of the unsorted list of Linked List: 1. Linked list is an ordered
elements (the exchanged element collection of elements of same type,
takes the place where smallest which are connected to each other
element is initially placed). using pointers. 2.New elements can be
Merge Sort: The basic concept of stored anywhere in the memory.
merge sort is divides the list into two 3.Linked list can be singly, doubly or
smaller sub lists of approximately circular. 4.Size of a linked list is
equal size. Quick Sort: numbers are variable. 5.Linked list is an dynamic
divided and again subdivided and data structure.
division goes on until it is not possible
25. Linked List: A linked list can be
to divide further the procedure is
defined as, “an ordered collection of
applied recursively to the two parts of
finite homogeneous data elements
the array, on either side of the pivot
called as nodes where the linear order
element. Counting Sort: Counting sort
is maintained by means of links or
is an algorithm for sorting a collection
pointers”. Operations on Linked List:
of objects according to keys that are
1.Create a linked list, 2.Traverse a
small integers. So, it is an integer
linked list, 3.Insert a node in the linked
sorting algorithm. Radix Sort: Radix
list, 4.Delete a node in the linked list.
sort it is a non-comparison based
Advantages of Linked List: 1.Linked
algorithm suitable for integer values to
Lists are Dynamic Data Structures, 2.
be sorted. It sorts the elements digit by
Efficient Memory Utilization,
digit.
3.Insertion and Deletions are Easier
23. LIST: A list can be defined as, “a and Efficient, 4.Easy for Complex
collection of elements”. A linked list is a Application.
linear collection of data elements
26. TYPES OF LINKED LIST:
called nodes, each pointing to the next
1 Singly Linked List: The way to
node by means of pointers.
represent a linear list is to expand each
node to contain a link or pointer to the
next node. This representation is called
a one-way chain or singly linked list. ai are either atoms or the list of atoms.
Advantages of Singly Linked List: (i) Thus A = (a1, a2, a3, ... an)”.
Accessibility of a node in the forward
29. STACK: A stack is an ordered
direction is easier. (ii) Insertion and
collection of homogeneous data
deletion of nodes are easier.
element where the insertion and
2. Doubly Linked List: It is also called
deletion operations take place at only
as two-way linked list. A linked list
one end called as TOP of the stack.
which can be traversed both in
APPLICATIONS OF STACK: 1.
backward as well as forward direction
Expression Conversion, 2.Expression
is called doubly linked list. Advantages
Evaluation, 3.Syntax Parsing, 4.String
of Doubly Linked List: (i) Doubly
Reversal, 5.Parenthesis Checking, 7.
linked list with header node, most of
Function Call.
the problems can be solved very easily
and effectively.(ii) Insertion and 30. Function Call and Recursion: A
deletion are simple as compared to function is a self-contained block of
other lists. 3. Circular Linked List: A code that executes a certain task.
linked list in which the pointer of the Recursion: A procedure is called
last node points to the first node of the recursive, if the procedure is defined
list is called circular linked list. by itself.

27. Difference Singly, Doubly Linked 31. Queue: A queue is a linear list of
List: elements in which data can only be
Singly Linked List (SLL): 1.Singly inserted at one end, called the rear
linked list allows us to go one way and deleted from other end, called the
direction. 2.Singly linked list uses less front. Advantages of Queues:
memory per node (one pointer). 3. 1.Queues are flexible, requiring no
Complexity of Insertion and Deletion at communication programming.
known position is O(n). 4.Singly linked 2.Adding or removing elements can be
list is unidirectional i.e., only one done quickly. 3.Queue is used in many
direction. applications such as printing
Doubly Linked List (DLL): 1.Doubly documents. 4.Queue provides first-in,
linked list has two way directions next first-out access.
and previous. 2.Doubly linked list uses
32. TYPES OF QUEUE:
more memory per node. 3.Complexity
1.Linear Queue: A queue is a linear
of Insertion and Deletion at known
data structure in which data can only
position is 0(1). 4.It is bidirectional.
be inserted at one end, called the rear,
28.GENERALIZED LINKED LIST: is and deleted from the other end, called
defined as, “a finite sequence of n>=0 the front. 2.Circular Queue: In a
elements, a1, a2, a3, ..., an, such that circular queue, all nodes aretreated as
circular. Last node is connected back to
the first node.
3.Dequeue (Double Ended Queue): In
Double Ended Queue, insert and
delete operation can be occur at both
ends that is front and rear of the
queue. 4.Priority Queue: Priority
queue contains data items which have
some preset priority.
33. Round Robin Algorithm: The
Round Robin (RR) algorithm is one of
the CPU scheduling algorithms
designed for the time sharing systems.
In RR algorithm, the CPU is allocated to
a process for a small time inter val
called time quantum.