Data Structure Introduction to Data Structure

Introduction to Data Structure

Data Structure
Structure means particular way of data organization.
Data structure is refer to the organization of data in computer memory or the way in which
data is efficiently stored, process and retrieve is called data structure.
Data structure is a structural representation of logical relationship between elements of data.

Types of data structure:

Depending on arrangement of data, data structure can be classified as array, Linked list,
Queue, Tree or Graph.

A. According to Size:
a. Static DS: A Static Data Structure is said to be static if we can store data upto a fixed
number. Eg Array.
b. Dynamic DS: A dynamic Data Structure who allows programmer to change its size
during execution of program, i.e. to add or remove data. Eg. Linked List, Graph, Array.
B. According to its occurrence:
a. Linear Data Structure: In linear data structure data is stored in consecutive memory
location or data is stored in sequential form i.e. every element in a structure has unique
predecessor and unique successor. Example Array, Stack, Queue, Linked List.
b. Nonlinear data structure This type is opposite to linear. The data values in this
structure are not arranged in order. Example Graph, Tree

By: Suyog Sawant Page 1

Data Structure Introduction to Data Structure
Graph
Graphs representations have found application in almost all subjects like geography,
engineering and solving games and puzzles.
A graph G consist of
1. Set of vertices V (called nodes), (V = {v1, v2, v3, v4......}) and
2. Set of edges E (i.e., E {e1, e2, e3......cm}
A graph can be represents as G = (V, E), where V is a finite and non-empty set at vertices and E
is a set of pairs of vertices called edges. Each edge ‘e’ in E is identified with a unique pair (a, b) of
nodes in V, denoted by e = [a, b].

Tree
One of the important non-liner data structure in computer science, Trees. Many real life
problems can be represented and solved using trees. Trees are very flexible, versatile and powerful
non-liner data structure that can be used to represent data items possessing hierarchical relationship
between the grand father and his children and grandchildren as so on.

Abstract Data Type (ADT)

Abstract data type:

ADT is a specification of set of data and set of operation that operates on data. ADT is a
mathematical model used to understand the design of data structure that may be include set of domain
called data values, Set of functions for operations call interfaced and set of axioms that defines the
semantics of operation in which only what is to be done is mentioned

Examples-
Array
Arrays are most frequently used in programming. Mathematical problems like matrix, algebra
and etc can be easily handled by arrays.
An array is a collection of homogeneous data elements described by a single name. Each
element of an array is referenced by a subscripted variable or value, called subscript or index
enclosed in parenthesis. If an element of an array is referenced by single subscript, then the array is
known as one dimensional array or linear array and if two subscripts are required to reference an
element, the array is known as two dimensional array and so on.
Analogously the arrays whose elements are referenced by two or more subscripts are called
multi-dimensional arrays.

List
A list is an ordered set consisting of a varying number of elements to which insertion and
deletion can be made. A list represented by displaying the relationship between the adjacent elements
is said to be a linear list. Any other list is said to be nonlinear. List can be implemented by using
pointers. Each element is referred to as nodes; therefore a list can be defined as a collection of nodes
as shown below:

By: Suyog Sawant Page 2

Data Structure Introduction to Data Structure

Stack
A stack is one of the most important and useful non-primitive linear data structure in
computer science. It is an ordered collection of items into which new data items may be added
/inserted and from which items may be deleted at only one end, called the top of the stack. As all the
addition and deletion in a stack is done from the top of the stack, the last added element will be first
removed from the stack. That is why the stack is also called
Last-in-First-out (LIFO)
Note that the most frequently accessible element in the stack is the top most elements, whereas the
least accessible element is the bottom of the stack. The operation of the stack can be illustrated as in
figure below In below diagram instead of top its TOS (top of stack)

The insertion (or addition) operation is referred to as push, and the deletion (or remove)
operation as pop. A stack is said to be empty or underflow, if the stack contains no elements. At this
point the top of the stack is present at the bottom of the stack. And it is overflow when the stack
becomes full, i.e., no other elements can be pushed onto the stack. At this point the tos pointer is at
the highest location of the stack.

By: Suyog Sawant Page 3

Data Structure Introduction to Data Structure

Queue
It is logically a first in first out (FIFO) linear data structure.
The concept of queue can be understood by our real life problems. For example a customer
come and join in a queue to take the train ticket at the end (rear) and the ticket is issued from the front
end of queue. That is, the customer who arrived first will receive the ticket first. It means the
customers are serviced in the order in which they arrive at the service centre.
It is a homogeneous collection of elements in which new elements are added at one end called
rear, and the existing elements are deleted from other end called front.

The basic operations that can be performed on queue are

1. Insert (or add) an element to the queue.
2. Delete (or remove) an element from a queue.

Array
C Programming Arrays
In C programming, one of the frequently arising problem is to handle similar types of data.
For example: If the user want to store marks of 100 students. This can be done by creating 100
variable individually but, this process is rather tedious and impracticable. These type of problem can
be handled in C programming using arrays.
An array is a sequence of data item of homogeneous value (same type).
Arrays are of two types:
A. One-dimensional arrays
B. Multidimensional arrays

One-dimensional arrays

Declaration of one-dimensional array

Data_type array_name [ array_size] ;
For example :
int marks [ 5 ] ;
Here, the name of array is marks. The size of array is 5, i.e., there are 5 items(elements) of
array marks. All element in an array are of the same data type i.e. int.
Size of array defines the number of elements in an array. Each element of array can be
accessed and used by user according to the need of program.
For example:
int marks[5];
marks[0] marks[1] marks[2] marks[3] marks[4]

Note that, the first element is numbered 0 and so on.

By: Suyog Sawant Page 4

Data Structure Introduction to Data Structure
Here, the size of array marks is 5 times the size of int because there are 5 elements, hence total
memory required to store array is 10. Suppose, the starting address of marks[0] is 5001 and the size
of int be 2 bytes. Then, the next address of marks[1] will be 5003, address of marks[2] will be 5005
and so on.
Initialization of one-dimensional array:
Arrays can be initialized at declaration time in this source code as:
int age[5]= 2, 4, 34, 3, 4;
It is not necessary to define the size of arrays during initialization.
int age[]=2, 4, 34, 3, 4;
In this case, the compiler determines the size of array by calculating the number of elements of an
array.

Multidimensional Arrays
C programming language allows programmer to create arrays of arrays known as
multidimensional arrays.
Declaration of one-dimensional array
Data_type array_name [ array_size] [array_size];
For example :
int marks [ 5 ] [ 6 ] ;

Marks
[0][0] [0][1] [0][2] [0][3] [0][4] [0][5]
[1][0]
[2][0]
[3][0]
[4][0] [4][5]

By: Suyog Sawant Page 5