Data structure

Data Structure: Definition

The logical and mathematical model of a particular organization of data is called
Data structure. The main characteristics of a data structure are:
Common Characteristics of Data Structures:
• Contains component data items which may be atomic or another data structure
• A set of operations on one or more of the component items
• Defined rules as to how components relate to each other and to the structure as a
whole
The choice of a particular data structure depends on following consideration:
• It must be rich enough in structure to mirror actual relationships of data in real world
for example the hierarchical relationship of the entities is best described by the
“tree” data structure.

• The structure should be simple enough that one can effectively process the data
when necessary.
 Practical Applications of Data Structures
• Score Board of a game is an example of array application.
• A simple question Paper is an array of numbered questions with each of them
assigned some marks.
• 2D arrays, commonly known as, matrices, are used in image processing.
• Speech processing, in which each speech signal is an array.
• Your viewing screen is also a multidimensional array of pixels.
• Book titles in a Library Management Systems.
• Online ticket booking.
• Contacts on a cell phone.
• For CPU scheduling in computer.
• To store the possible moves of chess on a chessboard.
• To store images of a specific size on an android or laptop.
 Categorization of Data Structures

• Linear and Non Linear

• Heterogenous and Homogenous

• Static and Dynamic

• Linear data structure- A data structure whose elements form a
sequence, and every element in structure has a unique predecessor
and a unique successor. Examples of linear data structure are:

• Arrays
• Linked Lists
• Stacks
• Queues

• Non-Linear data structures- A data structure whose elements do not

form a sequence. There is no unique predecessor or unique successor.
Examples of non linear data structures
• Trees
• Graphs
• Linear Data Structures

• Arrays- An array is a list of finite number of elements of same data

type. The individual elements of an array are accessed using an index
or indices to the array. Depending on number of indices required to
access an individual element of an array, array can be classified as:
• One-dimensional array or linear array that requires only one
index to access an individual element of an array

• Two dimensional array that requires two indices to access an

individual element of array

• The arrays for which we need two or more indices are known
as multidimensional array.
• Linked List

• Linear collection of data elements called nodes

• Each node consists of two parts; data part and pointer or link
part
• Nodes are connected by pointer links.
• The whole list is accessed via a pointer to the first node of the
list
• Subsequent nodes are accessed via the link-pointer member of
the current node
• Link pointer in the last node is set to null to mark the list’s end
• Use a linked list instead of an array when you have an
unpredictable number of data elements (dynamic memory
allocation possible)
• Diagram of two data nodes linked together

15 10

Data member
and pointer NULL pointer (points to nothing)

struct node {
int data;
struct node *nextPtr;
}
• nextPtr
– Points to an object of type node
– Referred to as a link
• Ties one node to another node
Types of Linked Lists

• Grounded Linked List

– Singly linked list
– Doubly linked list

• Circular Linked List

– Circular Linked list
• Pointer in the last node points back to the first node
– Circular doubly linked list
• Forward pointer of the last node points to the first node and backward
pointer of the first node points to the last node

• Header Linked List

– Linked list contains a header node that contains information regarding complete
linked list.
Stack- A stack, also called last-in-first-out (LIFO) system, is a linear list
in which insertions (push operation) and deletions (pop operations) can
take place only at one end, called the top of stack .
– Similar to a pile of dishes
– Bottom of stack indicated by a link member to NULL
– Constrained version of a linked list
• The two operations on stack are:
• push
– Adds a new node to the top of the stack
• pop
– Removes a node from the top
– Stores the popped value
– Returns true if pop was successful
Queues- A queue, also called a First-in-First-out (FIFO) system, is a
linear list in which insertions can take place at one end of the list, called
the rear of the list and deletions can take place only from other end ,
called the front of the list.

• Insert and remove operations

Tree- A tree is a non-linear data structure that represents a hierarchical
relationship between various elements.

• The top node of a tree is called the root node and each subsequent
node is called the child node of the root. Each node can have one or
more than one child nodes.

• General Tree
– Tree with all nodes having any number of child nodes

• Binary Tree
– Tree with all nodes having maximum two child nodes

• Binary search tree

– Type of Binary tree
Diagram of a binary tree

A D

C
Graph- A graph, G , is an ordered set (V,E) where V represent set of
elements called nodes or vertices in graph terminology and E represent
the edges between these elements.

• This data structure is used to represent relationship between pairs of

elements which are not necessarily hierarchical in nature. Usually
there is no distinguished `first' or `last' nodes. Graph may or may not
have cycles.
 Algorithms
• A finite set of steps that specify a sequence of operations to be carried
out in order to solve a specific problem is called an algorithm

Properties of Algorithms:

1. Finiteness- Algorithm must terminate in finite number of steps

2. Absence of Ambiguity-Each step must be clear and unambiguous
3. Feasibility-Each step must be simple enough that it can be easily
translated into the required language
4. Input-These are zero or more values which are externally supplied to
the algorithm
5. Output-At least one value is produced
 Algorithm complexity
• An algorithm is a sequence of steps to solve a problem. There can be more
than one algorithm to solve a particular problem and some of these solutions
may be more efficient than others. The efficiency of an algorithm is
determined in terms of utilization of two resources, time of execution and
memory. This efficiency analysis of an algorithm is called complexity
analysis, and it is a very important and widely-studied subject in computer
science.

• Performance requirements are usually more critical than memory

requirements. Thus in general, the algorithms are analyzed on the basis of
performance requirements i.e running time efficiency.

• Specifically complexity analysis is used in determining how resource(time

or space) requirements of an algorithm grow in relation to the size of input.
The input can be any type of data. The analyst has to decide which property
of the algorithm should be measured; the best choice is the property that
most significantly affects the efficiency-factor we are trying to analyze.
 Based on the type of resource variation studied, there are two types of
complexities
• Time complexity
• Space complexity
Space Complexity- The space complexity of an algorithm is amount
of memory it needs to run to completion. The space needed by a
program consists of following components:
• Instruction space-space needed to store the executable version of
program and is fixed.
• Data space-space needed to store all constants, variable values and
has further two components:
– Space required by constants and simple variables. This space is
fixed.
– Space needed by fixed sized structured variable such as arrays and
structures.
– Dynamically allocated space. This space usually varies.
• Environment stack space- Space needed to store information needed
to resume the suspended functions. Each time a function is invoked
following information is saved on environment stack

– Return address i.e from where it has to resume after completion of

the called function

– Values of all local variables and values of formal parameters in

function being invoked.
Time complexity- Time complexity of an algorithm is amount of time it needs to run to
completion. To measure time complexity, key operations are identified in a program
and are counted till program completes its execution. Time taken for various key
operations are:
• Execution of one of the following operations takes time 1:
1. assignment operation
2. single I/O operations
3. single Boolean operations, numeric comparisons
4. single arithmetic operations
5. function return
6. array index operations, pointer dereferences
• Running time of a selection statement (if, switch) is the time for the
condition evaluation + the maximum of the running times for the
individual clauses in the selection.

