1

DATA STRUCTURES AND OBJECT ORIENTED PROGRAMMING

1. Introduction
1.1. What is an algorithm ?
Informal Definition:
An Algorithm is any well-defined computational procedure that takes some
value or set of values as Input and produces a set of values or some value as output. Thus
algorithm is a sequence of computational steps that transforms the i/p into the o/p.

Formal Definition:
An Algorithm is a finite set of instructions that, if followed, accomplishes a
particular task. In addition, all algorithms should satisfy the following criteria.

1. INPUT  Zero or more quantities are externally supplied.

2. OUTPUT  At least one quantity is produced.
3. DEFINITENESS  Each instruction is clear and unambiguous.
4. FINITENESS  If we trace out the instructions of an algorithm, then for all cases,
the algorithm terminates after a finite number of steps.
5. EFFECTIVENESS  Every instruction must very basic so that it can be carried out,
in principle, by a person using only pencil & paper.

Issues or study of Algorithm:

 How to device or design an algorithm  creating and algorithm.

 How to express an algorithm  definiteness.
 How to analysis an algorithm  time and space complexity.
 How to validate an algorithm  fitness.
 Testing the algorithm  checking for error.

1.2. Algorithm Specification:

Algorithm can be described in three ways.

1. Natural language like English:

When this way is choused care should be taken, we should ensure that each &
every statement are definite.

2. Graphic representation called flowchart:

This method will work well when the algorithm is small& simple.

3. Pseudo-code Method:
In this method, we should typically describe algorithms as program, which
resembles language like Pascal & algol.

Unit I
1
 2

SPARKS – A language to specify the algorithm in Pseudo-code method :

Structured Programming: A Reasonably Komplete Set
or
Smart Programmers Are Required To Know SPARKS.
SPARKS contains facilities to manipulate numbers, boolean values and
characters.
1.2.1. Pseudo-Code Conventions:

1. Comments begin with // and continue until the end of line.

2. Blocks are indicated with matching braces {and}.

3. An identifier begins with a letter. The data types of variables are not explicitly
declared.

4. Compound data types can be formed with records. Here is an example,

Node. Record
{
data type – 1 data-1;
.
.
.
data type – n data – n;
node * link;
}

Here link is a pointer to the record type node. Individual data items of a record
can be accessed with  and period.

5. Assignment of values to variables is done using the assignment statement.

<Variable>:= <expression>;

6. There are two Boolean values TRUE and FALSE.

 Logical Operators AND, OR, NOT

Relational Operators <, <=,>,>=, =,!=

7. The following looping statements are employed.

For, while and repeat-until

While Loop:
While < condition > do
{
<statement-1>

Unit I
2
 3

.
.
.

<statement-n>
}

For Loop:
For variable: = value-1 to value-2 step step do

{
<statement-1>
.
.
.
<statement-n>
}
repeat-until:

repeat
<statement-1>
.
.
.
<statement-n>
until<condition>

8. A conditional statement has the following forms.

 If <condition> then <statement>

 If <condition> then <statement-1>
Else <statement-1>

Case statement:

Case
{
: <condition-1> : <statement-1>
.
.
.
: <condition-n> : <statement-n>
: else : <statement-n+1>
}

9. Input and output are done using the instructions read & write.

Unit I
3
 4

10. There is only one type of procedure:

Algorithm, the heading takes the form,

Algorithm Name (Parameter lists)

 As an example, the following algorithm fields & returns the maximum of ‗n‘ given
numbers:
Example 1.
1. algorithm Max(A,n)
2. // A is an array of size n
3. {
4. Result := A[1];
5. for I:= 2 to n do
6. if A[I] > Result then
7. Result :=A[I];
8. return Result;
9. }

In this algorithm (named Max), A & n are procedure parameters. Result & I are Local
variables.

1.3 HOW TO ANALYZE PROGRAMS

Introduction
The analysis of an algorithm provides background information that gives us a
general idea of how long an algorithm will take for a given problem set. For
each algorithm considered, we will come up with an estimate of how long it
will take to solve a problem that has a set of N input values. So, for example,
we might determine how many comparisons a sorting algorithm does to put a
list of N values into ascending order, or we might determine how many arith-
metic operations it takes to multiply two matrices of size N × N.

There are many algorithms that can solve a given problem. They will have
different characteristics that will determine how efficiently each will operate.
One goal is to develop skills for making evaluative judgements about programs.
There are many criteria upon which we can judge a program, for instance:
(i) Does it do what we want it to do?
(ii) Does it work correctly according to the original specifications of the task?
(iii) Is there documentation which describes how to use it and how it works?
(iv) Are subroutines created in such a way that they perform logical sub-
functions?
(v) Is the code readable?

Unit I
4
 5

The above criteria are all vitally important when it comes to writing software,
most especially for large systems.
There are other criteria for judging programs which have a more direct
relationship to performance.
These have to do with computing time and storage requirements of the
algorithms. Performance evaluation can be loosely divided into 2 major phases:
(a) a priori estimates and (b) a posteriori testing.
Both of these are equally important.
First consider a priori estimation. Suppose that somewhere in one of your
programs is the statement
x= x + 1.
We would like to determine two numbers for this statement. The first is the
amount of time a single execution will take; the second is the number of times it
is executed. The product of these numbers will be the total time taken by this
statement. The second statistic is called the frequency count, and this may vary
from data set to data set. One of the hardest tasks in estimating frequency
counts is to choose adequate samples of data. It is impossible to determine
exactly how much time it takes to execute any command unless we have the
following information:
(i) the machine we are executing on:
(ii) its machine language instruction set;
(iii) the time required by each machine instruction;
(iv) the translation a compiler will make from the source to the machine
language.
It is possible to determine these figures by choosing a real machine and an
existing compiler. Another approach would be to define a hypothetical machine
(with imaginary execution times), but make the times reasonably close to those
of existing hardware so that resulting figures would be representative.
Neither of these alternatives seems attractive. In both cases the exact times we
would determine would not apply to many machines or to any machine. Also,
there would be the problem of the compiler, which could vary from machine to
machine. Moreover, it is often difficult to get reliable timing figures because
of clock limitations and a multi-programming or time sharing environment.
Finally, the difficulty of learning another machine language outweighs the
advantage of finding "exact" fictitious times. All these considerations lead us to
follow a priori analysis.
1.3.1. Performance Analysis:
Performance evaluation can be loosely divided into two major phases : 1.
A priori estimates and a2. A posteriori testing We refer to these as performance analysis and
performance measurement respectively.

Unit I
5
 6

1. Space Complexity:
The space complexity of an algorithm is the amount of money it needs to
run to compilation.

2. Time Complexity:
The time complexity of an algorithm is the amount of computer time it
needs to run to compilation.

Space Complexity:

Space Complexity Example:

Algorithm abc(a,b,c)
{
return a+b++*c+(a+b-c)/(a+b) +4.0;
}

 The Space needed by each of these algorithms is seen to be the sum of the following
component.

1.A fixed part that is independent of the characteristics (eg:number, size)of the inputs and
outputs.
This part typically includes the instruction space (ie. Space for the code), space for
simple variable and fixed-size component variables (also called aggregate) space for
constants, and so on.

2. A variable part that consists of the space needed by component variables whose size is
dependent on the particular problem instance being solved, the space needed by
referenced variables (to the extent that is depends on instance characteristics), and the
recursion stack space.

 The space requirement S(P) of any algorithm p may therefore be written as,
S(P) = c+ Sp(Instance characteristics)
Where ‗c‘ is a constant.

Example 2:

Algorithm sum(a,n)
{
s=0.0;
for I=1 to n do
s= s+a[I];
return s;
}

Unit I
6
 7

 The problem instances for this algorithm are characterized by n, the

number of elements to be summed. The space needed d by ‗n‘ is one word,
since it is of type integer.
 The space needed by ‗a‘a is the space needed by variables of tyepe array
of floating point numbers.
 This is atleast ‗n‘ words, since ‗a‘ must be large enough to hold the ‗n‘
elements to be summed.
 So,we obtain sum(n)>=(n+3)
[ n for a[],one each for n, i, a & s]
Time Complexity:
The time T(P) taken by a program P is the sum of the compile time and the run time.
The compile time does not depend on the instance characteristics.
Also, we may assume that a compiled program will be run several times without
recompilation.
Consequently, we concern ourselves with just the run time of a program. This run
time is denoted by tp ( instance characteristics).
tp (n) = ca ADD(n) + cs SUB(n) + cm MUL(n) + cd DIV(n) +……..
When n denotes the instance characteristics and ca, cs, cm, cd and so on, respectively
denote the time needed for an addition, subtraction, multiplication, division, and so on, and
ADD, SUB, MUL, DIV are functions whose values are numbers of additions, subtractions,
multiplication, divisions, and so on that are performed when the code for P is used on an
instance with characteristic n.
The value of tp (n) for any given n can be obtained only experimentally. The program
is typed, compiled and run on a particular machine. The execution time is physically
clocked, and tp (n) obtained.
The number of steps any program statement is assigned depends on the kind of
statement. For example,
1. For example, comments  0 steps.
2. Assignment statements  1 steps.
[Which does not involve any calls to other algorithms]
3. An iterative statement such as for, while and repeat-until statements, we
consider the step counts only for the control part of the statement. The control part for ―for
and while‖ statements have the following forms:
for i := (expr) to (expr1) do
while ((expr)) do
Each execution of the control part of a while statement is given a step count equal to
the number of step counts assignable to (expr).
The step count for each execution of the control part of a for statement is one, unless
the counts attributable to (expr) and (expr1) are functions of the instance characteristics.
In this later case, the first execution of the control part of the for has a step count
equal to the of the counts for (expr) and (expr1). Ie for ( I = 1 to n ) means loop repeated
n+1 times. Remaining executions of the for statement have a step count of one; and so on.
Determination of number of steps needed by a program :

A method to determine the step count of an algorithm is to build a Step table in which we list
the total number of steps contributed by each statement.

Unit I
7
 8

First determine the number of steps per execution (s/e) of the statement and the
total number of times (ie., frequency) each statement is executed.
By combining these two quantities, the total contribution of all statements, the
step count for the entire algorithm is obtained.

