BASIC DATA STRUCTURES

UNIT I
Data structure is a collection of data type ‘values’ which are stored and organized in such a
way that it allows for efficient access and modification.
Data Types
Each variable in C has an associated data type. Each data type requires different amounts of
memory and has some specific operations which can be performed over it. Let us briefly describe
them one by one:
Following are the examples of some very common data types used in C:
 char: The most basic data type in C. It stores a single character and requires a single byte
of memory in almost all compilers.
 int: As the name suggests, an int variable is used to store an integer.
 float: It is used to store decimal numbers (numbers with floating point value) with single
precision.
 double: It is used to store decimal numbers (numbers with floating point value) with
double precision.
Different data types also have different ranges upto which they can store numbers. These ranges
may vary from compiler to compiler.

[Link]. Types & Description

1
Basic Types
They are arithmetic types and are further classified into: (a) integer types and (b) floating-
point types.

2
Enumerated types
They are again arithmetic types and they are used to define variables that can only assign
certain discrete integer values throughout the program.

3
The type void
The type specifier void indicates that no value is available.

4
Derived types
They include (a) Pointer types, (b) Array types, (c) Structure types, (d) Union types and (e)
Function types.

1|P a ge
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
 The void Type

Void type means no value. This is usually used to specify the type of functions which returns
nothing.

[Link]. Types & Description

1
Function returns as void
There are various functions in C which do not return any value or you can say they return
void. A function with no return value has the return type as void. For example, void exit
(int status);

2
Function arguments as void
There are various functions in C which do not accept any parameter. A function with no
parameter can accept a void. For example, int rand(void);

3
Pointers to void
A pointer of type void * represents the address of an object, but not its type. For example,
a memory allocation function void *malloc( size_t size ); returns a pointer to void which
can be casted to any data type.

Data Types Description

Arrays Arrays are sequences of data items having homogeneous values. They have adjacent
memory locations to store values.

References Function pointers allow referencing functions with a particular signature.

Pointers These are powerful C features which are used to access the memory and deal with their
addresses

Derived types

C allows the feature called type definition which allows programmers to define their identifier
that would represent an existing data type. There are three such types:

2|P a ge
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
Data Types Description

Structure It is a package of variables of different types under a single name. This is done to handle
data efficiently. "struct" keyword is used to define a structure.

Union These allow storing various data types in the same memory location. Programmers can
define a union with different members, but only a single member can contain a value at
a given time. It is used for

Enum Enumeration is a special data type that consists of integral constants, and each of them
is assigned with a specific name. "enum" keyword is used to define the enumerated data
type.

Abstract Data Types

Abstract Data type (ADT) is a type (or class) for objects whose behaviour is defined by a set
of value and a set of operations.
The definition of ADT only mentions what operations are to be performed but not how these
operations will be implemented. It does not specify how data will be organized in memory
and what algorithms will be used for implementing the operations. It is called “abstract”
because it gives an implementation-independent view. The process of providing only the
essentials and hiding the details is known as abstraction.

The user of data type does not need to know how that data type is implemented, for example,
we have been using Primitive values like int, float, char data types only with the knowledge
that these data type can operate and be performed on without any idea of how they are
implemented. So a user only needs to know what a data type can do, but not how it will be

3|P a ge
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
implemented. Think of ADT as a black box which hides the inner structure and design of the
data type. Now we’ll define three ADTs namely List ADT, Stack ADT, Queue ADT.

1. List ADT

 The data is generally stored in key sequence in a list which has a head structure
consisting of count, pointers and address of compare function needed to compare the
data in the list.

A list contains elements of the same type arranged in sequential order and following
operations can be performed on the list.
 get() – Return an element from the list at any given position.
 insert() – Insert an element at any position of the list.
 remove() – Remove the first occurrence of any element from a non-empty list.
 removeAt() – Remove the element at a specified location from a non-empty list.
 replace() – Replace an element at any position by another element.
 size() – Return the number of elements in the list.
 isEmpty() – Return true if the list is empty, otherwise return false.
 isFull() – Return true if the list is full, otherwise return false.

2. Stack ADT

 In Stack ADT Implementation instead of data being stored in each node, the pointer to
data is stored.
 The program allocates memory for the data and address is passed to the stack ADT.

4|P a ge
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
The head node and the data nodes are encapsulated in the ADT. The calling function can only
see the pointer to the stack.