• Loop execution time is the number of times the loop body is

executed + time for the loop check and update operations, + time for
the loop setup.
† Always assume that the loop executes the maximum number
of iterations possible

• Running time of a function call is 1 for setup + the time for any
parameter calculations + the time required for the execution of the
function body.
• Time-Space Tradeoff- The best algorithm to solve a given problem is
one that requires less space in memory and takes less time to
complete its execution. But in practice, it is not always possible to
achieve both of these objectives. Thus, we may have to sacrifice one
at the cost of other. This is known as Time-space tradeoff among
algorithms. Thus if space is our constraint, we have to choose an
algorithm that requires less space at the cost of more execution time.
On the other hand, if time is our constraint, such as in real time
systems, we have to choose a program that takes less time to complete
execution at the cost of more space.
 Expressing Space and time complexity: Big ‘O’ notation

• It is very difficult to practically analyze the variation of time

requirements of an algorithm with variation in size of input. A
better approach to express space/time complexity is in the form of a
function f (n) where n is the input size for a given instance of
problem being solved.

Efficiency (algorithm A) = a function F of some property of A's input.

• The most important notation used for expressing this function f(n) is
Big O notation.
• Big O notation is a characterization scheme that allows to measure the properties
of algorithm such as performance and/or memory requirements in general fashion.
Assumptions of Big ‘O’ notation
• Uses the dominant term of the function
• Omits lower order terms and coefficient of dominant terms

Apart from n (size of input), efficiency measure will depend on three cases which
will decide number of operations to be performed.

• Best case performance under ideal condition

• Worst case performance under most un favorable condition
• Average case performance under most probable condition.

Big ‘O’ notation tries to analyze each algorithm performance in worst condition.
It is the rate of increase of f(n) that is examined as a measure of efficiency.
 Rate of growth: Big O notation
• Suppose F is an algorithm and suppose n is the size of input data. Clearly,
complexity f(n) of F increases as n increases. Rate of increase of f(n) is examined
by comparing f(n) with some standard functions such as log 2n, n, nlog2n, n2,n3 and
2n. One way to compare f(n) with these standard functions is to use functional O
notation defined as follows:
• Definition: If f(n) and g(n) are functions defined on positive integers with the
property that f(n) is bounded by some multiple of g(n) for almost all n. That is,
suppose there exist a positive integer no and a positive number M such that for all n>
no we have
|f(n) | ≤ M |g(n)|
• Then we may write
f(n)=O g(n)
Which is read as f(n)(time taken for number of operations) is of the order of g(n). If
g(n)=n, it means that f(n) is a linear proportional to n. For g(n)=n 2 , f(n) is
proportional to n2. Thus if an array is being sorted using an algorithm with g(n)=n 2,
it will take 100 times as long to sort the array that is 10 times the size of another
array.
For the statement f(n)=O g(n) to be informative, g(n) should be as small a function
of n as possible for which f(n)=Og(n) is true.
• Based on Big O notation, algorithms can be categorized as
• Constant time ( O(1)) algorithms
• Logarithmic time algorithms (O(logn))
• Linear Time algorithm (O(n))
• Polynomial or quadratic time algorithm (O(nk))
• Exponential time Algorithm (O(kn))
– It can be seen that logarithmic function log(n) grows most slowly
whereas kn grows most rapidly and polynomial function nk grows
in between the two extremities. Big-O notation, concerns only the
dominant term, low-order terms and constant coefficients are
ignored in a statement. Thus if g(n) = n2+2n, the variation is taken
as O(n2) rather than O(n). Complexities of some well known
searching and sorting algorithms is:
• Linear Search: O(n) Mergesort: O(nlogn)
• Binary Search: O(log2n)
• Bubble sort: O(n2)
 2n
10 8
n3
107
n2
10 6

Time taken
105
nlogn
104
n
10 3

logn
10 2

1 10 100 1000 10,000

Input size n

Rate of Growth of f(n) with n

 How to evaluate constants of complexity
notation
• Big ‘O’ notation: the function f(n)=3n+2
• To evaluate the constants: According to Big O notation:
• 3n+2<=3n which cannot be true for any n. Thus increase value
of M to 4
• 3n+2<=4n which is valid for n>=2
• Thus , f(n)=O(n) for n>=2 as 3n+2<=4n where 4 is defined M
and n denotes g(n) with n0=2
 What is complexity of 10n2+4n+2 according to Big ‘O’ notation
• f(n)=10n2+4n+2
• According to Big ‘O’ notation,
• 10n2+4n+2 <=Mn2
• The M we can take as 11
• 10n2+4n+2 <=11n2
• Put values of n starting from 0 till the equation gets validated
• We can see n0>=5
• According to Big O notation, f(n)=10n2+4n+2 is O(n2) for n0>=5 as 10n2+4n+2 <=
11n2 . Value of M is 11 and value of n0 >=5
 Conventions Used for Algorithms
• Identifying number-Each algorithm is assigned as identification
number
• Comments-Each step may contain a comment in brackets which
indicate the main purpose of the step
• Assignment statement-Assignment statement will use colon-equal
notation
– Set max:= DATA[1]
• Input/Output- Data may be input from user by means of a read
statement
– Read: Variable names
• Similarly, messages placed in quotation marks, and data in variables
may be output by means of a write statement:
– Write: messages or variable names
• Selection Logic or conditional flow-
– If condition, then:
– [end of if structure]
• Double alternative
– If condition, then
– Else:
– [End of if structure]
• Multiple Alternatives
– If condition, then:
– Else if condition2, then:
– Else if condition3, then
– Else:
– [End of if structure]
• Iteration Logic

• Repeat- for loop

– Repeat for k=r to s by t:
– [End of Loop]

• Repeat-While Loop
– Repeat while condition:
– [End of loop]
 Various operations performed on Arrays
• Traversal- processing each element in the list

• Searching- Finding location of an element

• Insertion- Adding a new element

• Deletion- Removing an element

• Sorting-Arranging elements in some type of order

• Merging- Combining two lists into a single list