Step Table for algorithm :

Statement S/e Frequen Total
cy
1. Algorithm Sum(a,n) 0 - 0
2.{ 0 - 0
3. S=0.0; 1 1 1
4. for I=1 to n do 1 n+1 n+1
5. s=s+a[I]; 1 n n
6. return s; 1 1 1
7. } 0 - 0

Total 2n+3

The Time complexity of an algorithm is given by the number of steps taken by the algorithm
to compute the function( task) it was written for . Determining the exact step count (best
case, worst case or average) of an algorithm can prove to be an exceedingly difficult task.
For most situations , it is adequate to be able to make a statement t(n,m) = c1 n+c2m where
c1 and c2 are non negative constants.

 If we have two algorithms with the complexity of c1n2 + c2n and c3n
respectively, then we know that the one with complexity c3n will be faster than the
one with complexity c1n2 + c2n
 The time complexity of the above algorithm = O(n) as we follow the
Simple Rule: Drop lower order terms and constant factors
for 2n+3, we drop the constants 2 and 3.

5 ms worst-case
4 ms

3 ms
}average-case?
best-case
2 ms

1 ms

A B C D E F G
Input

Unit I
8
 9

Fig 1.1

Graphic Illustration
f(n) = 2n +6

f(n) = 2n+6
Conf. def:
Need to find a c g(n) = 4n
function g(n) and
a const. c such as
f(n) < cg(n)
g(n) = n and c = 4
 f(n) is O(n)
g(n) = n
The order of f(n)
is n
n

Fig 1.2
Analysis

Best Case
As its name indicates, the best case for an algorithm is the input that requires
the algorithm to take the shortest time. This input is the combination of values
that causes the algorithm to do the least amount of work. If we are looking at a
searching algorithm, the best case would be if the value we are searching for
(commonly called the target or key) was the value stored in the first location
that the search algorithm would check. This would then require only one
comparison no matter how complex the algorithm is. Notice that for searching
through a list of values, no matter how large, the best case will result in a
constant time of 1. Because the best case for an algorithm will usually be a
very small and frequently constant value, we will not do a best-case analysis
very frequently.
Worst Case
Worst case is an important analysis because it gives us an idea of the most time
an algorithm will ever take. Worst-case analysis requires that we identify the
input values that cause an algorithm to do the most work. For searching algo-
rithms, the worst case is one where the value is in the last place we check or is
not in the list. This could involve comparing the key to each list value for a
total of N comparisons. The worst case gives us an upper bound on how slowly
parts of our programs may work based on our algorithm choices.
Average Case

Unit I
9
 10

Average-case analysis is the toughest to do because there are a lot of details

involved. The basic process begins by determining the number of different
groups into which all possible input sets can be divided. The second step is to
determine the probability that the input will come from each of these groups.
The third step is to determine how long the algorithm will run for each of these
groups
Complexity:
Complexity refers to the rate at which the storage time grows as a function of the
problem size

Asymptotic analysis:
Expressing the complexity in term of its relationship to known function. This type
analysis is called asymptotic analysis.

1.4. Asymptotic Notation (Ω, O, Ө)

We introduce some terminology that enables us to make meaningful (but inexact)
statements about the time and space complexities of an algorithm.
Definition 1.4.1:
The Big “oh” notation describes an upper bound on the asymptotic growth of
the function f
[Big ―oh‖] The function f(n) = O(g(n)) (read as ―f of n is big oh of g of n‖) if and
only if there exist positive constants c and n0 such that f(n) ≤ c *g(n) for all n, n ≥ n0 .
Definition 1.4.2:
[Omega] The function f(n) = Ω(g(n)) (read as ―f of n is omega of g of n‖) if and only
if there exist positive constants c and n0 such that f(n) ≥ c*g(n) for all n, n ≥ n0 .
Definition 1.4.3:
[Theta] The function f(n) = Ө(g(n)) (read as ―f of n is theta of g of n‖) if and only if
there exist positive constants c1, c2 and n0 such that c1 g(n) ≤ f(n) ≤ c2g(n) for all n, n ≥ n0 .
Definition 1.4.4:
[Little ―oh‖] The function f(n) = o(g(n)) (read ad ―f of n is little oh of g of n‖) if and
only if f(n) = O(g(n)) and f(n) <> Ω(g(n))

Definition 1.4.5:
[Little omega] The function f(n) = ω(g(n)) (read as ―f of n is little omega of g of n‖) if
and only if f(n) = Ω(g(n)) and f(n)<> O(g(n))

Properties of Big-Oh

Unit I
10
 11

If f(n) is O(g(n)) then af(n) is O(g(n)) for any a.

If f(n) is O(g(n)) and h(n) is O(g‘(n)) then f(n)+h(n) is O(g(n)+g‘(n))
If f(n) is O(g(n)) and h(n) is O(g‘(n)) then f(n)h(n) is O(g(n)g‘(n))
If f(n) is O(g(n)) and g(n) is O(h(n)) then f(n) is O(h(n))
If f(n) is a polynomial of degree d , then f(n) is O(nd)
nx = O(an), for any fixed x > 0 and a > 1
An algorithm of order n to a certain power is better than an algorithm of order
a ( > 1) to the power of n
x
log n is O(log n), fox x > 0 – how?
log x n is O(ny) for x > 0 and y > 0
An algorithm of order log n (to a certain power) is better than an algorithm of
n raised to a power y.

Function Values :
log n n n log n n2 n3 2n
0 1 0 1 1 2
1 2 2 4 8 4
2 4 8 16 64 16
3 8 24 64 512 256
4 16 64 256 4096 65536
5 32 160 1024 32768 4294967296

Fig 1.3.

O(1) – Computing time is constant

O(n) – Linear
O(n2) – Quadratic
O(n3) – Cubic
O(2n) – Exponential
The order is
O(1)<O(log n)<O(n)<O(nlogn)< O(n2)< O(n3)< O(2n)

Another eg for analysis :

1 procedure FIBONACCI
2 read (n)
3-4 if n < 0 then [print ('error'); stop]
5-6 if n = 0 then [print ('0'); stop]
7-8 if n = 1 then [print ('1'); stop]
9 fnm2 0; fnm 1 1
10 for i 2 to n do
11 fn fnm1 + fnm2
12 fnm2 fnm1

Unit I
11
 12

13 fnm1 fn
14 end
15 print (fn)
16 end FIBONACCI
The first problem in beginning an analysis is to determine some reasonable
values of n. A complete set
would include four cases: n < 0, n = 0, n = 1 and n > 1. Below is a table which
summarizes the
frequency counts for the first three cases.
Step n < 0 n = 0 n = 1
--------------------------
1 1 1 1
2 1 1 1
3 1 1 1

8 0 16 1
Execution Count for Computing Fn
Each statement is counted once, so step 9 has 2 statements and is executed once
for a total of 2. Clearly, the actual time taken by each statement will vary. The
for statement is really a combination of several statements, but we will count it
as one. The total count then is 5n + 5. We will often write this as O(n),
ignoring the two constants 5. This notation means that the order of magnitude is
proportional to n.
When we say that the computing time of an algorithm is O(g(n)) we mean that
its execution takes no more than a constant times g(n). n is a parameter which
characterizes the inputs and/or outputs. For example n might be the number of
inputs or the number of outputs or their sum or the magnitude of one of them.
For the Fibonacci program n represents the magnitude of the input and the time
for this program is written as T(FIBONACCI) = O(n).

INTRODUCTION TO PROBLEM SOLVING

- Problem solving is a process of transforming the description of a problem into the

solution of that problem by using our knowledge of the problem domain and by relying
on our ability to select and use appropriate problem-solving Strategies, Techniques and
Tools.

- Problem solving (with in the context of developing programs) refers to analyzing a

problem with the intention of deriving a solution for the problem.

Unit I
12
 13

- Using computer‘s in problem solving.

- Software development method (SDM).

Consists of the following steps:

 Requirements specifications (Specification of needs).

 Problem analysis.
 Design the algorithm to solve the problem.
 Implementation.
 Testing and verification.
 Documentation.

 Requirements Specifications:

- State the problem clearly and unambiguously (Doubtless) to understand exactly:

 What the problem is?

 What is needed to solve it?
 What the solution should provide
 If there are constraints and special conditions.

 Problem Analysis:

In the analysis phase, we should identity the following:

 Inputs: To the problem, their form and the input media to be used.

 Outputs: Expected from the problem, their form and the output media to be used.

Unit I
13
 14

 Special constraints or (necessity) conditions (if any).

 Formulas or equations to be used.

Example:

Problem: Compute and display the total cost of apples given the number of kilograms
(kg) of apples purchased and the cost per kg of apples.

 Input: Quantity of Apples purchased (in kg).

 Cost per kg of Apples (in Rs. per kg).

 Output: Total cost of Apples (in Rs.).

 Constraint: N/A

 Formula: Total cost = Cost per kg x Quantity.

 Design the algorithm to solve the problem.

Purpose: To develop and verify algorithm.

- An algorithm is a list of steps to be executed with the right order in which these steps
should be executed.

- An algorithm must satisfy these requirements:

 It must have and Input.

 It must have an Output.
 It must not be ambiguous (there should not be different interpretations to it).
 It must be general (it can be used for different Inputs).

Unit I
14
 15

 Writing the algorithm is a difficult task  use top-down design (Divide and
Conquer approach).

 Top-Down design

1. List the major steps (most algorithm consists of at least the following):

 Get the data.

 Perform the computations.
 Display the result.

2. Perform algorithm refinement the step(s) may need to be broken down into a
more detailed list of steps.

3. Verify that the algorithm works as intended – perform desk check.

- It must be correct and it must solve the problem for which it is designed.

- It must execute and terminate in a finite amount of time.

- It must be efficient enough so that it can solve the intended problem using the resource
currently available on the computer.

 An algorithm can be represented using Pseudo codes (or) Flow charts.

- Specifying the order in which the steps are to be executed is important.

Example:

Algorithm for getting out of bed and prepare to go to work.