A Stack contains elements of the same type arranged in sequential order. All operations take
place at a single end that is top of the stack and following operations can be performed:
 push() – Insert an element at one end of the stack called top.
 pop() – Remove and return the element at the top of the stack, if it is not empty.
 peek() – Return the element at the top of the stack without removing it, if the
stack is not empty.
 size() – Return the number of elements in the stack.
 isEmpty() – Return true if the stack is empty, otherwise return false.
 isFull() – Return true if the stack is full, otherwise return false.

3. Queue ADT

The queue abstract data type (ADT) follows the basic design of the stack abstract data type.

5|P a ge
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
A Queue contains elements of the same type arranged in sequential order. Operations take
place at both ends, insertion is done at the end and deletion is done at the front. Following
operations can be performed:
 enqueue() – Insert an element at the end of the queue.
 dequeue() – Remove and return the first element of the queue, if the queue is not empty.
 peek() – Return the element of the queue without removing it, if the queue is not empty.
 size() – Return the number of elements in the queue.
 isEmpty() – Return true if the queue is empty, otherwise return false.
 isFull() – Return true if the queue is full, otherwise return false.

ALGORITHM AND PROBLEM SOLVING:

The set of instructions called a program. Any computing has to be performed independently
without depending on the programming language and the computer.

The problem solving techniques involves the following steps

1. Define the problem.
2. Formulate the mathematical model.

6|P a ge
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
 3. Develop an algorithm.
4. Write the code for the problem.
5. Test the program.

1. Define the Problem

 A clear and concise problem statement is provided.

 The problem definition should specify the input and output.
 Full knowledge about the problem is needed.

Example: TO FIND THE AVERAGE OF TWO NUMBERS.

2. Formulate the Mathematical Problem

 Any technical problem provided can be solved mathematically.

 Full knowledge about the problem should be provided along with the underlying
mathematical concept.

Example: (data1+data2)/2

3. Develop an Algorithm

 An algorithm is the sequence of operations to be performed.

 It gives the precise plan of the problem.
 An algorithm can be of flowchart or pseudo code.

Example:

Problem Definition: TO FIND THE AVERAGE OF TWO NUMBERS.

Algorithm:

STEP 1: Set the sum of the data values to 0.

STEP 2: Set the count of the data values to zero.
STEP 3: As long as the data values exist, add the next data value to
the sum and add 1 to the count.
STEP 4: To compute the average, divide the sum by the count.
STEP 5: Print the average.

Task: To find the average of 20 and 30 manually.

20 + 30=50 ; 50/2 =25.

4. Write the Code for the Problem

 The algorithm developed must be converted to any programming language.

 The compiler will convert the program code to the machine language which the
computer can understand.

7|P a ge
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
 5. Test the Program

 Testing involves checking errors both syntactically and semantically.

 The errors are called as “bugs”.
 When the compiler finds the bugs, it prevents compiling the code from programming
language to machine language.
 Check the program by providing a set of data for testing.

Problem Solving Process

The process of problem-solving is an activity which has its ingredients as the specification
of the program and the served dish is a correct program. This activity comprises of four steps

1. Understanding the problem: To solve any problem it is very crucial to understand the
problem first. The obvious and essential need to generate the output is an input. The input
may be singular or it may be a set of inputs. A proper relationship between the input and
output must be drawn in order to solve the problem efficiently. It means all the necessary
inputs required to compute the output should be present at the time of computation. However,
it should be kept in mind that the programmer should ensure that the minimum number of
inputs should be there. Any irrelevant input only increases the size of and memory overhead
of the program. Thus Identifying the minimum number of inputs required for output is
a crucial element for understanding the problem.

2. Devising the plan: Once a problem has been understood, a proper action plan has to be
devised to solve it. This is called devising the plan. This step usually involves computing the
result from the given set of inputs. It uses the relationship drawn between inputs and outputs
in the previous step. The complexity of this step depends upon the complexity of the problem
at hand.

3. Executing the plan: Once the plan has been defined, it should follow the trajectory of
action while ensuring the plan’s integrity at various checkpoints. If any inconsistency is
found in between, the plan needs to be revised.

4. Evaluation: The final result so obtained must be evaluated and verified to see if the
problem has been solved satisfactorily.

Problem Solving Methodology(The solution for the problem)