• Traversing Linear Arrays- Traversing a linear array is basically, visiting
each element of array exactly once. Traversing is usually required to count number
of elements of array or to perform other operations on each element of array.
Traversing a linear array depends on size of array. Thus, traversal is O(1) operation
for an array of size n.
• Algorithm: (Traversing a linear Array)
[Here LA is a linear array with lower bound LB and upper Bound UB.
This algorithm traverses LA applying an operation PROCESS to each
element of LA]
• Step 1: [Initialize Counter] Set k:=LB
• Step 2: Repeat step 3 and 4 while k<=UB Repeat for k=LB to UB:
• Step 3: [Visit Element] Apply PROCESS Apply PROCESS to
• to LA[k] LA[k]
• Step 4: [increase Counter] set k:=k+1
• [End of step 2 loop]
• Step 5: Exit
• Insertion and Deletion in an Array- Insertion refers to operation of
adding an element to an array and deletion refers to deleting an
element from an array
• Insertion- Insertion can be done at various positions but the main
cases undertaken are:
– Insertion at the start
– Insertion at the end
– Insertion in the middle
– Insertion at any other position
Inserting an element at the end of the array can be done easily
provided the memory space allocated for the array is large enough to
accommodate the additional element. For inserting at any other
position, elements of array have to be shifted downwards from the
position where insertion is to be done. The new element is then
inserted in vacated position.
• Algorithm: (Inserting into a Linear Array) INSERT(LA,N,K,ITEM)
[Here LA is a linear array with N elements and K is a
positive integer such that K<=N. This algorithm inserts an
element ITEM into Kth position in LA]
• Step 1: [Initialize counter] Set J:=N
• Step 2: Repeat while J ≥ K:
[Move Jth element downward] Set LA[J+1]:=LA[J]
[ Decrease Counter] Set J:=J -1
[End of Step 2 Loop]
• Step 3: [Insert element] Set LA[K]:=ITEM
• Step 4:[Reset N] Set N:=N+1
• Step 5: Return
• Algorithm: (Inserting into a SORTED Linear Array)
INSERTSRT(LA,N,ITEM)
Here LA is a linear array with N elements. This algorithm
inserts an element ITEM in sorted array LA.
• Step1: Set J:=1
• Step 2: Repeat while LA[J]<=ITEM and J<=N
Set J:=J+1
[End of Step 2 Loop]
• Step 3: If J>N
Set A[J]=ITEM
Set N:=N+1
Return
Else
[Initialize counter] Set I:=N
[End of If structure]
•
• Step 4: Repeat while I ≥ J
[Move Jth element downward] Set LA[I+1]:=LA[I]
[ Decrease Counter] Set I:=I-1
[End of Step 4 Loop]
• Step 5: [Insert element] Set LA[J]:=ITEM

• Step 6:[Reset N] Set N:=N+1

• Step 7: Return
• Deletion refers to the operation of removing an element from exiting
list of elements. Like insertion, deletion can be done easily from the
end of the list. However to delete an element from any other location,
the elements are to be moved upwards in order to fill up the location
vacated by the removed element.
Algorithm: (Deleting from a Linear Array) DELETE(LA,N,K,ITEM)
Here LA is a linear array with N elements and K is a
positive integer such that K<=N. This algorithm deletes an
element ITEM from Kth position in LA.
• Step 1: [Initialize counter] Set ITEM:=LA[K]
• Step 2: Repeat for J=K to N-1:
[Move J+1st element upward] Set LA[J]:=LA[J+1]
[End of Step 2 Loop]
• Step 3: [Reset N] Set N:=N-1
• Step 4: Return
Algorithm: (Deleting from a Linear Array) DELNUM(LA,N,ITEM)
Here LA is a linear array with N elements. This algorithm
deletes a Number ITEM in LA.
• Step 1: [Initialize counter] Set K=1
• Step 2: Repeat while LA[K] ≠ ITEM
Set K:= K +1
[End of Loop]
• Step 2: Repeat for J=K to N-1:
[Move J+1st element upward] Set LA[J]:=LA[J+1]
[End of Step 2 Loop]
• Step 3: [Reset N] Set N:=N-1
• Step 4: Return
 Analysis of Insertion and deletion operation
• The best possible case in insertion operation is when the item is
inserted at the last position. In this case, no movement of elements is
required. The worst case occurs when the element has to be inserted at
the beginning of the list. In this case, we have to move all the
elements down the list. Therefore, the while loop executes n times,
each moving one element down. Thus complexity of insertion
operation is O(n) in worst case and average case, i.e linear time and is
O(1) in best case .
• The best case in deletion occurs when the element to be deleted is the
last element of the array. In this case, no element is moved up. Thus
complexity of deletion in best case is O(1). The worst case occurs
when element is deleted from the first position. In this case, all (n-1)
elements are moved up. The while loop executes n-1 times, each time
moving one element down. Thus complexity of deletion operation is
also O(n) in worst case and average case i.e linear time.
Search In Arrays
• Algorithm: (Linear Search) LINEAR(DATA, N, ITEM, LOC)
[Here DATA is a linear array with N elements and ITEM is a given
item of information. This algorithm finds the location LOC of ITEM
in DATA, or sets LOC:=0 if search is unsuccessful ]
• Step 1: [Initialize Counter] Set LOC:=1
• Step 2: [Search for ITEM]
Repeat while LOC<=N:
If DATA[LOC] = ITEM, Then:
Write: ’Element is at the location’, LOC
Return
[End of if structure]
Set LOC:=LOC+1
[End of Loop]
• Step 3: [Unsuccessful] If LOC=N+1 , then:
Set LOC:=0
• Step 4: Return
• Binary Search: Binary search is a method of searching in which array
list is divided into two equal parts. The main requirement of binary
search method is that the array has to be in sorted order. If the
elements of array list are in ascending order, then , if desired element
is less than the middle element of the list, it will never be present in
second half of the array and if desired element is greater than middle
element, it will never be present in first half of the array list. Thus
focus is given only to the desired half of the array list.
• Algorithm: BINARY(DATA, LB, UB, ITEM, LOC)
[Here DATA is a sorted array with lower bound LB and
upper bound UB, and the ITEM is a given item of
information. The variables BEG, END and MID denote,
beginning, end and middle location of a segment of
elements of DATA. This algorithm finds the location LOC
of ITEM in DATA or set LOC=NULL]
• Step 1: [Initialize segment variable] Set BEG:=LB, END:=UB and
MID:= INT((BEG+END)/2)
Step 2: Repeat while BEG<=END and DATA[MID]≠ITEM
If ITEM < DATA[MID], then:
Set END:= MID -1
Else:
Set BEG:= MID +1
[End of if structure]
• Step 3: Set MID:=INT((BEG+END)/2)
[End of step2 loop]
• Step 4: If DATA[MID]=ITEM, then:
Set LOC:=MID
Else :
Set LOC:=NULL
[End of if structure]
• Step 5: Return
• Analysis of Linear Search and Binary Search
• LINEAR SEARCH
• In best possible case, item may occur at first position. In this case, search operation
terminates in success with just one comparison. The best case of a successful search
is O(1). However, the worst case occurs when either item is present at last position
or element is not there in the array. In former case, search terminates in success with
n comparisons. In latter case, search terminates in failure with n comparisons. Thus
in worst case, the linear search is O(n) operation. In average case, the average
number of comparisons required to find the location of item is approximately equal
to half of the number of elements O(n/2 ) in the array.
.
Complexity of Binary Search
 Complexity of binary search (contd.)