Unit I
15
 16

- Get out of Bed.

- Take Shower.
- Get Dressed.

 If a same steps are performed in a slightly different order, that is :

- Get out of Bed.

- Get Dressed.
- Take Shower.
What would be the result?

WHAT IS DATA STRUCTURE?

―The way information is organized in the memory of a computer is called a data

structure”.
(OR)

A data structure is a way of organizing data that considers not only the items stored, but also
their relationship to each other. Advance knowledge about the relationship between data
items allows designing of efficient algorithms for the manipulation of data.

Definition of data structures

Data structure deals with structure/ representation of data. It is a triple (D,A,F) consists of
:
(1) Domain D= set of elements for data manipulation or processing
(2) Axioms A = set of statements which have value either True or False
(3) Functions F= Set of operations performed on the set D
Eg
structure NATNO
1 declare ZERO( ) natno
2 ISZERO(natno) boolean
3 SUCC(natno) natno
4 ADD(natno, natno) natno
5 EQ(natno, natno) boolean
6 for all x, y natno let
7 ISZERO(ZERO) ::= true; ISZERO(SUCC(x)) ::= false

Unit I
16
 17

Here D= {1,2,3,4 ….}

F = set of operations like ADD(), ISZERO(), SUCC()
etc.
Addition of two natural number is a natural number.
The statement ADD(natno, natno) natno is having a
TRUE value

Why do we need data structures?

• Data structures allow us to achieve an important goal: component reuse

• Once each data structure has been implemented once, it can be used over and over
again in various applications.

Common data structures are

• Stacks • Queues • Lists
• Trees • Graphs • Tables

Classification of data Structure:

Based on how the data items or operated it will classified into

1. Primitive Data Stucture : is one the data items are operated closest to the
machine level instruction.
Eg : int, char and double.
2. Non-Primitive Data Structure : is one that data items are not operated
closest to machine level instruction.

2.1. Linear Data Structure : In which the data items are stored in sequence order.
Eg: Arrays, Lists, Stacks and Queues.

2.2. Non Linear Data Structure : In which the order of data items is not
presence.

Eg : Trees, Graphs.

Unit I
17
 18

Linear Data Structure

1. List Non-Linear Data Structures
a. Array 1. Graph
i. One Dimensional a. Adjacency List
ii. Multi-Dimensional b. Adjacency Matrix
iii. Dynamic Array c. Spanning Tree
iv. Matrix 2. Tree
1. Sparse Matrix a. M-Way Tree
b. Linked List i. B-Tree
i. Single Linked List 1. 2-3-4 Tree
ii. Double Linked List 2. B+ Tree
iii. Circular Linked List b. Binary Tree
c. Ordered List i. Binary Search
i. Stack Tree
ii. Queue ii. Self-Balancing
1. Circular Queue Binary Search
2. Priority Queue Tree
iii. Deque 1. AVL Tree
2. Dictionary (Associative Array) 2. Red-Black
a. Hash Table Tree
3. Splay Tree
iii. Heap
1. Min Heap
2. Max Heap
3. Binary
Heap
iv. Parse Tree

Unit I
18
 19

Operations performed on any linear structure:

1. Traversal – Processing each element in the list

2. Search – Finding the location of the element with a given value.
3. Insertion – Adding a new element to the list.
4. Deletion – Removing an element from the list.
5. Sorting – Arranging the elements in some type of order.
6. Merging – Combining two lists into a single list.

An example of several common data s Characteristics of Data Structures

Data
Advantages Disadvantages
Structure
Array Quick inserts Slow search
Fast access if index known Slow deletes
Fixed size
Ordered Faster search than unsorted array Slow inserts
Array Slow deletes
Fixed size

Unit I
19
 20

Stack Last-in, first-out acces Slow access to other items

Queue First-in, first-out access Slow access to other items
Linked List Quick inserts Slow search
Quick deletes
Binary Tree Quick search Deletion algorithm is complex
Quick inserts
Quick deletes
(If the tree remains balanced)
Red-Black Quick search Complex to implement
Tree Quick inserts
Quick deletes
(Tree always remains balanced)
2-3-4 Tree Quick search Complex to implement
Quick inserts
Quick deletes
(Tree always remains balanced)
(Similar trees good for disk storage)
Hash Table Very fast access if key is known Slow deletes
Quick inserts Access slow if key is not known
Inefficient memory usage
Heap Quick inserts Slow access to other items
Quick deletes
Access to largest item
Graph Best models real-world situations Some algorithms are slow and very
complex

Abstract Data Types

Abstract data type (ADT) is a specification of a set of data and the set of operations that can
be performed on the data.

Examples

 Associative array
 Set
 Stack
 Queue

Unit I
20
 21

 Tree

Uses of ADT: -

1. It helps to efficiently develop well designed program

2. Facilitates the decomposition of the complex task of developing a software system
into a number of simpler subtasks
3. Helps to reduce the number of things the programmer has to keep in mind at any time
4. Breaking down a complex task into a number of earlier subtasks also simplifies
testing and debugging

Linear Data Structures

A data structure is said to be linear if its elements form a sequence or a linear list.

Examples:
Arrays
Linked Lists
Stacks, Queues

Arrays
Arrays
 The very common linear structure is array. Since arrays are usually easy to
traverse, search and sort, they are frequently used to store relatively
permanent collections of data.
 An array is a list of a finite number n of homogeneous data elements (i.e., data
elements of the same type) such that:
a) The elements of the array are referenced respectively by an index
consisting of n consecutive numbers.
b) The elements of the array are stored respectively in successive
memory locations.

Opearations of Array

 Two basic operations in an array are storing and retrieving (extraction)

Storing: A value is stored in an element of the array with the statement of the form,

Data[i] = X ; Where I is the valid index in the array

And X is the element

Unit I
21
 22

Extraction : Refers to getting the value of an element stored in an array.

X = Data [ i ], Where I is the valid index of the array and X is the

element.

Array Representation
 The number n of elements is called the length or size of the array. If not
explicitly stated we will assume that the index starts from 0 and end with n-1.
 In general, the length (range) or the number of data elements of the array can
be obtained from the index by the formula,
Length = UB – LB + 1
 Where UB is the largest index, called the Upper Bound, and LB is the smallest
index, called Lower Bound, of the array.
 If LB = 0 and UB = 4 then the length is,
Length = 4 – 0 + 1 = 5
 The elements of an array A may be denoted by the subscript notation (or
bracket notation),
A[0], A[1], A[2], … , A[N]
 The number K in A[K] is called a subscript or an index and A[K] is called a
subscripted variable.
 Subscripts allow any element of A to be referenced by its relative position in
A.
 If each element in the array is referenced by a single subscript, it is called
single dimensional array.
 In other words, the number of subscripts gives the dimension of that array.

Two-dimensional Arrays
 A two-dimensional mXn array A is a collection of m*n data elements such
that each element is specified by a pair of integers (such as I, J), called
subscripts, with the property that,
0≤Im and 0 ≤ J  n
 The element of A with first subscript i and second subscript j will be denoted
by,
A[i,j] or A[i][j] (c language)
 Two-dimensional arrays are called matrices in mathematics and tables in
business applications; hence two-dimensional arrays are sometimes are called
matrix arrays.
 There is a standard way of drawing a two-dimensional mXn array A where
the elements of A form a rectangular array with m rows and n columns and
where the element A[i][j] appears in row i and column j.

Unit I
22
 23

 A row is a horizontal list of elements, and a column is a vertical list of

elements.
Example:
Columns

0 1 2

0 A[0][0] A[0][1] A[0][2]

Rows 1 A[1][0] A[1][1] A[1][2]

2 A[2][0] A[2][1] A[2][2]

 The two-dimensional array will be represented in memory by a block of m*n

sequential memory locations.
 Specifically, the programming languages will store the array either
1. Column by column, i.e. column-major order, or
2. Row by row, i.e. row-major order.
Abstract Data Types (ADT)
 The ADT consists of a set of definitions that allow programmers to use the
functions while hiding the implementation. This generalization of operations
with unspecified implementations is known as abstraction.
 An ADT is a data declaration packaged together with the operations that are
meaningful on the data type.
1. Declaration of Data
2. Declaration of Operations

A normal variable: An Array variable:

An array is a collection of memory locations
which allows storing homogeneous int b; int a[4];
elements. It is an example for linear data
structure. b
An array lets you declare and work with a
collection of values of the same type
6 a[0]

(homogeneous). For example, you might want a[1]

You place a value

6
to create a collection of five integers. One
into “b” with the a[2]
way to do it would be to declare five integers
statement
directly:
int a, b, c, d, e; b=6; a[3]

You place a value

into “a” with the
statement like:
Unit I
23 a[2]=6;
array index
 24

Suppose you need to fined average of 100 numbers. What will you do? You have to declare
100 variables. For example:
int a, b, c, d, e, f, g, h, i, j, k, l, m, n... etc.,
An easier way is to declare an array of 100 integers:
int a[100];

The General Syntax is:

datatype array_name [size];

Example: Subscript
int a[5];
The five separate integers inside this array are accessed by an index. All arrays start at index
zero and go to n-1 in C. Thus, int a[5]; contains five elements. For example:
a[0] = 12;
a[1] = 9;
a[2] = 14;
a[3] = 5;
a[4] = 1;

Note: The array name will hold the address of the first element. It is called as BASE
ADDRESS of that array. The base address can’t be modified during execution, because it
is static. It means that the increment /decrement operation would not work on the base
address.
Consider the first element is stored in the address of 1020. It will look like this,

1020 1022 1024 1026 1028

a 12 9 14 5 1
0 1 2 3 4 .

a[0] means a + 0  1020 + 0  1020 (locates the 1020)

a[1] means a + 1  1020 + 1 * size of datatype  1020 + 2  1022 [ for ‗int‘ size is 2
byte]
a[2] means a + 2  1020 + 2 * size of datatype  1020 + 4  1024
a[3] means a + 3  1020 + 3 * size of datatype  1020 + 6  1026
a[4] means a + 4  1020 + 4 * size of datatype  1020 + 8  1028
Array indexing helps to manipulate the index using a for loop. Because of that retrieval of
element from an array is very easy. For example, the following code initializes all of the
values in the array to 0:

