INTRODUCTION TO DATASTRUCTURE
Computer is an electronic machine which is used for data processing and
manipulation. When programmer collects such type of data for processing,
require to store all of them in computer’s main memory.
i. In order to make computer work follow the below
o Representation of data in computer.
o Accessing of data.
o How to solve problem step by step.
ii. For doing this task use data structure.
What is Data Structure?
i. Data structure is a representation of the logical relationship
existing between individual elements of data.
ii. Data Structure is a way of organizing all data items that considers
not only the elements stored but also their relationship to each
other.
iii. It can also define data structure as a mathematical or logical
model of a particular organization of data items.
iv. The representation of particular data structure in the main memory
of a computer is called as storage structure.
v. The storage structure representation in auxiliary memory is called as file
structure.
vi. It is defined as the way of storing and manipulating data in
organized form so that it can be used efficiently.
vii. Data Structure mainly specifies the following four things
a. Organization of Data
b. Accessing methods
c. Degree of associativity
d. Processing alternatives for information
viii. Algorithm + Data Structure = Program
ix. Data structure study covers the following points
a. Amount of memory require to store.
b. Amount of time require to process.
c. Representation of data in memory.
d. Operations performed on that data.
DATA
PRIMITIV NON
INTEGER FLOATING CHARACTE POINTER ARRAY LIST FILE
LINEAR NON
STACK QUEUE GRAPH TREE
Data Structures are normally classified into two broad categories
1. Primitive Data Structure
2. Non-primitive data Structure
Data types
A particular kind of data item, as defined by the values it can take, the
programming language used, or the operations that can be performed
on it.
Primitive Data Structure
i. Primitive data structures are basic structures and are directly operated upon
by machine instructions.
ii. Primitive data structures have different representations on different
computers.
iii. Integers, floats, character and pointers are examples of primitive data
structures.
iv. These data types are available in most programming languages as built in
type.
Integer: It is a data type which allows all values without fraction part.
Use it for whole numbers also.
Float: It is a data type which use for storing fractional numbers.
Character: It is a data type which is used for character values.
Pointer: A variable that holds memory address of another variable
are called pointer.
Non primitive Data Type
i. These are more sophisticated data structures.
ii. These are derived from primitive data structures.
iii. The non-primitive data structures emphasize on structuring of a
group of homogeneous or heterogeneous data items.
iv. Examples of Non-primitive data type are Array, List, and File etc.
A Non-primitive data type is further divided into Linear and Non-Linear data
structure
Array: An array is a fixed-size sequenced collection of elements of the same
data type.
List: An ordered set containing variable number of elements is called as
Lists.
File: A file is a collection of logically related information. It can be
viewed as a large list of records consisting of various fields.
Linear data structures
i. A data structure is said to be Linear, if its elements are connected in
linear fashion by means of logically or in sequence memory
locations.
ii. There are two ways to represent a linear data structure in memory,
Static memory allocation
Dynamic memory allocation
iii. The possible operations on the linear data structure are: Traversal,
Insertion, Deletion, Searching, Sorting and Merging.
Examples of Linear Data Structure are Stack and Queue.
iv. Stack: Stack is a data structure in which insertion and deletion operations
are performed at one end only.
The insertion operation is referred to as ‘PUSH’ and deletion
operation is referred to as ‘POP’ operation.
Stack is also called as Last in First out (LIFO) data structure.
v. Queue: The data structure which permits the insertion at one end
and Deletion at another end, known as Queue.
End at which deletion is occurs is known as FRONT end and
another end at which insertion occurs is known as REAR end.
Queue is also called as First in First out (FIFO) data structure.
Nonlinear data structures
i. Nonlinear data structures are those data structure in which data items are
not arranged in a sequence.
ii. Examples of Non-linear Data Structure are Tree and Graph.
iii. Tree: A tree can be defined as finite set of data items (nodes) in
which data items are arranged in branches and sub branches
according to requirement.
Trees represent the hierarchical relationship between various
elements.
Tree consist of nodes connected by edge, the node
represented by circle and edge lives connecting to circle.
Graph: Graph is a collection of nodes (Information) and connecting
edges (Logical relation) between nodes.
o A tree can be viewed as restricted graph.
o Graphs have many types:
Un-directed Graph
Directed Graph
Mixed Graph
Multi Graph
Simple Graph
Null Graph
Weighted Graph
Difference between Linear and Non Linear Data Structure
Linear Data Structure Non-Linear Data Structure
Every item is related to its previous and next Every item is attached with many other
time. items.
Data is arranged in linear sequence. Data is not arranged in sequence.
Data items can be traversed in a single run. Data cannot be traversed in a single run.
Eg. Array, Stacks, linked list, queue. Eg. Tree, graph.
Implementation is easy. Implementation is difficult.
Operation on Data Structures
Design of efficient data structure must take operations to be performed
on the data structures into account. The most commonly used operations
on data structure are broadly categorized into following types
1. Create
The create operation results in reserving memory for program
elements. This can be done by declaration statement. Creation of
data structure may take place either during compile-time or run-
time. malloc () function of C language is used for creation.
2. Destroy
Destroy operation destroys memory space allocated for specified
data structure. free() function of C language is used to destroy data
structure.
3. Selection
Selection operation deals with accessing a particular data within a data
structure.
4. Updation
It updates or modifies the data in the data structure.
5. Searching
It finds the presence of desired data item in the list of data items, it
may also find the locations of all elements that satisfy certain
conditions.
6. Sorting
Sorting is a process of arranging all data items in a data structure
in a particular order, say for example, either in ascending order or
in descending order.
7. Merging
Merging is a process of combining the data items of two different sorted
list into a single sorted list.
8. Splitting
Splitting is a process of partitioning single list to multiple list.
9. Traversal
Traversal is a process of visiting each and every node of a list in
systematic manner.
Time and space analysis of algorithms
Algorithm
An essential aspect to data structures is algorithms.
Data structures are implemented using algorithms.
An algorithm is a procedure that you can write as a C function or
program, or any other language.
An algorithm states explicitly how the data will be manipulated.
Algorithm Efficiency
Some algorithms are more efficient than others. We would prefer
to choose an efficient algorithm, so it would be nice to have
metrics for comparing algorithm efficiency.
The complexity of an algorithm is a function describing the
efficiency of the algorithm in terms of the amount of data the
algorithm must process.
Usually there are natural units for the domain and range of this
function. There are two main complexity measures of the
efficiency of an algorithm.
Time complexity
Time Complexity is a function describing the amount of time an
algorithm takes in terms of the amount of input to the algorithm.
"Time" can mean the number of memory accesses performed,
the number of comparisons between integers, the number of
times some inner loop is executed, or some other natural unit
related to the amount of real time the algorithm will take.
Space complexity
Space complexity is a function describing the amount of memory (space)
an algorithm takes in terms of the amount of input to the algorithm.
Space complexity is sometimes ignored because the space used is
minimal and/or obvious, but sometimes it becomes as important an
issue as time.