• Approximately, we have to run the algorithm till

N/2k=1
• Multiply both sides by 2k
N=2k
• Taking log2 on both sides,
log2N=k.log22 and log22=1
• Thus , k, number of iterations required to search for an element in an array using
binary search is
• k= log2N
Problem: Suppose there are 1000000 elements in an array. How many
maximum comparisons will be required in binary search to search for
an element
Solution: Find out what power of 2 will be approximately equivalent
to the size of array such that
2x = y >= n
210= 1024 > 1000
Thus 220 > 1000000
Thus 20 comparisons will be required for searching for the element
Problem: Suppose there are 84 elements in an array. Find out number
of iterations required to search an element in the array using binary
search algorithm
• Solution: As binary search divides the array into halves, we need to calculate the
number of divisions required till array reduces to one element. In other words we
need to find the highest power of 2 greater than number of elements in the array.
• Thus, we need to find k for which
2k > 84
As 27 is 128, we can take value of k approximately equal to 7. Thus 7 iterations will be
required to search an element in the array
 Address calculations in arrays

• Address Calculation in single (one) Dimension Array:

• Address of an element of an array say “A[ I ]” is calculated using the following
formula:
• Address of A [ I ] = B + W * ( I – LL )
• Where,
B = Base address
W = Storage Size of one element stored in the array (in byte)
I = Subscript of element whose address is to be found
LL = Lower limit / Lower Bound of subscript, if not specified assume 0 (zero)
• Given the base address of an array B[1300…..1900] as 1020 and size
of each element is 2 bytes in the memory. Find the address
of B[1700].
• Solution:
• The given values are: B = 1020, LL = 1300, W = 2, I = 1700
• Address of A [ I ] = B + W * ( I – LL )
• = 1020 + 2 * (1700 – 1300)
= 1020 + 2 * 400
= 1020 + 800
= 1820 [Ans]
• Address Calculation in Double (Two) Dimensional Array:
• While storing the elements of a 2-D array in memory, these are
allocated contiguous memory locations. Therefore, a 2-D array must
be linearized so as to enable their storage.
• There are two alternatives to achieve linearization:
• Row-Major
• Column-Major.
• Address of an element of any array say “A[ I ][ J ]” is calculated in
two forms as given:
(1) Row Major System (2) Column Major System
Row Major System:
• The address of a location in Row Major System is calculated using the
following formula:
• Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
Column Major System:
• The address of a location in Column Major System is calculated using
the following formula:
• Address of A [ I ][ J ] Column Major Wise = B + W * [ ( I – Lr ) +
M * ( J – Lc )]
• Where,
B = Base address
I = Row subscript of element whose address is to be found
J = Column subscript of element whose address is to be found
W = Storage Size of one element stored in the array (in byte)
Lr = Lower limit of row/start row index of matrix, if not given
assume 0 (zero)
Lc = Lower limit of column/start column index of matrix, if not given
assume 0 (zero)
M = Number of row of the given matrix
N = Number of column of the given matrix
• Usually number of rows and columns of a matrix are given ( like
A[20][30] or A[40][60] ) but if it is given as A[Lr- – – – – Ur, Lc- – –
– – Uc]. In this case number of rows and columns are calculated as:
• Number of rows (M) will be calculated as = (Ur – Lr) + 1
• Number of columns (N) will be calculated as = (Uc – Lc) + 1
• Number of elements in the array will be calculated as=M x N
• Q 1. An array X [-15……….10, 15……………40] requires one byte
of storage. If beginning location is 1500 determine the location of X
[15][20].
• Solution:
• As you see here the number of rows and columns are not given in the
question. So they are calculated as:
• Number or rows say M = (Ur – Lr) + 1 = [10 – (- 15)] +1 = 26
Number or columns say N = (Uc – Lc) + 1 = [40 – 15)] +1 = 26
• (i) Column Major Wise Calculation of above equation
• The given values are: B = 1500, W = 1 byte, I = 15, J = 20, Lr = -15,
Lc = 15, M = 26
• Address of A [ I ][ J ] = B + W * [ ( I – Lr ) + M * ( J – Lc ) ]
• = 1500 + 1 * [(15 – (-15)) + 26 * (20 – 15)]
= 1500 + 1 * [30 + 26 * 5]
= 1500 + 1 * [160]
= 1660 [Ans]
• (ii) Row Major Wise Calculation of above equation
• The given values are: B = 1500, W = 1 byte, I = 15, J = 20, Lr = -15, Lc = 15, N = 26
• Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
• = 1500 + 1* [26 * (15 – (-15))) + (20 – 15)]
= 1500 + 1 * [26 * 30 + 5]
= 1500 + 1 * [780 + 5]
= 1500 + 785
= 2285 [Ans]
 Sorting Techniques in Array
• Bubble sort method- The bubble sort method requires n-1 passes to
sort an array where n is the size of array. In each pass, every element
of the array a[i] is compared with a[i+1] for i=0 to n-k where k is the
pass number. If a[i]>a[i+1], they are swapped. This will cause largest
element to move or bubble up.
• Algorithm: BUBBLE(DATA, N)
Here DATA is an array with N elements. This
algorithm sorts the elements in DATA.
• Step 1: Repeat step 2 and 3 for K=1 to N-1:
• Step 2: [Initialize pass pointer PTR] Set PTR:=1
• Step 3:[Execute Pass] Repeat while PTR ≤ N-K
• IF DATA[PTR] > DATA[PTR + 1], then:
Interchange DATA[PTR] and DATA[PTR + 1]
[End of If structure]
Set PTR:=PTR +1
[End of Step 3 loop]
[End of Step 1 Loop]
• Step 4: Return
• Complexity analysis of Bubble sort method: Traditionally, time for
sorting an array is measured in terms of number of comparisons. The
number f(n) of comparisons in bubble sort is easily computed.
Specifically, there are n-1 comparisons during first pass, n-2
comparisons in second pass and so on.
Thus, f(n)=(n-1) +(n-2) +-------+2+1
= n(n-1)/2 = n2 / 2 – n/2
= O(n2)
Thus time required to sort an array using bubble sort method is
proportional to n2 where n is number of input items. Thus complexity
of bubble sort is O(n2). This complexity remains same in both worst
case and average case. Best case complexity of bubble sort is O(n).
Bubble sort is not considered to be a good sorting algorithm for large
value of n .
 Intialization