int a[5]; /* Array declaration */

int i;

/* Initializing Array Elements to 0

*/
for (i=0; i<5; i++)
a[i] = 0;

/* print array */

Unit I
24
 25

printf("Elements in the array

are…\n");
for (i=0; i < 5; i++)
printf("%d\n",a[i]);

Note : (mathematics) A matrix most of whose entries are zeros.

Advantages:
 Reduces memory access time, because all the elements are stored sequentially. By
incrementing the index, it is possible to access all the elements in an array.
 Reduces no. of variables in a program.
 Easy to use for the programmers.
Disadvantages:
 Wastage of memory space is possible. For example: Storing only 10 elements in a
100 size array. Here, remaining 90 elements space is waste because these spaces
can’t be used by other programs till this program completes its execution.
 Storing heterogeneous elements are not possible.
 Array bound checking is not available in ‗C‘. So, manually we have to do that.

Note : Memory representation of 1, 2 and multidimentional array refer class

notes:

STRUCTURES

1. Definition:

struct : Declares a structure, an object consisting of multiple data items that may be of
different types.

2. DEFINING A STRUCTURE:

Syntax: optional
struct tag
{
data-type member 1;
Don‘t forget the
Semicolon here
data-type member 2;
…………
data-type member m;
};

Here, struct is the required keyword; tag (optional) is a name that identifies structures of this
type; and member1, meber2, …, member m are individual member declarations.

Unit I
25
 26

 The individual members can be ordinary variables, pointers, arrays, or other

structures.
 A storage class cannot be assigned to an individual member, and individual members
can not be initialized within a structure type declaration.

3. DECLARING STRUCTURE VARIABLES:

Once the composition of the structure has been defined, individual structure-type
variables can be declared as follows:

storage-class struct tag variable1, varibale2, …, variable n;

where storage-class is an optional storage class specifier, struct is a required keyword,

tag is the name that appeared in the structure declaration and variable1, variable2, …,
variable n are structure variables of type tag.

Example:
struct student
{
int regno;
char name[20];
char dept[10];
int year;
};
Here, regno, name, dept and year are the members of the student structure. And this is the
definition of the datatype. So, no memory will be allocated at this stage. The memory will be
allocated after the declaration only. Structure variables can be declared as following
methods:

a) Normal way of declaration

struct student s1, s2;
b) It is possible to combine the declaration of the structure composition with that of the
structure variables, as shown below:

struct student
{
int regno;
char name[20];
char dept[10];
int year;
} s1, s2;
c) If we are going to declare all the necessary structure variables at definition time then we
can create them without the tag, as shown below:
struct
{
int regno;
char name[20];

Unit I
26
 27

char dept[10];
int year;
} s1, s2;
Since there is no tag name, additional variables can not be generated other than this location.
i.e. can‘t create new variables with this structure in the local functions. If we want we have to
redefine the structure variable once again.
d) If we use the typedef in front of the struct keyword then the tag name alone can be used in
other places whenever you want to use the student data type.
typedef struct student
{
int regno;
char name[20];
char dept[10];
int year;
} ;student s1, s2; /* here the struct keyword is not needed because of typedef */
struct student
{ int regno;
char name[20];
char dept[10];
int year;
};

s1 s2 sN

The size of each of these variables is 34 bytes because the size of the student datatype is 34
bytes. And the memory will be allocated for each variable as follows:
34 bytes

2 bytes 20 bytes 10 bytes 2 bytes

Address 6100 6102 6122 6132

s1

regno name dept year

34 bytes

2 bytes 20 bytes 10 bytes 2 bytes

Address 1002 1004 1024 1034

s2

regno name dept year

Unit I
27
 28

4. INITIALIZING STRUCTURE VARIABLES:

The members of a structure variable can be assigned initial values in much the same
manner as the elements of an array. The initial values must appear in the order in which they
will be assigned to their corresponding structure members, enclosed in braces and separated
by commas.

The general form is,

storage-class struct tag variable = {value1, value2, …,value n};

A structure variable, like an array, can be initialized only if its storage class is either
external or static.

Example:
static struct student s1 = { 340, “Kumara Vel”, “CSE”, 3};
static struct student s2 = {533, “Sankari”, “CSE”, 4};

5. STORING VALUES INTO THE MEMBERS OF THE STRUCTURE VARIABLES:

a) Values may be stored by assignment operation.

s1.regno = 500;
strcpy(s1.name, “Surya”);
strcpy(s1.dept, “CSE”);
s1.year = 3;

b) also the scanf statement may be used to give values through the keyboard.
scanf(“%d”, &s1.regno);
scanf(“%s”, s1.name);
scanf(“%s”, s1.dept);
scanf(“%d”, &s1.year);

OR

scanf(“%d%s%s%d”, &s1.regno, s1.name, s1.dept, &s1.year);

6. ARRAYS IN THE STRUCTURE:

The derived data types like array can be included in the structure as a member.

Example:

Unit I
28
 29

struct student
{

int roll;
char name[20]; This is an int
int marks[5]; array. So each This is a char
location can be array but it is
int total; accessed only used as string.
float avg; with help of So no need to
address only. So worry about the
char result[5]; the subscripts individual
}stu; are needed location and their
addresses

In memory it would be stored as given below:

stu (size is 43 bytes)

name array (size – 20 bytes) mark array (size – 10 bytes) result (size – 5 bytes)

2190 2192 2212 2214 2216 2218 2220 2222 2224 2228

stu

roll name 0 1 2 3 4 total avg result

mark

To access this location we

need to use,
stu.mark[3]
7. NESTED STRUCTURES:
A structure variable may be defined as a member of another structure. In such
situations, the declaration of the embedded structure must appear before the declaration of
the outer structure.

Example:
struct date struct bill
{ {
int day; int cno;
int month; char name[20];
int year; float amt;
}; struct date
struct bill {
{ OR int day;
int cno; int month;
char name[20]; int year;
float amt; }billdate, paydate;
struct date billdate;
}b1, b2;

Unit I
29
 30

struct date paydate;

}b1, b2;
The second structure bill now contains another structure, date, as one of its members. The
structure may look like as follows:
b1 (size of the variable is 38 bytes)

billdate (size – 6 bytes) paydate (size – 6 bytes)

2190 2192 2212 2216 2218 2220 2222 2224 2226

b1

cno name amt day month year day month year

This can be This can be
accessed by b1.cno accessed by This can be
b1.billdate.day accessed by
b1.paydate.year

8. PROCESSING STRUCTURES:
Consider the following structure:

struct student
{
int regno;
char name[20];
char dept[10];
struct date
{
int day;
int month;
int year;
}bday;
int marks[5];
int year;
} s1;
The members of a structure are usually processed individually, as separate entities.
Therefore, we must be able to access the individual structure members. A structure member
can be accessed by writing
structure_variable.member
where variable refers to the name of a structure-type variable, and member refers to the name
of a member within the structure. The period (.) separates the variable name from the
member name. It is a member of the highest precedence group, and its associativity is left to
right.
Example:
s1.regno, s1.name, s1.dept, s1.year
A nested structure member can be accessed by writing
structure_variable.member.submember;

Unit I
30
 31

Example:
s1.bday.day, s1.bday.month, s1.bday.year

where member refers to the name of the member within the outer structure, and submember
refers to the name of the member within the embedded structure. similarly, if a structure is
an array, then an individual array element can be accessed by writing
structure-variable.member[expression];
Example:
s1.mark[0], s1.mark[1], s1.mark[2], s1.mark[3], s1.mark[4]

10. POINTERS TO STRUCTURES:

The address of a given structure variable can be obtained by using the & operator.
Pointers to structures, like all other pointer variables may be assigned addresses. The
following statements illustrate this concept.
Example:
struct student
{
int regno;
char name[20]; This is structure
char dept[10]; variable
int year;
}; This is structure
pointer variable
struct student stu, *sptr;
sptr = &stu;
34 bytes

2 bytes 20 bytes 10 bytes 2 bytes

This is Address 6100 6102 6122 6132

structure
pointer stu1
variable.
regno name dept year

1008
Address of the
Address of the pointer variable
sptr 6100 structure variable sptr.
stu1 To access this location
2 bytes using structure pointer
variable (sptr),
Access to members of the structure is shown below: sptr->dept
should be used

printf(“Student Registration Number : %d\n”, sptr->regno);

printf(“Student Name : %s\n”, sptr->name);
printf(“Department Name : %s\n”, sptr->dept);
printf(“Year of Study : %d\n”, sptr->year);

Unit I
31
 32

POINTERS

What Are Pointers?

A pointer is a variable that holds a memory address. This address is the location of
another object(typically another variable) in memory. For example, if one variable contains
the address of anothervariable, the first variable is said to point to the second.

Pointer Variables
If a variable is going to be a pointer, it must be declared as such. A pointer
declaration consists of a base type, an *, and the variable name. The general form for
declaring a pointer variable is

type *name;

where type is the base type of the pointer and may be any valid type. The name of the
pointer variable is specified by name.

The base type of the pointer defines the type of object to which the pointer will point.
Technically,any type of pointer can point anywhere in memory. However, all pointer
operations are done relative to the pointer's base type. For example, when you declare a

Unit I
32
 33

pointer to be of type int *, the compiler assumes that any address that it holds points to an
integer— whether it actually does or not. (That is, an int * pointer always ''thinks" that it
points to an int object, no matter what that piece of memory actually contains.) Therefore,
when you declare a pointer, you must make sure that its type is compatible with the type of
object to which you want to point.
The Pointer Operators
The pointer operators were discussed in Chapter 2. We will review them here. There
are two pointer operators: * and &. The & is a unary operator that returns the memory
address of its operand. (Remember, a unary operator only requires one operand.) For
example,
m = &count;
places into m the memory address of the variable count. This address is the computer's
internal location of the variable. It has nothing to do with the value of count . You can think
of & as returning "the address of." Therefore, the preceding assignment statement can be
verbalized as "m receives the address of count ."