The methodology to solve a problem is defined as the most efficient solution to the problem.
Under problem-solving methodology, we will see a step by step solution for a problem. These
steps closely resemble the software life cycle.

Step by step solution for a problem (Software Life Cycle)

1. Problem Definition/Specification:
In order to solve the problem, it is very necessary to define the problem to get its proper
understanding. For example, suppose we are asked to write a code for “ Compute the average
of three numbers”.Once a problem has been defined, the program’s specifications are then
listed. Problem specifications describe what the program for the problem must do.

8|P a ge
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
2. Problem Analysis (Breaking down the solution into simple steps): The problem is
divided into subproblems so that designing a solution to these subproblems gets easier. The
solutions to all these individual parts are then merged to get the final solution of the original
problem. It is like divide and merge approach.

Modular Approach for Programming :

The process of breaking a large problem into subproblems and then treating these individual
parts as different functions is called modular [Link] function behaves
independent of another and there is minimal inter-functional communication. There are two
methods to implement modular programming :
1. Top Down Design : In this method, the original problem is divided into subparts. These
subparts are further divided. The chain continues till we get the very fundamental subpart
of the problem which can’t be further divided. Then we draw a solution for each of these
fundamental parts.

2. Bottom Up Design : In this style of programming, an application is written by using the

pre-existing primitives of programming language. These primitives are then amalgamated
with more complicated features, till the application is written. This style is just the reverse
of the top-down design style.

9|P a ge
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
2. Design – Algorithm & Flowchart Development

 Algorithm and flowchart are developed to provide a sequence of actions to be

performed.
 Algorithm provides a basic logic in solving the problem by providing sequence of
instructions.

Algorithm can be of
[Link] chart
2. Pseudo Code.

Program Design Language(PDL) : It has no specific standard rules for defining the PDL
statements. PDL is independent of any programming language. It is also called as Pseudo Code.

3. Program Coding

 Code the algorithm in the selected programming language.

 The processes of translating the algorithm or the flowchart into an exact instruction that
will make up the program are called program coding.

4. Program Compilation and Execution

 After program coding, the program has to be compiled and executed.
 During compilation, if no error is produced, then the program is executed successfully.
 If errors are available, then the errors are displayed in the terminal, and corrected later
with correct syntax and then compiled.

5. Program Debugging and Testing

 Errors are called as “bugs”

 Errors can be categorized as follows

Syntax errors(during compilation).

Example: Program does not compile, missing bracket, bad punctuation.

Run time (during execution)

Example: Program crashes, Check input data.

Logical (incorrect or illogical answers)

Example: Program runs and give wrong output.

6. Documentation

 Once the programmer is free from the errors, it is the duty of the programmer to
document all the necessary documents which is provided to the program users as
manual.
 Helps the user to operate correctly.

10 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
ALGORITHM

 Algorithms are one of the most basic tools that are used to develop the problem solving
logic.
 An algorithm is defined as a finite sequence of explicit instructions that, when provided
with a set of input values produces an output and then terminates.
 In algorithm, after a finite number of steps, solution of the problem is achieved.
 Algorithms can have steps that repeat (iterate) or require decisions (logic and
 comparison) until the task is completed.
 Different algorithms may accomplish the same task, with a different set of instructions,
in more or less the same time, space, and efforts.

EXAMPLE: To determine the largest number out of three numbers A, B, and C

Step 1: Start
Step 2: Read three numbers say A, B, C
Step 3: Find the larger number between A and B and store it in MAX_AB
Step 4: Find the larger number between MAX_AB and C and store it in MAX
Step 5: Display MAX
Step 6: Stop

The above-mentioned algorithm terminates after six steps. This explains the feature of
finiteness. Every action of the algorithm is precisely defined; hence, there is no scope for
ambiguity. Once the solution is properly designed, the only job left is to code that logic into a
programming language.

1. Characteristics of Algorithm

An algorithm has five main characteristics:

 It should have finite number of inputs.

 Terminates after a finite number of steps.
 Instructions are precise and unambiguous.
 Operations are done exactly and in a finite amount of time.
 Outputs are derived from the input by applying the algorithm

2. Quality of Algorithm

There are few factors that determine the quality of a given algorithm
 An algorithm should be relatively fast.
 Any algorithm should require minimum computer memory to produce the desired
output in an acceptable amount of time.

FLOWCHART
 Flowchart is a diagrammatic representation of an algorithm that illustrates the sequence