time of
Time taken by inner
variables
loop to execute
Time taken
by outer
loop to
execute
• Algorithm: BUBBLE_BESTCASE(DATA, N)
Here DATA is an array with N elements. This
algorithm sorts the elements in DATA.
• Step 1: Repeat step 2 and 3 for K=1 to N-1:
• Step 2: [Initialize pass pointer PTR] Set PTR:=1
Set FLAG:=0
• Step 3:[Execute Pass] Repeat while PTR ≤ N-K
• IF DATA[PTR] > DATA[PTR + 1], then:
• SET FLAG:=1
Interchange DATA[PTR] and DATA[PTR + 1]
[End of If structure]
Set PTR:=PTR +1
[End of Step 3 loop]
IF FLAG=0,then:
Return
[End of Step 1 Loop]
• Step 4: Return
• Selection sort method: Selection sort method requires n-1 passes to
sort an array. In first pass, find smallest element from elements
a[0],a[1],---a[n-1] and swap with first element. i.e a[0]. In second
pass, find the smallest element from a[1],a[2]----------a[n-1] and swap
with a[1] and so on.
• Algorithm: (Selection sort) SELECTION(A, N)
This algorithm sorts an array A with N elements.
• Step 1: Repeat steps 2 and 3 for k=1 to N-1
• Step 2: Set Min:=A[k] and LOC:=k
• Step 3: Repeat for j=k+1 to N:
If Min>A[j], then:
Set Min:= A[j] and LOC:=J
[End of if structure]
[End of step 3 Loop]
• Step 4: [Interchange A[k] and A[LOC]]
Set Temp:= A[k]
Set A[k]:= A[LOC]
Set A[LOC]:=Temp
[End of step 1 Loop]
• Step 5 Return

• Complexity of Selection sort method: The number f (n) of

comparisons in selection sort algorithm is independent of original
order of elements. There are n-1 comparisons during pass 1 to find the
smallest element, n-2 comparisons during pass 2 to find the second
smallest element, and so on.
• Accordingly,
• f (n)= (n-1)+(n-2)+----------------------+2+1
• = n(n-1)/2= O(n2)
• The f (n) holds the same value O(n2) for best case, worst case and
average case.
• Insertion sort- In this procedure of sorting, we pick up a value and
insert it at appropriate place in sorted sub list i.e during kth operation
or iteration, the element a[k] is inserted in its proper place in sorted
sub array a[1],a[2],a[3]---a[k-1]. This task is accomplished by
comparing a [k] with a[k-1],a[k-2] ------- and so on until the first
element a [j] such that a [j] ≤ a [k] is found. Then each element
a[k-1],a[k-2]--------a[j+1] are moved one position up and a [k] is
inserted in ( j+1)th position in array.
 Algorithm: (Insertion sort) INSERTIONSORT(A , N)
This algorithm sorts the array A with N elements.
• Step 1: Set A[0]:= -∞
• Step 2: Repeat steps 3 to 5 for K=2 to N:
• Step 3: Set TEMP:=A[K] and PTR:=K-1
• Step 4: Repeat while TEMP <A[PTR] :
[Moves element forward] Set A[PTR + 1]:=A[PTR]
Set PTR:= PTR – 1
[End of step 4 Loop]
• Step 5:[Inserts element in proper place] Set A[PTR + 1]:= TEMP
[End of step 2 Loop]
• Step 6: Return
 Algorithm: (Insertion sort) INSERTIONSORT2(A , N)
This algorithm sorts the array A with N elements.
• Step 1: Repeat steps 3 to 5 for K=2 to N:
• Step 2: Set TEMP:=A[K] and PTR:=K-1
• Step 3: Repeat while TEMP <A[PTR] and PTR >= 1 :
[Moves element forward] Set A[PTR + 1]:=A[PTR]
Set PTR:= PTR – 1
[End of step 3 Loop]
• Step 5:[Inserts element in proper place] Set A[PTR + 1]:= TEMP
[End of step 1 Loop]
• Step 6: Return
• Complexity of Insertion Sort
The number f(n) of comparisons in insertion sort algorithm can be
easily computed . Worst case occurs when array A is in reverse order
and inner loop must use n-1 comparisons.
f(n)=1+2+----------------n-1
=n(n+1)/2=O(n2)
In average case, there will be approximately (n-1)/2 comparisons in
inner loop
f(n)=1/2+2/2+---------------(n-1)/2=n(n+1)/4=O(n 2)

In best case, the complexity of insertion sort will be O(n) as only the
passes will work but no movement of elements will be done
LINKED LIST
• Advantages and disadvantages of arrays over a linked list
Advantages:
• Arrays use contiguous memory location which facilitate calculation of
address of nth element if address of first element is known.
• Random access of elements is possible
• Arrays consume less memory as they do not require extra memory for
storage of pointers as required in a linked list
• Due to random access , binary search is possible in arrays which is an
efficient searching algorithm
Disadvantages:
• Arrays require size specification before using them which cannot be
changed . In other words , Arrays cannot grow in size
• Arrays cannot use scattered memory
• Insertion and deletion in Arrays is expensive
• Arrays support only homogenous elements and thus, cannot store
records or heterogeneous data
• Advantage and disadvantages of linked list over an array
Advantages:
• Linked list can use scattered memory easily
• Linked lists are dynamic and grow in size as per the requirement
• Linked lists support heterogeneous data and can store records
• Insertion and deletion of elements in a Linked list is more conveneint
and less expensive in terms of time taken
Disadvantages:
• Linked list does not support random access of elements
• Linked lists can lead to problem of dangling pointers
• Extra memory is wasted in each node of a linked list as each node
requires a pointer for storing the address of next element
• There is no way of calculating the address of nth node of a linked list
from the address of first node
• Binary search is not implemented in a linked list as random access is
not possible
• Linked List- A linked list or one-way list is a linear collection of data
elements, called nodes , where linear order is given by means of
pointers. Each node is divided into two parts:
• The first part contains the information of the element.
• Second part, called the linked field or next pointer field, contains the
address of the next node in the list.
Representation of Linked list in memory
• Linked list is maintained in memory by two linear arrays: INFO and
LINK such that INFO[K] and LINK[K] contain respectively the
information part and the next pointer field of node of LIST. LIST also
requires a variable name such as START which contains the location
of the beginning of the list and the next pointer denoted by NULL
which indicates the end of the LIST.
START

INFO[PTR]
LINK[PTR]
 BED NUMBER PATIENT NEXT
START
1 Kirk 7
5
2
3 Dean 11
4 Maxwell 12
5 Adams 3
6
7 Lane 4
8 Green 1
9 Samuels 0
10
11 Fields 8
12 Nelson 9
• Algorithm: (Traversing a Linked List)
Let LIST be a linked list in memory. This algorithm
traverses LIST, applying an operation PROCESS to each
element of LIST. Variable PTR points to the node
currently being processed.
• Step 1: Set PTR:= START
• Step 2: Repeat while PTR ≠ NULL:
Apply PROCESS to INFO[PTR]
Set PTR:= LINK[PTR] [PTR now points to next node]
[End of Step 2 Loop]
• Step 3: Exit
 Searching an unsorted Linked List