To understand the above assignment better, assume that the variable count uses
memory location 2000 to store its value. Also assume that count has a value of 100. Then,
after the preceding assignment, m will have the value 2000.
The second pointer operator, *, is the complement of &. It is a unary operator that returns the
value located at the address that follows. For example, if m contains the memory address of
the variable count,
q = *m;
places the value of count into q. Thus, q will have the value 100 because 100 is stored at
location 2000, which is the memory address that was stored in m. You can think of * as "at
address." In this case, the preceding statement can be verbalized as "q receives the value at
address m."

Pointer Expressions

Unit I
33
 34

In general, expressions involving pointers conform to the same rules as other

expressions. This section examines a few special aspects of pointer expressions, such as
assignments, conversions, and arithmetic.

Pointer Assignments
You can use a pointer on the right-hand side of an assignment statement to assign its
value to another pointer. When both pointers are the same type, the situation is
straightforward. For example:

#include <stdio.h>
int main(void)
{
int x = 99;
int *p1, *p2;
p1 = &x;
p2 = p1;
/* print the value of x twice */
printf(''Values at p1 and p2: %d %
d\n", *p1, *p2);
/* print the address of x twice */
printf("Addresses pointed to by p1 and p2: %p %p", p1, p2);
return 0;
}

After the assignment sequence

p1 = &x;
p2 = p1;
p1 and p2 both point to x. Thus, both p1 and p2 refer to the same object. Sample output from
the program, which confirms this, is shown here.
Values at p1 and p2: 99 99
Addresses pointed to by p1 and p2: 0063FDF0 0063FDF0

Unit I
34
 35

Notice that the addresses are displayed by using the %p printf( ) format specifier, which
causes printf( ) to display an address in the format used by the host computer. It is also
possible to assign a pointer of one type to a pointer of another type. However, doing so
involves a pointer conversion, which is the subject of the next section.

Pointer Conversions
One type of pointer can be converted into another type of pointer. There are two
general categories of conversion: those that involve void * pointers, and those that don't.
Each is examined here.
In C, it is permissible to assign a void * pointer to any other type of pointer. It is also
permissible to assign any other type of pointer to a void * pointer. A void * pointer is called
a generic pointer. The void * pointer is used to specify a pointer whose base type is
unknown. The void * type allows a function to specify a parameter that is capable of
receiving any type of pointer argument without reporting a type mismatch. It is also used to
refer to raw memory (such as that returned by the malloc( ) function described later in this
chapter) when the semantics of that memory are not known. No explicit cast is required to
convert to or from a void * pointer. Except for void *, all other pointer conversions must be
performed by using an explicit cast. However, the conversion of one type of pointer into
another type may create undefined behavior. For example, consider the following program
that attempts to assign the value of x to y, through the pointer p. This program compiles
without error, but does not produce the desired result.

#include <stdio.h>
int main(void)
{
double x = 100.1, y;
int *p;
/* The next statement causes p (which is an
integer pointer) to point to a double. */
p = (int *) &x;

Unit I
35
 36

/* The next statement does not operate as expected. */

y = *p; /* attempt to assign y the value x through p */
/* The following statement won't output 100.1. */
printf(''The (incorrect) value of x is: %f", y);
return 0;
}
Notice that an explicit cast is used when assigning the address of x (which is implicitly a
double * pointer) to p, which is an int * pointer. While this cast is correct, it does not cause
the program to act as intended (at least not in most environments). To understand the
problem, assume 4-byte ints and 8-byte doubles. Because p is declared as an integer pointer,
only 4 bytes of information will be transferred to y by this assignment statement,
y = *p;
not the 8 bytes that make up a double. Thus, even though p is a valid pointer, the fact that it
points to a double does not change the fact that operations on it expect int values. Thus, the
use to which p is put is invalid. The preceding example reinforces the rule stated earlier:
Pointer operations are performed relative to the base type of the pointer. While it is
technically permissible for a pointer to point to some other type of object, the pointer will
still ''think" that it is pointing to an object of its base type. Thus, pointer operations are
governed by the type of the pointer, not the type of the object being pointed to.
One other pointer conversion is allowed: You can convert an integer into a pointer or
a pointer into an integer. However, you must use an explicit cast, and the result of such a
conversion is implementation defined and may result in undefined behavior. (A cast is not
needed when converting zero, which is the null pointer.)

Pointer Arithmetic
There are only two arithmetic operations that you can use on pointers: addition and
subtraction. To understand what occurs in pointer arithmetic, let p1 be an integer pointer with
a current value of 2000. Also, assume ints are 2 bytes long. After the expression
p1++;

Unit I
36
 37

p1 contains 2002, not 2001. The reason for this is that each time p1 is incremented, it will
point to the next integer. The same is true of decrements. For example, assuming that p1 has
the value 2000, the expression
p1--;
causes p1 to have the value 1998.
Generalizing from the preceding example, the following rules govern pointer
arithmetic. Each time a pointer is incremented, it points to the memory location of the next
element of its base type. Each time it is decremented, it points to the location of the previous
element. When applied to char pointers, this will appear as ''normal" arithmetic because a
char object is always 1 byte long no matter what the environment. All other pointers will
increase or decrease by the length of the data type they point to. This approach ensures that a
pointer is always pointing to an appropriate element of its base type. Figure below illustrates
this concept. You are not limited to the increment and decrement operators. For example, you
may add or subtract integers to or from pointers. The expression
p1 = p1 + 12;
makes p1 point to the 12th element of p1's type beyond the one it currently points to.
Besides addition and subtraction of a pointer and an integer, only one other arithmetic
operation is allowed: You can subtract one pointer from another in order to find the number
of objects of their base type that separate the two. All other arithmetic operations are
prohibited. Specifically, you cannot multiply or divide pointers; you cannot add two pointers;
you cannot apply the bitwise operators to them; and you cannot add or subtract type float or
double to or from pointers.

Unit I
37
 38

Pointer Comparisons
You can compare two pointers in a relational expression. For instance, given two
pointers p and q, the following statement is perfectly valid:

if(p < q) printf("p points to lower memory than q\n");

Generally, pointer comparisons are useful only when two pointers point to a common object,
such as an array. As an example, a set of stack functions are developed that store and retrieve
integer values. As most readers will know, a stack is a list that uses first-in, last-out
accessing. It is often compared to a stack of plates on a table— the first one set down is the
last one to be used. Stacks are used frequently in compilers, interpreters, spreadsheets, and
other system-related software. To create a stack, you need two functions: push( ) and pop( ).
The push( ) function places values on the stack, and pop( ) takes them off. These routines are
shown here with a simple main( ) function to drive them. The program puts the values you
enter into the stack. If you enter 0, a value is popped from the stack. To stop the program,
enter –1.
#include <stdio.h>
#include <stdlib.h>
#define SIZE 50
void push(int i);
int pop(void);

Unit I
38
 39

int *tos, *pl, stack[SIZE];

int main(void)
{
int value;
tos = stack; /* tos points to the top of stack */
p1 = stack; /* initialize p1 */
do {
printf(''Enter value: ");
scanf("%d", &value);
if(value != 0) push(value);
else printf("value on top is %d\n", pop());
} while(value != -1);
return 0;
}
void push(int i)
{
p1++;
if(p1 == (tos+SIZE)) {
printf(''Stack Overflow.\n");
exit(1);
}
*p1 = i;
}
int pop(void)
{
if(p1 == tos) {
printf("Stack Underflow. \n");
exit(1);
}
p1--;
return *(p1+1);

Unit I
39
 40

}
You can see that memory for the stack is provided by the array stack. The pointer p1 is set to
point to the first element in stack. The p1 variable accesses the stack. The variable tos holds
the memory address of the top of the stack. It is used to prevent stack overflows and
underflows. Once the stack has been initialized, push( ) and pop( ) can be used. Both the
push( ) and pop( ) functions perform a relational test on the pointer p1 to detect limit errors.
In push( ), p1 is tested against the end of the stack by adding SIZE (the size of the stack) to
tos. This prevents an overflow. In pop( ), p1 is checked against tos to be sure that a stack
underflow has not occurred. In pop( ), the parentheses are necessary in the return statement.
Without them, the statement would look like this,
return *p1+1;
which would return the value at location p1 plus one, not the value of the location p1+1.

Pointers and Arrays

There is a close relationship between pointers and arrays. Consider this program fragment:
char str[80], *p1;
p1 = str;
Here, p1 has been set to the address of the first array element in str. To access the fifth
element in str, you could write str[4] or *(p1+4)
Both statements will return the fifth element. Remember, arrays start at 0. To access the fifth
element, you must use 4 to index str. You also add 4 to the pointer p1 to access the fifth
element because p1 currently points to the first element of str. (Recall that an array name
without an index returns the starting address of the array, which is the address of the first
element.)
The preceding example can be generalized. In essence, C provides two methods of accessing
array elements: pointer arithmetic and array indexing. Although the standard array-indexing
notation is sometimes easier to understand, pointer arithmetic can be faster. Since speed is
often a consideration in programming, C programmers often use pointers to access array
elements.

Unit I
40
 41

These two versions of putstr( )— one with array indexing and one with pointers— illustrate
how you can use pointers in place of array indexing. The putstr( ) function writes a string to
the standard output device one character at a time.

/* Index s as an array. */
void putstr(char *s)
{
register int t;
for(t=0; s[t]; ++t) putchar(s[t]);
}
/* Access s as a pointer. */
void putstr(char *s)
{
while(*s) putchar(*s++);
}

Most professional C programmers would find the second version easier to read and
understand. Depending upon the compiler, it might also be more efficient. In fact, the pointer
version is the way routines of this sort are commonly written in C.

Arrays of Pointers
Pointers can be arrayed like any other data type. The declaration for an int pointer array of
size 10 is
int *x[10];
To assign the address of an integer variable called var to the third element of the pointer
array, write
x[2] = &var;
To find the value of var, write
*x[2]

Unit I
41
 42

If you want to pass an array of pointers into a function, you can use the same method that you
use to pass other arrays: Simply call the function with the array name without any subscripts.
For example, a function that can receive array x looks like this:
void display_array(int *q[])
{
int t;
for(t=0; t<10; t++)
printf(''%d ", *q[t]);
}
Remember, q is not a pointer to integers, but rather a pointer to an array of pointers to
integers.
Therefore you need to declare the parameter q as an array of integer pointers, as just shown.
You cannot declare q simply as an integer pointer because that is not what it is. Pointer
arrays are often used to hold pointers to strings. For example, you can create a function that
outputs an error message given its index, as shown here:
void syntax_error(int num)
{
static char *err[] = {
"Cannot Open File\n",
''Read Error\n",
"Write Error\n",
"Media Failure\n"
};
printf("%s", err[num]);
}
The array err holds a pointer to each error string. This works because a string constant used
in an expression (in this case, an initialization) produces a pointer to the string. The printf( )
function is called with a character pointer that points to the error message whose index is
passed to the function.
For example, if num is passed a 2, the message Write Error is displayed.

Unit I
42
 43

Sorting Techniques
SHELL SORT
1. The shell sort , named after its developer Donald.L.shell in 1959
2. This sort is an extension of the insertion sort, which has the limitation, that it compares only
the consecutive elements and interchange the elements by only one space.
3. The smaller elements that are far away require many passes through the sort, to properly insert
them in its correct position.
4. The shell sort overcomes this limitation, gains speed than insertion sort, by comparing
elements that are at a specific distance from each other, and interchanges them if necessary.
5. The shell sort divides the list into smaller sub lists, and then sorts the sub lists separately using
the insertion sort. This is done by considering the input list being n-sorted.
6. This method splits the input list into h-independent sorted files. The procedure of h-sort is
insertion sort considering only the h th element (starting anywhere).
7. The value of h will be initially high and its repeatedly decremented until it reaches 1. When h
is equal to 1, a regular insertion sort is performed on the list, but by then the list of data is
guaranteed to be almost sorted.
8. Using the above procedure for any sequence values of h, always ending in 1 will produce a
sorted list.

Algorithm :- SHELL(ARR,N)
WHERE ARR IS AN ARRAY OF N ELEMENTS.
1. REPEAT FOR I=(N+1)/2 TO 1
2. REPEAT FOR J=I TO N-1
3. ASSIGN TEMP=ARR[J] , K=J-1
4. REPEAT WHILE (K>=0 AND TEMP < ARR[K])
5. ASSIGN ARR[K+1] = ARR[K], K=K-1
6. (END OF STEP4 WHILE LOOP)
7. ASSIGN ARR[K+1] =TEMP
8. INCREMENT J BY 1
9. (END OF STEP 2 FOR LOOP)
10. ASSIGN I = I/2
11. (END OF STEP1 FOR LOOP)
12. PRINT THE SORTED ARRAY ARR.

END SHELL()
Example

Unit I
43
 44

QUICK SORT
1. Quick sort also referred as partition exchange sort was developed by C.A.R.Hoare.
2. It is a sorting algorithm, which perform very well on larger lists than any other sorting
methods.
3. It employs divide and conquer rule for its operation. The main idea of the quick sort is to
divide the initial unsorted list in to two parts, such that every element in the first list is less than
all the elements present in the second list.
4. The procedure is then repeated recursively for both the parts, up to relatively short sequences,
which can be sorted until the sequences, reduces to length one i.e we divide the problem into two
smaller ones and conquer by solving the smaller ones.
5. The first step of the algorithm requires choosing a pivot

Unit I
44
 45

6. Value that will be used to divide big and small numbers.

7. Usually the first element of the list is chosen as the pivot value.
8. Once the pivot value has been selected, all elements smaller than the pivot are placed towards
the beginning of the set and all the elements larger than the pivot are placed to the right.
9. This process essentially sets the pivot value in the correct place each time.
10. Each side of the pivot is then quick sorted.

Algorithm QUICK (ARR,FIRST, LAST)

Where arr is an array of n elements, first refers to the first index of the array and last refers to the last index
of the array.
1. IF (FIRST<LAST) THEN
2. ASSIGN PIVOT = APP[FIRST], I=FIRST, J=LAST)
3. REPEAT WHILE (I<J)
4. REPEAT WHILE(ARR[I] <= PIVOT AND I LAST)
5. INCREMENT I BY 1
6. (END OF STEP4 WHILE LOOP)
7. REPEAT WHILE (ARR[J] <= PIVOT AND J>FIRST) DECREMENT J BY 1
8. DECREMENT J BY 1
9. (END OF STEP 7 WHILE LOOP)
10. IF(I<J) THEN

INTERCHANGE ARR[I] AND ARR[J]

(END OF STEP 10 IF STRUCTURE)
11. (END OF STEP 3 IF STRUCTURE)
12. INTERCHANGE ARR[FIRST]AND ARR[J]
13. QUICK(ARR,J+1,LAST)
14. QUICK(ARR,J+1,LAST)
15. (END OF STEP1 IF STRUCTURE)
16. PRINT THE SORTED ARRAY ARR.

END QUICK()

EXAMPLE :

Unit I
45
 46

Unit I
46
 47

UNIT -II
STACK :

“A stack is an ordered list in which all insertions and deletions are made at one end,
called the top”. stacks are sometimes referred to as Last In First Out (LIFO) lists

Stacks have some useful terminology associated with them:

 Push To add an element to the stack

 Pop To remove an element from the stock
 Peek To look at elements in the stack without removing them
 LIFO Refers to the last in, first out behavior of the stack
 FILO Equivalent to LIFO

Unit I
47
 48

stack (data structure)

Simple representation of a stack

Given a stack S=(a[1],a[2],.......a[n]) then we say that a1 is the bottom most element
and element a[i]) is on top of element a[i-1], 1<i<=n.

Implementation of stack :

1. array (static memory ).

2. linked list (dynamic memory)

The operations of stack are

1. PUSH operations
2. POP operations
3. PEEK operations

The Stack ADT

A stack S is an abstract data type (ADT) supporting the following three methods:
push(n) : Inserts the item n at the top of stack

pop() : Removes the top element from the stack and returns that top element.
An error occurs if the stack is empty.
peek(): Returns the top element and an error occurs if the stack is empty.

1. Adding an element into a stack. ( called PUSH operations )

Adding element into the TOP of the stack is called PUSH operation.

Unit I
48
 49

Check conditions :

If TOP = N , then STACK FULL

where N is maximum size of the stack.

Adding into stack ( PUSH algorithm )

procedure add(item : items);

{add item to the global stack stack ; top is the current top of stack
and n is its maximum size}
begin
if top = n then stackfull;
top := top+1;
stack(top) := item;
end: {of add}

item /
element 6
Stack Stack

PUSH top 6
operation
top 8 8
4 4

Implementation in C using array:

/* here, the variables stack, top and size are global variables */
void push (int item)
{
if (top == size-1)
printf(“Stack is Overflow”);
else
{
top = top + 1;
stack[top] = item;
}
}

2. Deleting an element from a stack. ( called POP operations )

Unit I
49
 50

Deleting or Removing element from the TOP of the stack is called POP operations.

Check Condition:

TOP = 0, then STACK EMPTY

Deletion in stack ( POP Operation )

procedure delete(var item : items);

{remove top element from the stack stack and put it in the item}
begin
if top = 0 then stackempty;
item := stack(top);
top := top-1;
end; {of delete}

item /
element 6

top 6 POP
8 operation
top 8
4
4
Stack
Stack

Implementation in C using array:

/* here, the variables stack, and top are global variables */
int pop ( )
{
if (top == -1)
{
printf(“Stack is Underflow”);
return (0);
}
else
{
return (stack[top--]);
}
}

Unit I
50
 51

3. Peek Operation:

 Returns the item at the top of the stack but does not delete it.
 This can also result in underflow if the stack is empty.
item /
element 6

top 6 top 6
PEEK
8 operation 8
4 4
Stack Stack
Algorithm:
PEEK(STACK, TOP)
BEGIN
/* Check, Stack is empty? */
if (TOP == -1) then
print ‚Underflow‛ and return 0.
else
item = STACK[TOP]/ * stores the top element into a local variable */
return item / * returns the top element to the user */
END

Implementation in C using array:

/* here, the variables stack, and top are global variables */
int pop ( )
{
if (top == -1)
{
printf(“Stack is Underflow”);
return (0);
}
else
{
return (stack[top]);
}
}

Unit I
51
 52

Note :

1. Infix notation A+(B*C)

equivalent Postfix notation ABC*+

2. Infix notation (A+B)*C

Equivalent Postfix notation AB+C*

Unit I
52
 53

Examples of use: ( application of stack )

Arithmetic Expressions: Polish Notation

 An arithmetic expression will have operands and operators.

 Operator precedence listed below:
Highest : ($)
Next Highest : (*) and (/)
Lowest : (+) and (-)

 For most common arithmetic operations, the operator symbol is placed in

between its two operands. This is called infix notation.

Unit I
53
 54

Example: A + B , E * F
 Parentheses can be used to group the operations.
Example: (A + B) * C
 Accordingly, the order of the operators and operands in an arithmetic
expression does not uniquely determine the order in which the operations are
to be performed.

 Polish notation refers to the notation in which the operator symbol is placed
before its two operands. This is called prefix notation.
Example: +AB, *EF
 The fundamental property of polish notation is that the order in which the
operations are to be performed is completely determined by the positions of
the operators and operands in the expression.
 Accordingly, one never needs parentheses when writing expressions in Polish
notation.

 Reverse Polish Notation refers to the analogous notation in which the

operator symbol is placed after its two operands. This is called postfix
notation.
Example: AB+, EF*
 Here also the parentheses are not needed to determine the order of the
operations.

 The computer usually evaluates an arithmetic expression written in infix notation in

two steps,
1. It converts the expression to postfix notation.
2. It evaluates the postfix expression.
 In each step, the stack is the main tool that is used to accomplish the given task.

(1)Question : ( Postfix evaluation )

How to evaluate a mathematical expression using a stack The algorithm for

Evaluating a postfix expression ?

• Initialise an empty stack

• While token remain in the input stream

– Read next token

– If token is a number, push it into the stack

Unit I
54
 55

– Else, if token is an operator, pop top two tokens off the stack, apply
the operator, and push the answer back into the stack

• Pop the answer off the stack.

Algorithm postfixexpression

Initialize a stack, opndstk to be empty.

{scan the input string reading one element at a time into symb }
While ( not end of input string )
{
Symb := next input character;

If symb is an operand Then

push (opndstk,symb)
Else
[symbol is an operator]
{
Opnd1:=pop(opndstk);
Opnd2:=pop(opndnstk);
Value := result of applying symb to opnd1 & opnd2
Push(opndstk,value);
}
Result := pop (opndstk);

Example:
623+-382/+*2$3+

Symbol Operand 1 (A) Operand 2 (B) Value (A  B) STACK

6 6
2 6, 2
3 6, 2, 3
+ 2 3 5 6, 5
- 6 5 1 1
3 1, 3
8 1, 3, 8
2 1, 3, 8, 2

Unit I
55
 56

/ 8 2 / 1, 3, 4
+ 3 4 7 1, 7
* 1 7 7 7
2 7, 2
$ 7 2 49 49
3 49, 3
+ 49 3 52 52

The Final value in the STACK is 52. This is the answer for the given expression.

(2) run time stack for function calls ( write factorial number calculation procedure)
push local data and return address onto stack
return by popping off local data and then popping off address and returning to it
return value can be pushed onto stack before returning, popped off by caller

(3) expression parsing

e.g. matching brackets: [ ... ( ... ( ... ) [ ...( ... ) ...] ... ) ... ]
push left ones, pop off and compare with right ones

4) INFIX TO POSTFIX CONVERSION

Infix expressions are often translated into postfix form in which the operators appear after
their operands. Steps:

1. Initialize an empty stack.

2. Scan the Infix Expression from left to right.
3. If the scannned character is an operand, add it to the Postfix Expression.
4. If the scanned character is an operator and if the stack is empty, then push the character to
stack.

5. If the scanned character is an operator and the stack is not empty, Then

(a) Compare the precedence of the character with the operator on the top of the stack.
(b) While operator at top of stack has higher precedence over the scanned character & stack
is not empty.
(i) POP the stack.
(ii) Add the Popped character to Postfix String.
( c ) Push the scanned character to stack.

6. Repeat the steps 3-5 till all the characters

7. While stack is not empty,
(a) Add operator in top of stack
(b) Pop the stack.
8. Return the Postfix string.

Unit I
56
 57

Algorithm Infix to Postfix conversion ( without parenthesis)

1. Opstk = the empty stack;

2. while ( not end of input )
{
symb = next input character;

3. if ( symb is an operand )
add symb to the Postfix String
4. else
{
5. While( ! empty (opstk) && prec ( stacktop ( opstk), symb) )
{
topsymb = pop ( opstk )
add topsymb to the Postfix String;
} / * end of while */
Push(opstk, symb);
} /* end else */
6. } /* end while * /

7. While( ! empty ( opstk ) )

{
topsymb = pop (opstk)
add topsymb to the Postfix String
} /* end of while */
8. Return the Postfix String.
QUEUE :

“A queue is an ordered list in which all insertions at one end called REAR and
deletions are made at another end called FRONT”. queues are sometimes referred
to as First In First Out (FIFO) lists.

enqueue
(Insertion)

dequeue Rear
Front
(Deletion)

Unit I
57
 58

Example
1. The people waiting in line at a bank cash counter form a queue.
2. In computer, the jobs waiting in line to use the processor for execution. This
queue is called Job Queue.

Operations Of Queue

There are two basic queue operations. They are,

Enqueue – Inserts an item / element at the rear end of the queue. An error occurs if
the queue is full.
Dequeue – Removes an item / element from the front end of the queue, and returns
it to the user. An error occurs if the queue is empty.

1. Addition into a queue

procedure addq (item : items);

{add item to the queue q}
begin
if rear=n then queuefull
else begin
rear :=rear+1;
q[rear]:=item;
end;
end;{of addq}

2. Deletion in a queue
procedure deleteq (var item : items);
{delete from the front of q and put into item}
begin
if front = rear then queueempty
else begin
front := front+1
item := q[front];
end;
end

Uses of Queues ( Application of queue )

Unit I
58
 59

Queues remember things in first-in-first-out (FIFO) order. Good for fair (first come first
served) ordering of actions.

Examples of use: (Application of stack )

1• scheduling

processing of GUI events

printing request

2• simulation

orders the events

models real life queues (e.g. supermarkets checkout, phone calls on hold)

Circular Queue :
Location of queue are viewed in a circular form. The first location is viewed after the
last one.
Overflow occurs when all the locations are filled.

rear

fron
t
Algorithm Circular Queue Insert

Void CQInsert ( int queue[ ], front, rear, item)

{
if ( front = = 0 )
front = front +1;
if ( ( ( rear = maxsize ) && ( front = = 1 ) ) || ( ( rear ! = 0 ) && ( front = rear +1)))
{
printf( ― queue overflow ―);

if( rear = = maxsize )

rear = 1;

Unit I
59
 60

else
rear = rear + 1;
q [ rear ] = item;
}
}

Algorithm Circular Queue Delete

int CQDelete ( queue [ ], front, rear )

{
if ( front = = 0 )
printf ( ― queue underflow ―);
else
{
item = queue [ front ];
if(front = = rear )
{
front = 0; rear = 0;
}
else if ( front = = maxsize )
{
front = 1;
}
else
front = front + 1;
}
return item;
}

Priority Queue

A priority queue is a collection of elements such that each element has been assigned
a priority and such that the order in which elements are deleted and processed
comes from the following rules:
1. An element of higher priority is processed before any element of lower
priority.
2. Two elements with the same priority are processed according to the order in
which they were added to the queue.

Two types of queue are

1. Ascending Priority Queue

2. Descending Priority Queue

Unit I
60
 61

1. Ascending Priority Queue

Collection of items into which item can be inserted arbitrarily & from
which only the Smallest item can be removed.

2. Descending Priority Queue

Collection of items into which item can be inserted arbitrarily & from
which only the Largest item can be removed.

Double Ended Queue

A deque (short for double-ended queue) is an abstract data structure for which elements can
be added to or removed from the front or back(both end). This differs from a normal queue,
where elements can only be added to one end and removed from the other. Both queues and
stacks can be considered specializations of deques, and can be implemented using deques.

Two types of Dqueue are

1. Input Restricted Dqueue

2. Ouput Restricted Dqueue.

Unit I
61
 62

1. Input Restricted Dqueue

Where the input (insertion) is restricted to the rear end and the deletions has
the options either end

2. Ouput Restricted Dqueue.

Where the output (deletion) is restricted to the front end and the insertions
has the option either end.

Example: Timesharing system using the prototype of priority queue – programs of high
priority are processed first and programs with the same priority form a standard queue.

Linked List
 Some demerits of array, leads us to use linked list to store the list of items.
They are,
1. It is relatively expensive to insert and delete elements in an array.
2. Array usually occupies a block of memory space, one cannot simply
double or triple the size of an array when additional space is required.
(For this reason, arrays are called “dense lists” and are said to be “static”
data structures.)
 A linked list, or one-way list, is a linear collection of data elements, called
nodes, where the linear order is given by means of pointers. That is, each
node is divided into two parts:
 The first part contains the information of the element i.e. INFO or
DATA.
 The second part contains the link field, which contains the address of
the next node in the list.
NODE
INFO LINK

Unit I
62
 63

 The linked list consists of series of nodes, which are not necessarily adjacent
in memory.
 A list is a dynamic data structure i.e. the number of nodes on a list may vary
dramatically as elements are inserted and removed.
 The pointer of the last node contains a special value, called the null pointer,
which is any invalid address. This null pointer signals the end of list.
 The list with no nodes on it is called the empty list or null list.

Example: The linked list with 4 nodes.

START
OR 7 5 8 9
HEAD

Types of Linked Lists:

a) Linear Singly Linked List

b) Circular Linked List
c) Two-way or doubly linked lists
d) Circular doubly linked lists

