DATA STRUCTURES
Data structure:
1. A data structure is a way of organizing all data items that considers not only the elements stored but
also their relationship to each other.
2. Data structure is the representation of the logical relationship existing between individual elements of
data.
3. Data structure is defining as a mathematical or logical model of particular organization of data items.
Data structure is needed because:
1. It helps to understand the relationship of one element with the other.
2. It helps in the organization of all data items within the memory.
Classification of Data Structure/ type of data structure
Data structure has many different uses in our daily life. There are many different data
structures that are used to solve different mathematical and logical problems. By using data
structure, one can organize and process a very large amount of data in a relatively short period.
Linear data structure: Data structure in which data elements are arranged sequentially or
linearly, where each element is attached to its previous and next adjacent elements is called
a linear data structure.
Examples: array, stack, queue, linked list, etc.
o Static data structure: Static data structure has a fixed memory size. It is easier
to access the elements in a static data structure.
Example: array data structure.
o Dynamic data structure: In the dynamic data structure, the size is not fixed. It
can be randomly updated during the runtime which may be considered efficient
concerning the memory (space) complexity of the code.
Examples: stack and queue data structures.
Non-linear data structure: Data structures where data elements are not placed
sequentially or linearly are called non-linear data structures. In a non-linear data
structure, we can’t traverse all the elements in a single run.
Examples: tree and graph data structures.
Need of data type: The data type is needed because it determines what type of information can be
stored in the field and how the data can be formatted.
Basic terminologies used in data structure :
1. Data: Data are simply values or sets of values. A data item refers to a single unit of values.
2. Entity: An entity is something that has certain attributes or properties which may be assigned
values.
3. Field : A field is a single elementary unit of information representing an attribute of an entity.
4. Record: A record is the collection of field values of a given entity.
5. File: A file is the collection of records of the entities in a given entity set.
Data organization: Each record in a file may contain many field items, but the value in a certain field
may uniquely determine the record in the file. Such a field K is called a primary key, and the values
k1 , k2 ,... in such a field are called keys or key values.
Define algorithm
1. An algorithm is a step-by-step finite sequence of instructions, to solve a well-defined computational
problem.
2. Every algorithm must satisfy the following criteria:
i. Input: There are zero or more quantities which are externally supplied.
ii. Output: At least one quantity is produced.
iii. Definiteness: Each instruction must be clear and unambiguous.
iv. Finiteness: If we trace out the instructions of an algorithm, then for all cases the algorithm will
terminate after a finite number of steps.
v. Effectiveness: Every instruction must be basic and essential.
Define complexity and its types.
1. The complexity of an algorithm M is the function f(n) which gives the running time and/or storage
space requirement of the algorithm in terms of the size n of the input data.
2. The storage space required by an algorithm is simply a multiple of the data size n.
3. Following are various cases in complexity theory:
a. Worst case: The maximum value of f(n) for any possible input.
b. Average case: The expected value of f(n) for any possible input.
c. Best case: The minimum possible value of f(n) for any possible input.
Types of complexity:
1. Space complexity: The space complexity of an algorithm is the amount of memory it needs to run to
completion.
2. Time complexity: The time complexity of an algorithm is the amount of time it needs to run to
completion.
Array:
Array is a linear data structure where all elements are arranged sequentially. It is a
collection of elements of same data type stored at contiguous memory locations.
types of an array.
There are two types of array:
1. One-dimensional array:
a. An array that can be represented by only one-one dimension such as row or column and that holds
finite number of same type of data items is called one-dimensional (linear) array.
b. One dimensional array (or linear array) is a set of ‘n’ finite numbers of homogeneous data elements
such as:
i. The elements of the array are referenced respectively by an index set consisting of ‘n’ consecutive
number.
ii. The elements of the array are stored respectively in successive memory locations. ‘n’ number of
elements is called the length or size of an array. The elements of an array ‘A’ may be denoted in C
language as : A[0], A[1], A[2], ... A[n –1]
2. Multidimensional arrays:
a. An array can be of more than one dimension. There are no restrictions to the number of dimensions
that we can have.
b. As the dimensions increase the memory requirements increase drastically this can result in shortage
of memory.
c. Hence a multidimensional array must be used with utmost care. d. For example, the following
declaration is used for 3-D array:
int a [50] [50] [50];
Row major and column major
In programming and computer science, row-major and column-major refer to two different
ways of storing multidimensional arrays (like matrices) in memory. These concepts describe the
order in which the elements of an array are laid out in memory.
1. Row-major order:
In row-major order, elements of the array are stored row by row. That is, the elements of the first
row are stored first, followed by the elements of the second row, and so on.
Row-major and column-major order is approaches in computing for storing arrays
with multiple dimensions in linear memory, such as random access memory (RAM).
The two methods differ in the sequence in which elements are stored concurrently in
the memory. The items in row-major order are organized sequentially down the row,
whereas those in column-major order are arranged sequentially along the column.