• Algorithm: SEARCH( INFO,LINK,START,ITEM,LOC)
LIST is a linked list in memory. This algorithm finds the
location, LOC, of the node where ITEM first appears in
LIST, or sets LOC=NULL
• Step 1: Set PTR:=START
• Step 2: Repeat while PTR≠ NULL
If ITEM = INFO[PTR], then:
Set LOC := PTR
Return
Set PTR:= LINK[PTR]
[End of If structure]
[End of Step 2 Loop]
• Step 3: [Search is unsuccessful] Set LOC:=NULL
• Step 4: Return
Complexity of this algorithm is same as that of linear search
algorithm for linear array. Worst case running time is proportional to
number n of elements in LIST and the average case running time is
proportional to n/2 with condition that ITEM appears once in LIST
but with equal probability in any node of LIST.
The best case complexity of linear search for an element in linked list
is O(1)

Binary search cannot be applied to linked list as there is no

provision to locate the middle element of LIST. This property is one
of the main drawback of using a linked list as a data structure.
• Search in sorted list
• Algorithm: SRCHSL(INFO,LINK,START,ITEM,LOC)
LIST is sorted list (Sorted in ascending order) in memory.
This algorithm finds the location LOC of the node where
ITEM first appears in LIST or sets LOC=NULL
• Step 1: Set PTR:= START
• Step 2:Repeat while PTR ≠ NULL and ITEM>=INFO[PTR]
If ITEM = INFO[PTR], then:
Set LOC := PTR
Return
Else If ITEM > INFO[PTR], then:
Set PTR := LINK[PTR]
[End of If structure]
[End of step 2 Loop]
• Step 3: Set LOC:= NULL
• Step 4: Return
• Insertion into a Linked List- Together with the linked list , a special
list is maintained in memory which consist of unused memory cells.
This list, which has its own pointer, is called the list of available space
or the free storage list or the free pool. This list is called the Avail
List. During insertion operation, new nodes are taken from this avail
list which is maintained just like normal data linked list using its own
pointer. Similar to START, Avail list also has its own start pointer
named as AVAIL which stores the address of the first free node of
avail list.
 1 Kirk 7
2 6
START 5
3 Dean 11
4 Maxwell 12
5 Adams 3
6 0
7 Lane 4
8 Green 1
AVAIL 10 9 Samuels 0
10 2
11 Fields 8
12 Nelson 9
• Insertion in a Linked List- Algorithms which insert nodes into linked
lists come up in various situations. Three main cases to be discussed
are:
• Inserting node at the beginning of the List
• Inserting node after the node with a given location
• Inserting node into a sorted list.
For all algorithms, variable ITEM contains the new
information to be added to the list. All cases follow some common
steps:
• Checking to see if free space is available in AVAIL list. If
AVAIL=NULL, algorithm will print overflow
• Removing first node from AVAIL list. Using variable NEW to keep
track of location of new node, this step can be implemented by the
pair of assignments (in this order)
NEW:= AVAIL and AVAIL:=LINK[AVAIL]
• Copying new information into new node
INFO[NEW]:=ITEM
 START

AVAIL

ITEM

NEW

INSERTION AT THE BEGINNING OF THE LINKED LIST

 INSERTING AT THE BEGINNING OF THE LIST
• Algorithm: INSFIRST (INFO, LINK,START,AVAIL,ITEM)
This algorithm inserts ITEM as the first node in the list
• Step 1: [OVERFLOW ?] If AVAIL=NULL, then
Write: OVERFLOW
Return
• Step 2: [Remove first node from AVAIL list ]
Set NEW:=AVAIL and AVAIL:=LINK[AVAIL].
• Step 3: Set INFO[NEW]:=ITEM [Copies new data into new node]
• Step 4: Set LINK[NEW]:= START
[New node now points to original first node]
• Step 5: Set START:=NEW [Changes START so it points to new
node]
• Step 6: Return
 INSERTING AFTER A GIVEN NODE
• Algorithm: INSLOC(INFO, LINK,START,AVAIL, LOC, ITEM)
This algorithm inserts ITEM so that ITEM follows the
node with location LOC or inserts ITEM as the first node
when LOC =NULL
• Step 1: [OVERFLOW] If AVAIL=NULL, then:
• Write: OVERFLOW
• Return
• Step 2: [Remove first node from AVAIL list]
Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
• Step 3: Set INFO[NEW]:= ITEM [Copies new data into new node]
• Step 4: If LOC=NULL, then:
Set LINK[NEW]:=START and START:=NEW
Else:
Set LINK[NEW]:=LINK[LOC] and LINK[LOC]:= NEW
[End of If structure]
• Step 5: Return
START LOC

AVAIL

NEW

18
ITEM
 INSERTING BEFORE A GIVEN NODE
• Algorithm: INSLOC(INFO, LINK,START,AVAIL, ITEM, ITEM1)
This algorithm inserts ITEM so that ITEM PRECEDES the
node with data item ITEM1
• Step 1: [OVERFLOW] If AVAIL=NULL, then:
Write: OVERFLOW
Return
• Step 2: [Remove first node from AVAIL list]
Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
• Step 3: Set INFO[NEW]:= ITEM [Copies new data into new node]
• Step 4: Set PTR:=START and SAVE:=NULL
• Step 5: Repeat while INFO[PTR]≠ ITEM1
Set SAVE:=PTR and PTR:=LINK[PTR]
[End of Loop]
• Step 6:Set LOC:=SAVE
• Step 7: If LOC=NULL, then:
Set LINK[NEW]:=START and START:=NEW
Else:
Set LINK[NEW]:=LINK[LOC] and LINK[LOC]:= NEW
[End of If structure]
• Step 8: Return
 INSERTING BEFORE A GIVEN NODE WITH LOCATION GIVEN
• Algorithm: INSLOC(INFO, LINK,START,AVAIL, ITEM, LOC)
This algorithm inserts ITEM so that ITEM PRECEDES the
node with location LOC
• Step 1: [OVERFLOW] If AVAIL=NULL, then:
Write: OVERFLOW
Return
• Step 2: [Remove first node from AVAIL list]
Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
• Step 3: Set INFO[NEW]:= ITEM [Copies new data into new node]
• Step 4: Set PTR:=START and SAVE:=NULL
• Step 5: Repeat while PTR≠ LOC
Set SAVE:=PTR and PTR:=LINK[PTR]
[End of Loop]
• Step 6:Set LOC:=SAVE
• Step 7: If LOC=NULL, then:
Set LINK[NEW]:=START and START:=NEW
Else:
Set LINK[NEW]:=LINK[LOC] and LINK[LOC]:= NEW
[End of If structure]
• Step 8: Return
 INSERTING BEFORE NTH NODE