of operations to be performed to get a solution.
 The different boxes are interconnected with the help of arrows.

11 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
  The boxes represent operations and the arrows represent the sequence in which the
operations are implemented.
 The primary purpose of the flowchart is to help the programmer in understanding the
logic of the program.

1. Flowchart Symbols
Symbol Symbol Name Description

Flow Lines Flow lines are used to

connect symbols. These
lines indicate the sequence
of steps and the direction of
flow of control.

Terminal This symbol is used to

represent the beginning
(start), the termination
(end), or halt (pause) in the
program logic.

Input/Output It represents information

entering or leaving the
system, such as customer
order (input) and servicing
(output).

Processing Process symbol is used for

representing arithmetic and
data movement instructions.
It can represent a single step
('add two cups of flour'), or
an entire sub-process ('make
bread') within a larger
process.

Decision Decision symbol denotes a

decision (or branch) to be
made. The program should
continue along one of the
two routes (IF/ELSE).
This symbol has one entry
and two exit paths. The path
chosen depends on whether
the answer to a question is
yes or no.
Connector Connector symbol is used to
join different flow lines.

12 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
 Off-page This symbol is used to
Connector indicate that the flowchart
continues on the next page.

Document Document is used to

represent a paper document
produced during the
flowchart process.

Manual Input Manual input symbol

represents input to be given
by a developer /
programmer.

Manual Operation Manual operation symbol

shows that the process has to
be done by a
developer/programmer.

Online Storage This symbol represents the

online data storage such as
hard disks, magnetic drums,
or other storage devices.

Communication Link Communication link symbol

is used to represent data
received or to be transmitted
from an external system

Magnetic Disk This symbol is used to

represent data input or
output from and to a
magnetic disk.

Guidelines for preparing flowcharts The following guidelines should be used for creating a
flowchart:

 The flowchart should be clear, neat, and easy to follow.

 The flowchart must have a logical start and finish.
 In drawing a proper flowchart, all necessary requirements should be listed in logical
order.
 Only one flow line should come out from a process symbol.
 Only one flow line should enter a decision symbol. However, two or three flow lines
(one for each possible answer) may leave the decision symbol.
 Only one flow line is used with a terminal symbol.
 In case of complex flowcharts, connector symbols are used to reduce the number of
flow lines.

13 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
2. Benefits of Flowcharts

A flowchart helps to clarify how things are currently working and how they could-be improved.
The reasons for using flowcharts as a problem-solving tool are given below.

i) Makes Logic Clear: The main advantage of using a flowchart to plan a task is that it provides
a pictorial representation of the task, which makes the logic easier to follow. Even less
experienced personnel can trace the actions represented by a flowchart, that is, flowcharts are
ideal for visualizing fundamental control structures employed in computer programming.

ii) Communication: Being a graphical representation of a problem-solving logic, flowcharts

are better way of communicating the logic of a system to all concerned. The diagrammatical
representation of logic is easier to communicate to all the interested parties as compared to
actual program cede as the users may not be aware of all the programming techniques.

iii) Effective Analysis: With the help of a flowchart, the problem can be analyzed in an
effective way. This is because the analyzing duties of the programmers can be delegated to
other persons, who may or may not know the programming techniques, but they have a broad
idea about the logic.

iv) Useful in Coding: The flowcharts act as a guide or blueprint during the analysis and
program development phase. Once the flowcharts are ready, the programmers can plan the
coding process effectively as they know where to begin and where to end, making sure that no
steps are omitted. As a result, error free programs are developed in high-level language and
that too at a faster rate.

3. Limitation of Flowchart:

Flowchart can be used for designing the basic concept of the program in pictorial form but
cannot be used for programming purposes. Some of the limitations of the flowchart are given
as follows:

v) Proper Testing and Debugging: By nature, a flowchart helps in detecting the errors in a
program, as the developers know exactly what the logic should do.

vi) Appropriate Documentation: Flowcharts serve as a good program documentation tool.

Since normally the programs are developed for novice users; they can take the help of the
program documentation to know what the program actually does and how to, use the program.

i) Complex: The major disadvantage in using flowcharts is that when a program is very large,
the flowcharts may continue for many pages, making them hard to follow.

ii) Costly: Drawing flowcharts are viable only if the problem-solving logic is straightforward
and not very lengthy. However, if flowcharts are to be drawn for a huge application, the time
and cost factor of program development may get out of proportion, making it a costly affair