Advantages of Linked List

1. Linked List is dynamic data structure; the size of a list can grow or shrink during the
program execution. So, maximum size need not be known in advance.
2. The Linked List does not waste memory
3. It is not necessary to specify the size of the list, as in the case of arrays.
4. Linked List provides the flexibility in allowing the items to be rearranged.

What are the pitfalls encountered in single linked list?

1. A singly linked list allows traversal of the list in only one direction.
2. Deleting a node from a list requires keeping track of the previous node, that is, the
node whose link points to the node to be deleted.
3. If the link in any node gets corrupted, the remaining nodes of the list become
unusable.

Linearly-linked List

Is a collection of elements called Nodes. Each node consist of two fields, namely
data field to hold the values and link(next ) field points to the next node in the list.

It consists of a sequence of nodes, each containing arbitrary data fields and one or two
references ("links") pointing to the next and/or previous nodes.

Unit I
63
 64

A linked list is a self-referential datatype (or) data structure because it contains a

pointer or link to another data of the same type.

Linked lists permit insertion and removal of nodes at any point in the list in constant
time, but do not allow random access.

Several different types of linked list exist: singly-linked lists, doubly-linked lists,
and circularly-linked lists. One of the biggest advantages of linked lists is that nodes may
have multiple pointers to other nodes, allowing the same nodes to simultaneously appear in
different orders in several linked lists