• Algorithm: INSLOC(INFO, LINK,START,AVAIL, ITEM, N)
This algorithm inserts ITEM so that ITEM PRECEDES the Nth node
• Step 1: [OVERFLOW] If AVAIL=NULL, then:
Write: OVERFLOW
Return
• Step 2: [Remove first node from AVAIL list]
Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
• Step 3: Set INFO[NEW]:= ITEM [Copies new data into new node]
• Step 4: Set PTR:=START , K:=1, LOC:=NULL
• Step 5: Repeat while K< N-1
PTR:=LINK[PTR]
• Set K:=K+1
Set LOC:=PTR
• [End of Loop]
• Step 7: If LOC=NULL, then:
Set LINK[NEW]:=START and START:=NEW
Else:
Set LINK[NEW]:=LINK[LOC] and LINK[LOC]:= NEW
[End of If structure]
• Step 8: Return
 INSERTING IN SORTED LIST • SAVE:=PTR and PTR:=LINK[PTR]
• Algorithm: INSSORT(INFO, [End of while loop]
LINK,START,AVAIL, LOC, ITEM)
[This algorithm inserts ITEM so that ITEM
follows the node with location LOC or • Step 6: Set LOC:=SAVE
inserts ITEM as the first node] • Step 7:
when LOC =NULL] If LOC=NULL, then:
• Step 1: [OVERFLOW] Set LINK[NEW]:=START and
• If AVAIL=NULL, then: START:=NEW
Write: OVERFLOW Else:
Return Set LINK[NEW]:=LINK[LOC] and
[end of if structure] LINK[LOC]:= NEW
• Step 2: [Remove first node from AVAIL list] [End of If structure]
Set NEW:=AVAIL and • Step 8: Return
AVAIL:=LINK[AVAIL]
• Step 3: Set INFO[NEW]:= ITEM
[Copies new data into new node]
• Step 4: [save previous address]
• Set SAVE:=NULL and PTR:=START
• Step 5:
• Repeat while ITEM>=INFO[PTR] and
PTR ≠ NULL
 Complexity of insertion in linked list

• Complexity of inserting a node in a linked list is O(1)in an empty all the cases as
elements need not be shifted for list or at beginning of the list. This is the best case.
• Inserting at any other position in a linked list is O(n). This complexity is same for
worst and average case.
 Deletion of a node from a linked list
• Case 1: Deletion of node following a given node
• Algorithm: DEL(INFO,LINK,START,AVAIL,LOC,LOCP)
This algorithm deletes node N with location LOC. LOCP
is location of node which precedes N or when N is first
node, LOCP=NULL.
• Step 1: If LOC=NULL, then:
Write: ‘UNDERFLOW’
Return
• Step 2: If LOCP=NULL, then:
Set START:=LINK[START] [Deletes first node]
Else:
Set LINK[LOCP]:=LINK[LOC]
[End of if structure]
• Step 3: [Return deleted node to AVAIL list]
Set LINK[LOC]:=AVAIL and
AVAIL:=LOC
• Step 4: Return
 Deleting the node with a given item of information