.
iii) Difficult to Modify: Due to its symbolic nature, any changes or modification to a flowchart
usually requires redrawing the entire logic again, and redrawing a complex flowchart is not a

14 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
simple task. It is not easy to draw thousands of flow lines and symbols along with proper
spacing, especially for a large complex program.

iv) No Update: Usually programs are updated regularly. However, the corresponding update
of flowcharts may not take place, especially in the case of large programs. As a result, the logic
used in the flowchart may not match with the actual program's logic.

PSEUDOCODE

 Pseudocode is made up of two words: pseudo and code. Pseudo means imitation and
code refers to instructions, written in a programming language. As the name suggests,
pseudocode is not a real programming code, but it models and may even look like
programming code.

 Pseudo code uses plain English statements rather than symbols, to represent the
processes of a computer program. It is also known as PDL (Program Design Language),
as it emphasizes more on the design aspect of a computer program or structured English,
because usually pseudo code instructions are written in normal English, but in a
structured way.

 If an algorithm is written in English, the description may be at such a high level that it
may prove difficult to analyze the algorithm and then to transform it into actual code.

 If instead, the algorithm is written in code, the programmer has to invest a lot of time
in determining the details of an algorithm, which he may choose not to implement
(since, typically, algorithms are analyzed before deciding which one to implement).

 Therefore, the goal of writing pseudocode is to provide a high-level description of an

algorithm, which facilitates analysis and eventual coding, but at the same time
suppresses many of the details that are insignificant.

Example: The pseudocode given below calculates the area of a rectangle.

PROMPT the user to enter the height of the rectangle

PROMPT the user to enter the width of the rectangle
COMPUTE the area by multiplying the height with width
DISPLAY the area

Pseudocode uses some keywords to denote programming processes. Some of them are:

Input: READ, OBTAIN, GET, and PROMPT

Output: PRINT, DISPLAY, and SHOW
Compute: COMPUTE, CALCULATE, and DETERMINE
Initialise: SET and INITIALISE
Add One: INCREMENT

15 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
1. Pseudocode Guidelines

Writing pseudocode is not a difficult task. Even if you do not know anything about the
computers or computer languages, you can still develop effective and efficient pseudo codes,
if you are writing in an organized manner.

Here are a few general guidelines for developing pseudocodes:

 Statements should be written in simple English and should be programming language

independent. Remember that pseudocodes only describe the logic plan to develop a
program, it is not programming.
 Steps must be understandable, and when the steps are followed, they must produce a
solution to the specified problem.
 Pseudocodes should be concise.
 Each instruction should be written in a separate line and each statement in pseudocode
should express just one action for the computer.
 Capitalize keywords such as READ, PRINT, and so on.
 Each set of instructions is written from top to bottom, with only one entry and one exit.
 It should allow for easy transition from design to coding in programming language.

2. Benefits of Pseudocode

Pseudocode provides a simple method of developing the program logic as it uses everyday
language to prepare a brief set of instructions in the order in which they appear in the completed
program. It allows the programmer to focus on the steps required to solve a program rather than
on how to use the computer language. Some of the most significant benefits of pseudocode are:

 Since it is language independent, it can be used by most programmers.

 It is easier to develop a program from a pseudocode than with a flowchart.
 Often, it is easy to translate pseudocode into a programming language, a step which can
be accomplished by less experienced programmers.
 Unlike flowcharts, pseudocode is compact and does not tend to run over many pages.
It's simple structure and readability makes it easier to modify.

3. Limitations Of Pseudocode

Although pseudocode is a very simple mechanism to simplify problem-solving logic, it has its
limitations. Some of the most notable limitations are:

 It does not provide visual representation of the program's logic.

 There are no accepted standards for writing pseudocodes.
 Pseudocode cannot be compiled nor executed, and there are no real formatting or syntax
rules.

Data Structures
Data structure is a Specific way to store and organize data in a computer's memory so that these
data can be used efficiently later. Data may be arranged in many different ways such as the
logical or mathematical model for a particular organization of data is termed as a data structure

Program=algorithm + Data Structure

16 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
Need Data Structures:

 Each data structure allows to be store data in specific manner

 Data Structures allows efficient data search and retrieval

 Specific Data Structures are decided to worked for specific problem

 It allows to manage large amount databases and indexing service such as hash table

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

 Primitive data structures are basic structures and are directly operated upon by