Singly-linked list

The simplest kind of linked list is a singly-linked list (or slist for short), which has one link
per node. This link points to the next node in the list, or to a null value or empty list if it is
the final node.

A singly linked list containing three integer values

Doubly-linked list

A more sophisticated kind of linked list is a doubly-linked list or two-way linked list. Each
node has two links: one points to the previous node, or points to a null value or empty list if it
is the first node; and one points to the next, or points to a null value or empty list if it is the
final node.

An example of a doubly linked list.

Circularly-linked list

In a circularly-linked list, the first and final nodes are linked together. This can be done for
both singly and doubly linked lists. To traverse a circular linked list, you begin at any node
and follow the list in either direction until you return to the original node. Viewed another
way, circularly-linked lists can be seen as having no beginning or end. This type of list is
most useful for managing buffers for data ingest, and in cases where you have one object in a
list and wish to see all other objects in the list.

Unit I
64
 65

The pointer pointing to the whole list is usually called the end pointer.

Singly-circularly-linked list

In a singly-circularly-linked list, each node has one link, similar to an ordinary singly-linked
list, except that the next link of the last node points back to the first node.

As in a singly-linked list, new nodes can only be efficiently inserted after a node we already
have a reference to. For this reason, it's usual to retain a reference to only the last element in
a singly-circularly-linked list, as this allows quick insertion at the beginning, and also allows
access to the first node through the last node's next pointer.