For deleting with given item of information, we first need to know the
location of item to be deleted and also the location preceding the item
to be deleted. For this, one algorithm will be called from the main
algorithm to search for the two locations. Two variables, SAVE and
PTR will be used to save the location of preceding and current node at
every comparison respectively. Once , locations are found, deletion
will be done in main algorithm.
• Algorithm: DELETE(INFO,LINK,START,ITEM,LOC,LOCP)
[This algorithm finds the location LOC of first node N
which contains ITEM and location LOCP of node
preceding N. if ITEM does not appear in the list, procedure
sets LOC=NULL and if ITEM appears in first node, then it
sets LOCP=NULL]
• Step 1: If START=NULL, then:
Write: ‘Underflow’
Return
• Step 2: Set PTR=START
• Step 3: Set SAVE:=NULL and PTR:=START
Repeat while INFO[PTR] ≠ ITEM and PTR≠NULL:
Set SAVE:=PTR and PTR:=LINK[PTR]
[end of while loop]
• Step 4: Set LOC:=PTR and LOCP:=SAVE
• Step 5: IF LOC=NULL, then
Write:`element not in list’
Return
• Step 3: If LOCP=NULL, then:
Set START:= LINK[START]
Else:
Set LINK[LOCP]:=LINK[LOC]
[End of if structure]
• Step 4: Set LINK[LOC]:=AVAIL and AVAIL:=LOC
• Step 5: Return
 Concatenating two linear linked lists
• Algorithm: Concatenate(INFO,LINK,START1,START2)
This algorithm concatenates two linked lists with start
pointers START1 and START2
• Step 1: Set PTR:=START1
• Step 2: Repeat while LINK[PTR]≠NULL:
Set PTR:=LINK[PTR]
[End of Step 2 Loop]
• Step 3: Set LINK[PTR]:=START2
• Step 4: Return
• Circular Linked List- A circular linked list is a linked list in which
last element or node of the list points to first node. For non-empty
circular linked list, there are no NULL pointers. The memory
declarations for representing the circular linked lists are the same as
for linear linked lists. All operations performed on linear linked lists
can be easily extended to circular linked lists with following
exceptions:
• While inserting new node at the end of the list, its next pointer field is
made to point to the first node.
• While testing for end of list, we compare the next pointer field with
address of the first node
Circular linked list is usually implemented using header linked
list. Header linked list is a linked list which always contains a special
node called the header node, at the beginning of the list. This header
node usually contains vital information about the linked list such as
number of nodes in lists, whether list is sorted or not etc. Circular
header lists are frequently used instead of ordinary linked lists as
many operations are much easier to state and implement using header
lists
• This comes from the following two properties of circular header
linked lists:
• The null pointer is not used, and hence all pointers contain valid
addresses
• Every (ordinary ) node has a predecessor, so the first node may not
require a special case.
• Algorithm: (Traversing a circular header linked list)
This algorithm traverses a circular header linked list with
START pointer storing the address of the header node.
• Step 1: Set PTR:=LINK[START]
• Step 2: Repeat while PTR≠START:
Apply PROCESS to INFO[PTR]
Set PTR:=LINK[PTR]
[End of Loop]
• Step 3: Return
 Searching a circular header linked list
• Algorithm: SRCHHL(INFO,LINK,START,ITEM,LOC)
• This algorithm searches a circular header linked list
• Step 1: Set PTR:=LINK[START]
• Step 2: Repeat while INFO[PTR]≠ITEM and PTR≠START:
Set PTR:=LINK[PTR]
[End of Loop]
• Step 3: If INFO[PTR]=ITEM, then:
Set LOC:=PTR
Else:
Set LOC:=NULL
[End of If structure]
• Step 4: Return
 Insertion in a circular header linked list
Algorithm: INSRT(INFO,LINK,START,AVAIL,ITEM,LOC)
This algorithm inserts item in a circular header linked list
after the location LOC
• Step 1:If AVAIL=NULL, then
Write: ‘OVERFLOW’
Exit
• Step 2: Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
• Step 3: Set INFO[NEW]:=ITEM
• Step 4: Set LINK[NEW]:=LINK[LOC]
Set LINK[LOC]:=NEW
• Step 5: Return
 Insertion in a sorted circular header linked list
Algorithm: INSSRT(INFO,LINK,START,AVAIL,ITEM)
This algorithm inserts an element in a sorted circular header
linked list
Step 1: If AVAIL=NULL, then
Write: ‘OVERFLOW’
Return
Step 2: Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
Step 3: Set INFO[NEW]:=ITEM
Step 4: Set SAVE:=START and PTR:=LINK[START]
Step 5: Repeat while PTR≠START and ITEM <=INFO[PTR]
Set SAVE:=PTR and PTR:=LINK[PTR]
[End of Loop]
Step 6 : Set LOC:=SAVE
Step 5: Set LINK[NEW]:=LINK[LOC]
Set LINK[LOC]:=NEW
Step 6: Return
 Deletion from a circular header linked list
Algorithm: DELLOCHL(INFO,LINK,START,AVAIL,ITEM)
This algorithm deletes an item from a circular header linked list.
• Step 1: Set SAVE:=START and PTR:=LINK[START]
• Step 2: Repeat while INFO[PTR]≠ITEM and PTR≠START
Set SAVE:=PTR and PTR:=LINK[PTR]
[End of Loop]
• Step 3: If INFO[PTR]=ITEM, then:
Set LOC:=PTR and LOCP:=SAVE
Else:
Set LOC:=NULL and LOCP:=SAVE
[End of If Structure]
• Step 2: If LOC=NULL, then:
Write: ‘item not in the list’
Return
• Step 3: Set LINK[LOCP]:=LINK[LOC] [Node deleted]
• Step 4: Set LINK[LOC]:=AVAIL and AVAIL:=LOC
• [Memory retuned to Avail list]
• Step 5: Return
 Doubly Linked List: Two-way List
• A two-way list is a linear linked list which can be traversed in two
directions: in usual forward direction from beginning of the list to end
and in backward direction from end of list to the beginning. Thus,
given the location LOC of a node N in list, one has immediate access
to both the next node and the preceding node in the list.
• Each node of a two-way list is divided into three parts:
– An information field INFO which contains data of N
– A pointer field FORW which contains the location of next node in
the list
– A pointer field BACK which contains the location of preceding
node.
The list also requires two list pointer variables FIRST which
points to first node in the list and LAST which points to the last node
in the list. Thus null pointer will appear in FORW field of last node in
list and also in BACK field of first node in list.
• Two way lists are maintained in memory by means of linear arrays in
same way as one way list except that two pointer arrays , FORW and
BACK , are required instead of one list pointer variable. The list
AVAIL will still be maintained as a one-way list.
LAST
FIRST

FORW[PTR]
BACK[PTR]
• Trailer node- A trailer node is like a header node in a linked list except
that it stores the address of the last node in a linked list. The
significance of this node is in a doubly linked list that can be traversed
in both the direction. In doubly linked list, we can take the advantage
of trailer node in searching a node in a sorted doubly linked list. The
search will be more efficient.
 Operations on a Two-way list
• Traversal
• Algorithm: Traversal
This algorithm traverses a two-way list. FORW and BACK
are the two address parts of each node containing the address
of next node and previous node respectively. INFO is the
information part of each node. START contains the address
of the first node
Step 1: Set PTR:=START
Step 2: Repeat while PTR≠ NULL
Apply PROCESS to INFO[PTR]
Step 3: Set PTR:=FORW[PTR]
[End of Step 2 Loop]
Step 4: Exit
• Algorithm: SEARCH(INFO,FORW,BACK,ITEM,START,LOC)
This algorithm searches the location LOC of ITEM in a two-
way list and sets LOC=NULL if ITEM is not found in the list
• Step 1: Set PTR:=START
• Step 2: Repeat while PTR≠NULL and INFO[PTR]≠ITEM
Set PTR:=FORW[PTR]
[End of Loop]
• Step 3: If INFO[PTR]=ITEM, then:
Set LOC:=PTR
Else:
Set LOC:=NULL
• Step 4: Return
• Algorithm:INSRT (INFO,FORW,BACK,START,AVAIL,LOCA, LOCB, ITEM)
This algorithm inserts an item in a doubly linked list.
LOCA and LOCB location of adjacent nodes A and B
• Step 1: [OVERFLOW] If AVAIL=NULL, then:
Write: OVERFLOW
Return
• Step 2: Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
Set INFO[NEW]:=ITEM
• Step 3: Set FORW[LOCA]:=NEW and BACK[NEW]:=LOCA
Set FORW[NEW]:=LOCB and BACK[LOCB]:=NEW
• Step 4: Return
• Algorithm: DELETE(INFO,FROW,BACK,START,AVAIL,LOC)
This algorithm deletes a node from a two-way list
• Step 1: If LOC=START , then:
START:=FORW[START]
BACK[START]:=NULL
Return
• Step 2: [Delete node] Set FORW[BACK[LOC]]:=FORW[LOC]
Set BACK[FORW[LOC]]:=BACK[LOC]
• Step 3: [Returning node to AVAIL]
Set FORW[LOC]:=AVAIL and AVAIL:=LOC
• Step 4: Return
Algorithm: DELETE(INFO,FROW,BACK,START,AVAIL,LOC, BACK[START]:=NULL
ITEM) Return
[This algorithm deletes a node from a two-way list when • Step 6: [Delete node]
item to be deleted is given]
Set FORW[BACK[LOC]]:=FORW[LOC]
• Step 1: If START =NULL
Set BACK[FORW[LOC]]:=BACK[LOC]
Write: ‘Underflow’ • Step 7: [Returning node to AVAIL]
Return
Set FORW[LOC]:=AVAIL and AVAIL:=LOC
[End of If Structure] • Step 8: Return
• Step 2: Set PTR:=START
• Step 3: Repeat while PTR ≠ NULL and INFO[PTR] ≠ ITEM
PTR:=FORW[PTR]
[End of While Loop]
• Step 4: If PTR=NULL
Write : ’element already deleted’
Return
[End of If Structure]
• Step 5: If INFO[PTR]=ITEM
Set LOC:=PTR
[End of If Structure]
• Ste 5: If LOC=START , then:
START:=FORW[START]