machine instructions.
 Primitive data structures have different representations on different computers.
 Integers, floats, character and pointers are examples of primitive data structures.
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. We can use it for

17 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
 whole numbers.
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

 These are more sophisticated data structures.

 These are derived from primitive data structures.
 The non-primitive data structures emphasize on structuring of a group of homogeneous
or heterogeneous data items.
 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

 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.
 There are two ways to represent a linear data structure in memory,
Static memory allocation
Dynamic memory allocation
 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.
 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.
 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

 Nonlinear data structures are those data structure in which data items are not arranged in a
sequence.
 Examples of Non-linear Data Structure are Tree and Graph.
 Tree: A tree can be defined as finite set of data items (nodes) in which data items are
18 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
 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.
A tree can be viewed as restricted graph.
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

Basic In this structure, the elements In this structure, the elements are
are arranged sequentially or arranged hierarchically or non-linear
linearly and attached to one manner.
another.

Types Arrays, linked list, stack, queue Trees and graphs are the types of a
are the types of a linear data non-linear data structure.
structure.

implementation Due to the linear organization, Due to the non-linear organization,

they are easy to implement. they are difficult to implement.

Traversal As linear data structure is a The data items in a non-linear data

single level, so it requires a structure cannot be accessed in a
single run to traverse each data single run. It requires multiple runs
item. to be traversed.

Arrangement Each data item is attached to Each item is attached to many other
the previous and next items. items.

19 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
Levels This data structure does not In this, the data elements are
contain any hierarchy, and all arranged in multiple levels.
the data elements are organized
in a single level.

Memory In this, the memory utilization In this, memory is utilized in a very

utilization is not efficient. efficient manner.

Time complexity The time complexity of linear The time complexity of non-linear
data structure increases with data structure often remains same
the increase in the input size. with the increase in the input size.

Applications Linear data structures are Non-linear data structures are used
mainly used for developing the in image processing and Artificial
software. Intelligence.

Operation on Data Structures

There are different types of operations that can be performed for the manipulation of data in
every data structure.

Traversing: Traversing a Data Structure means to visit the element stored in it.

Searching: Searching means to find a particular element in the given data-structure. It is

considered as successful when the required element is found.

Insertion: Insertion means to add an element in the given data structure. The operation of
insertion is successful when the required element is added to the required data-structure. It is
unsuccessful in some cases when the size of the data structure is full and when there is no
space in the data-structure to add any additional element. In stack, this operation is called
Push. In the queue, this operation is called Enqueue.

Deletion: Deletion means to delete an element in the given data structure. The operation of
deletion is successful when the required element is deleted from the data structure. In stack,
this operation is called Pop. In Queue this operation is called Dequeue.
Selection: Selection operation deals with accessing a particular data within a data structure.
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.
Merging: Merging is a process of combining the data items of two different sorted list into a
single sorted list.

Splitting: Splitting is a process of partitioning single list to multiple list.

20 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
Arrays
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.

21 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
Characteristics of arrays:
 An array holds elements that have the same data type.
 Array elements are stored in subsequent memory locations.
 Two-dimensional array elements are stored row by row in
subsequent memory locations.
 Array name represents the address of the starting element.
 Array size should be mentioned in the declaration. Array size must be a constant
expression and not a variable.
Advantages of Arrays

 Arrays represent multiple data items of the same type using a single name.
 In arrays, the elements can be accessed randomly by using the index number.
 Arrays allocate memory in contiguous memory locations for all its elements. Hence
there is no chance of extra memory being allocated in case of arrays. This
avoids memory overflow or shortage of memory in arrays.
 Using arrays, other data structures like linked lists, stacks, queues, trees, graphs etc
can be implemented.
 Two-dimensional arrays are used to represent matrices.

Disadvantages of Arrays

 The number of elements to be stored in an array should be known in advance.

 An array is a static structure (which means the array is of fixed size). Once declared the
size of the array cannot be modified. The memory which is allocated to it cannot be
increased or decreased.
 Insertion and deletion are quite difficult in an array as the elements are stored in
consecutive memory locations and the shifting operation is costly.
 Allocating more memory than the requirement leads to wastage of memory space and
less allocation of memory also leads to a problem.

Applications of Arrays

 Array stores data elements of the same data type.

 Maintains multiple variable names using a single name. Arrays help to maintain large