•Note that there is no NULL terminating pointer

•Choice of head node is arbitrary
•A tail pointer serves no purpose
•What purpose(s) does the head pointer serve?

Doubly-circularly-linked list

In a doubly-circularly-linked list, each node has two links, similar to a doubly-linked list,
except that the previous link of the first node points to the last node and the next link of the
last node points to the first node. As in doubly-linked lists, insertions and removals can be
done at any point with access to any nearby node.

Sentinel nodes
Linked lists sometimes have a special dummy or sentinel node at the beginning and/or at the
end of the list, which is not used to store data.

Unit I
65
 66

Basic Operations on Linked Lists

1. Insertion
a. At first
b. At last
c. At a given location (At middle)
2. Deletion
a. First Node
b. Last Node
c. Node in given location or having given data item

Initial Condition

HEAD = NULL;
/* Address of the first node in the list is stored in HEAD. Initially there is no node in
the list. So, HEAD is initialized to NULL (No address) */

What are the Applications of linked list?

 To implement of Stack, Queue, Tree, Graph etc.,
 Used by the Memory Manager
 To maintain Free-Storage List

Doubly Linked Lists (or) Two – Way Lists

There are some problems in using the Single linked list. They are

1. A singly linked list allows traversal of the list in only one direction. (Forward only)
2. Deleting a node from a list requires keeping track of the previous node, that is, the
node whose link points to the node to be deleted.

These major drawbacks can be avoided by using the double linked list. The doubly
linked list is a linear collection of data elements, called nodes, where each node is
divided into three parts. They are:

1. A pointer field LEFT which contains the address of the preceding node in the list
2. An information field INFO which contains the data of the Node
3. A pointer field RIGHT which contains the address of the next node in the list

LEFT INFO RIGHT

Unit I
66
 67

Example:
head 7060 2140 4020 end
7060 NULL 7 2140 7060 7 4020 2140 7 NULL 4020

Linked lists vs. arrays

Array Linked list
Indexing O(1) O(n)
Inserting / Deleting at end O(1) O(1)
Inserting / Deleting in middle (with iterator) O(n) O(1)
Persistent No Singly yes
Locality Great Bad

Array Linked list

Static memory Dynamic memory
Insertion and deletion required to
Insertion and deletion are made
modify the existing element
easy.
location
Elements stored as contiguous Element stored as Non-contiguous
memory as on block. memory as pointers
Accessing element is fast Accessing element is slow
SINGLY LINKED LISTS

1. Insertion of a Node in the Beginning of a List

Step 1 : Allocate memory for a node and assign its address to the variable ‘ New’
Step 2 : Assign the element in the data field of the new node.
Step 3 : Make the next field of the new node as the beginning of the existing list.
Step 4 : Make the new node as the Head of the list after insertion.

Algorithm InsertBegin ( Head, Elt )

[ Adding the element elt in the beginning of the list pointed by Head]

1. new  getnode ( NODE )

2. data ( new )  elt
3. next ( new )  Head
4. Head  new
5. return Head

Unit I
67
 68

Insertion of a Node at the End of a Singly Linked List

Step 1 : Allocate memory for a node and assign its address to the variable ‘ New’
Step 2 : Assign the element in the data field of the new node.
Step 3 : Make the next field of the new node as NULL This is because the new node
will be the end of the resultant list.
Step 4 : If the existing list is empty, call this new node as the list. Else, get the
address of the last node in the list by traversing from the beginning pointer.
Step 5: Make the next field of the last node point to the new node.

Algorithm InsertEnd ( Head, Elt )

[ Adding the element elt at the end of the list]

1. new  getnode ( NODE )

2. data ( new )  elt
3. next ( new )  NULL
4. if (Head == NULL ) Then
Head  new
Return Head
Else
Temp  Head
5. While ( next ( temp ) # NULL )
temp  next ( temp )
6. next ( temp )  new
7. return Head.

Applications of linked lists

Linked lists are used as a building block for many other data structures, such as stacks,
queues and their variations.

1. Polynomial ADT:

A polynomial can be represented with primitive data structures. For example, a polynomial
represented as akxk ak-1xk-1 + ... + a0 can be represented as a linked list. Each node is a
structure with two values: ai and i. Thus, the length of the list will be k. The first node will
have (ak, k), the second node will have (ak-1, k-1) etc. The last node will be (a0, 0).

Unit I
68
 69

The polynomial 3x9 + 7x3 + 5 can be represented in a list as follows: (3,9) --> (7,3) --> (5,0)
where each pair of integers represent a node, and the arrow represents a link to its
neighbouring node.
Derivatives of polynomials can be easily computed by proceeding node by node. In our
previous example the list after computing the derivative would represented as follows: (27,8)
--> (21,2). The specific polynomial ADT will define various operations, such as
multiplication, addition, subtraction, derivative, integration etc. A polynomial ADT can be
useful for symbolic computation as well.

2. Large Integer ADT:

Large integers can also be implemented with primitive data structures. To conform to our
previous example, consider a large integer represented as a linked list. If we represent the
integer as successive powers of 10, where the power of 10 increments by 3 and the coefficent
is a three digit number, we can make computations on such numbers easier. For example, we
can represent a very large number as follows:
513(106) + 899(103) + 722(100).
Using this notation, the number can be represented as follows:
(513) --> (899) --> (722).
The first number represents the coefficient of the 106 term, the next number represents the
coefficient of the 103 term and so on. The arrows represent links to adjacent nodes.
The specific ADT will define operations on this representation, such as addition, subtraction,
multiplication, division, comparison, copy etc.

An array allocates memory for all its elements lumped together as one block of memory. In
contrast, a linked list allocates space for each element separately in its own block of memory
called a "linked list element" or "node". The list gets is overall structure by using pointers to
connect all its nodes together like the links in a chain.
Each node contains two fields: a "data" field to store whatever element type the list holds for
its client, and a "next" field which is a pointer used to link one node to the next node.

Each node is allocated in the heap with a call to malloc(), so the node memory continues to
exist until it is explicitly deallocated with a call to free(). The front of the list is a pointer to
the first node. Here is what a list containing the numbers 1, 2, and 3 might look like...

Unit I
69
 70

malloc() malloc() is a system function which allocates a block of memory in the "heap"
and returns a pointer to the new block. The prototype for malloc() and other heap functions
are in stdlib.h. The argument to malloc() is the integer size of the block in bytes. Unlike
local ("stack") variables, heap memory is not automatically deallocated when the creating
function exits. malloc() returns NULL if it cannot fulfill the request. (extra for experts) You
may check for the NULL case with assert() if you wish just to be safe. Most modern
programming systems will throw an exception or do some other automatic error handling in
their memory allocator, so it is becoming less common that source code needs to explicitly
check for allocation failures.
free() free() is the opposite of malloc(). Call free() on a block of heap memory to indicate to
the system that you are done with it. The argument to free() is a pointer to a block of memory
in the heap — a pointer which some time earlier was obtained via a call to malloc().

Sequential list: contiguous cells, indexed by location

Linked list: noncontiguous cells linked by pointers, implicitly indexed by number of

links away from head

Both also contain

location of first element (head)
length or end-of-list marker
Examples of end-of-list marker:
„\0‟ for C strings (sequential list)
NULL for C linked list

Representation
Sequential list: contiguous cells, indexed by location Linked list: noncontiguous cells linked
by pointers, implicitly indexed by number of links away from head
Both also contain
location of first element (head)
length or end-of-list marker
Examples of end-of-list marker:
„\0‟ for C strings (sequential list)
NULL for C linked list

Unit I
70
 71

Sequential List implementation

In C: typically an array with an int for the last used index.
A problem: must reserve memory for the list to grow into.
limits length of list to reserved length
reserved memory unusable for other purposes
Main advantage of sequential list: fast access to element by index.

Linked List implementation

In C: typically individual cells dynamically allocated containing a pointer to the next cell.

Advantages:

space used adapts to size • usually results in better space usage than sequential despite storing
a pointer in each cell

speed improvements for some operations

Disadvantages:

• speed reductions for some operations

Time efficiency 1

In the following, let n be the length of the list.

Initialize to empty list
Sequential and Linked O(1)
For sequential lists this really depends on the complexity of memory allocation, a complex
subject in itself. For linked lists, memory allocation time can affect the performance of the
other operations.
Select ith element
Sequential O(1) Linked O(i)

Time efficiency 2
Determine length
Sequential and Linked
O(1) if recorded
O(n) for marker – then linked takes longer following pointers and is more likely to leave the
cache
Traverse
Sequential and Linked O(n)
Linked takes longer for reasons above, but may be
insignificant compared to processing done on the elements.
Search

Unit I
71
 72

Sequential ordered O(log n)

Sequential unordered, Linked O(n)
Linked takes longer for reasons above.
Ordering can improve linked on average, since we can more
quickly detect that an element isn‘t in the list.

Time efficiency 3
Changes
These depend of course on how we locate where to make the change. The following describe
the additional cost.
Delete or insert element
Sequential O(n * size of an element) We must move elements over! Linked O(1)
Replace element (unordered)
Sequential and Linked O(1)
Replace data in an element
Sequential and Linked O(1)

Variants
There are other list implementations. For example:
Doubly Linked list
allows efficient backwards traversal
takes longer to insert and delete (but the same complexity)
takes more space for the extra pointer (unless we use the for trick to save space at the cost of
time)
Circular list (head and tail linked)

Unit I
72