data under a single variable name. This avoid the confusion of using multiple variables.
 Arrays can be used for sorting data elements. Different sorting techniques like Bubble
sort, Insertion sort, Selection sort etc use arrays to store and sort elements easily.
 Arrays can be used for performing matrix operations. Many databases, small and large,
consist of one-dimensional and two-dimensional arrays whose elements are records.
 Arrays can be used for CPU scheduling.
 Lastly, arrays are also used to implement other data structures like Stacks, Queues,
Heaps, Hash tables etc.

22 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
One Dimensional array
 Simplest data structure that makes use of computed address to locate its
elements is the one- dimensional array or vector; number of memory locations is
sequentially allocated to the vector.
 A vector size is fixed and therefore requires a fixed number of memory locations.
 Vector A with subscript lower bound of “one” is represented as below….

Datatype arrayname[size];

Datatype : Vaild Primitive data type

Arrayname: Name of an array
Size : Maximum number of data in array

Example : int a[10];

In an array name “a”, during execution, the compiler allocates 10 consecutive memory
location.

Memory allocation of one dimensional array:

The first element of the array is stored at a free memory location says n. This is called base
address of the array. The next element is stored in the n+1 memory location and so on.

Each memory location can be accessed by using indexing or subscripting as a[0], a[1],…
a[n].The smallest value of the array index is called as Lower Bound (lb) and highest value of
the array index is called Upper Bound (ub).

Range=(upper bound-lowerbound +1)

Two Dimensional array:

An array consisting of two subscripts is known as two-dimensional array. These are often
known as array of the array. In two dimensional arrays the array is divided into rows and
columns. These are well suited to handle a table of data

data_type array_name[row_size][column_size];

Example: int arr[3][3];

where first index value shows the number of the rows and second index value shows the number
of the columns in the array.

23 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
 1. Row-Major order Implementation

2. Column-Major order Implementation

In Row-Major Implementation of the arrays, the arrays are stored in the memory in terms
of the row design, i.e. first the first row of the array is stored in the memory then second
and so on. Suppose we have an array named arr having 3 rows and 3 columns then it can
be stored in the memory in the following manner :

int arr[3][3];

arr[0][0] arr[0][1] arr[0][2]

arr[1][0] arr[1][1] arr[1][2]

arr[2][0] arr[2][1] arr[2][2]

1 2 3 4 5 6 7 8 9

In Column-Major Implementationof the arrays, the arrays are stored in the memory in
the term of the column design, i.e. the first column of the array is stored in the memory
then the second and so on.

1 4 7 2 5 8 3 6 9

Multidimensional arrays are often known as array of the arrays. In multidimensional

arrays the array is divided into rows and columns, mainly while considering
multidimensional arrays we will be discussing mainly about two dimensional arrays and
a bit about three dimensional arrays.

data_type array_name[size1][size2][size3]------[sizeN];

24 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
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.
 We often speak of "extra" memory needed, not counting the memory needed to store
the input itself. Again, we use natural (but fixed-length) units to measure this.
 We can use bytes, but it's easier to use, say, number of integers used, number of fixed-
sized structures, etc. In the end, the function we come up with will be independent
of the actual number of bytes needed to represent the unit.
 Space complexity is sometimes ignored because the space used is minimal
and/or obvious, but sometimes it becomes as important an issue as time.
Worst Case Analysis
In the worst case analysis, we calculate upper bound on running time of an algorithm. We
must know the case that causes maximum number of operations to be executed. For Linear
Search, the worst case happens when the element to be searched is not present in the array.

25 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.
When x is not present, the search () functions compares it with all the elements of array []
one by one. Therefore, the worst case time complexity of linear search would be.

Average Case Analysis

In average case analysis, we take all possible inputs and calculate computing time for all of
the inputs. Sum all the calculated values and divide the sum by total number of inputs. We
must know (or predict) distribution of cases. For the linear search problem, let us assume
that all cases are uniformly distributed. So we sum all the cases and divide the sum by
(n+1).

Best Case Analysis

In the best case analysis, we calculate lower bound on running time of an algorithm. We
must know the case that causes minimum number of operations to be executed. In the linear
search problem, the best case occurs when x is present at the first location. The number of
operations in worst case is constant (not dependent on n). So time complexity in the best
case would be.

26 | P a g e
BASIC DATA STRUCTURES, [Link] SHANKARI, ANNA UNIVERSITY.