U.

KUMARA SWAMY sC:

VYSHNAVI DEGREE COLLEGE, YMG.
Unit-I
Introduction: DATA STRUCTURES
"A data structure is a
computer so that can be used particular (way of store and organizing dat in
manage large amounts of data efficiently." Data structures provide a means toa
design efficient algorithms. efficiently. Efficient data structures are
a key to
Benefits:
Following time and space are two
dependent upon the structure of data.measurements for efficiency of program.
1. Space efficiency: This These are
is also referred as space
the amount of temporary complexity
amount of memory neededstorage required for running the of program. It indicates
2. Time efficiency: is also by the program to run to completion. program. ie., it is the
amount of time a programreferred
takes
as Time complexity of
program. It indicates the
Note that the time taken by a for execution.(Thai is how fast program is runs.
calculation. program for compilation is not
included in the
Data structures are important
for the following reasons:
1. Data structures are used
2. Specific data structures in almost every program or software system.
are essential ingredients
make possible the of many efficient
management
collection of databases. of huge algorithms, and
amounts of data, such as large
3. Some integrated
as the keyprogramming languages emphasize data
organizing factor in software design. structures, rather than algorithms,
Classification of Datastructures
Data Siucures

Primittve Data Structures

Nan-Pimitve Data Srucures
Integer Real Charscter Boolesn Inoar Deta Non-incar Data
Sucures Sructures
Arays Trses
unbed Ust
-Graphs
Scks

A
data structure can Quoues
be broadly classified into
(1) Primitive data structure
(ii) Non-primitive data structure

1| Page
 VYSHNAVIDEGREE COLLEGE, YMG
UKUMARA SWAMY MCA:
() Primitive data structure:
operated upon by machine level
The data structures that are directly
such as int, float, double, Boolean these
instructions ie. the fundamental data types
are known as primitive data structures.
(ii) Non-primitive data structure:
primitive, are called non-primitive data
The data structures, which are not
structures.
structures.
There are two types of non-primitive data items
Structure is said to be linear if its data
a. Linear Data Structure: A Data
address of first data item, then we can
form a sequence) That is if we know the
retrieve the second one, next third one and so on up to
the last item.
Ex: Arrays, Linked List, Stacks, Queues.
Dattye Array:- An array is group of similar type of data items.
only one link
Single linked list: -A linked list in which the node contains
field that point to the next node. node contains two link
Double linked list: - A linked list in which the
fields those are referred as previous and next fields.
Data structure. It is a
Stack: - It is also called as last-in-first-out (LIFO)
one end.
linear list in which insertion and deletion take place only atstructure. It is a
(FIFO) Data
Queue: - It is also called as first-in-first-out
once end and deletion takes
linear list in which insertion takes place at
place at other end. non-linear if its data
b. Non-linear data structure:- A Data Structure said to be
unique predecessor or unique
items do not form a sequence, ie., there is no
SuccesSor.
Ex: Trees, Graphs, Set
structures are
The frequently used non-linear data
together with finite set of directed
(a) Trees :-A tree is a finite set of nodes
edges that defines parent-child relationships
(vertices) which are connected
(b) Graphs: - graph is a finite set of nodes
with finite set of edges (arcs).
(Note draw diagrams for above linear and non-linear Data structures)
Concept of Abstract Data Type
Abstract Data Type (ADT)
operations that manipulate that data
In Object Oriented Programming data and the
are grouped tógether in classes or collections store data and allow
Abstract Data Types (ADTs) or data structures
it.
various operations on the data to acoSss and change (modify) are called member data,
The individual elements of the data structure of the ADT
and the operations of the ADT are called member functions.
Every Collection ADT should provide a way to: 300
Add an item
Renove an item
Find, retrieve, or access an item
Is the collection empty fictd

2|Page

VEOA XEFOX
 U.KUMARA SWAMY MCA VYSHNAVIDEGREE COLLEGE, YMG.

Make the collection empty

Give me a sub set of the collection
lots or
ADTs or Collection classes should be generic: only write them once, hold
all types of data.
Ex: AbstractDataType LinearList
elements
Instances: ordered finite collections of zero or more
Operations:
otherwise
empty(): return true if the list is empty, false
list.
size( ): return the list size i.e number of elements in the
getindex): returns the indexth elements of the
list.
indexOf(x): return the index of the first occurrence of x in the
list,
returns -1 if x is not in the list.
their index
erase (index); remove/delete the indexth element and
reduced by 1.
insert(index, x): insert x as the indexth element
and their index
increased by 1.
output( ): display the list of elements from left to right.

Storage structures
The main purpose for computer systems is to execute programs.
These programs together with the data they act upon, must be stored in main
memory during execution.
" Ideally, we would want the programs and data to reside in the main memory
permanently.
" However, this is not possible because
VThe main memory is usually too small to store all needed data permanently.
The main memory is a volatile storage device that looses its content when
power is turned off or lost.
Since large data sets cannot fit into main memory, secondary storage structures are
necessary to handle such data.
Magnetic disk is the most common form of secondary storage in computer systems.
With storage structures, a small portion of the data is kept in primary storage, and
additional data read from secondary storage as needed.
A data storage structures is a means of organizing data as blocks in secondary
memory that optimizes I/O read/write operations.
Data storage structures include: Sequential files, Random access files, Indexed files.

3 | Page

VEOANRN
U.KUMARA SWAMY MCA: VYSHNAVI DEGREE COLLEGE, YMG.

ile Structures
Afile is a collection of data stored on mass storage (hard disk, tapes, CD/DVD).
A file is a collection of records. The data in File is subdivided into records. Each
record contains a number of fields. One (or more) field is the key field. Key field is
used to uniquely identify the particular record in the file.
Key field Field

S.no S.name Percentage

AAA 80% Record
111
112 BBB 90%
113 CCC 95%
Methods to accessing files:
> Sequential files
Indexed files
Hashed files.
Sequential File:
the form of an array, or alinked list of
A very natural way to store a file is in
entire file may be traversed in a linear
the records. In these representations, the simple to implement and can
fashion. This file structure is called sequential file. It is
be economic in space.
a file are likely to be
On the negative side, most search operations in such
inefficient, since searching requires traversing of the sequence of records according
particularly when the file is in disk,
to the storage sequence. In case of large files,
such traversal times can be too long.
Indexed Sequential File:
file structures, indexed
To overcome the shortcomings of the sequential like in a
of the file are stored
sequential file structure is used. In this the records maintained.
records is (are)
sequential file. But in addition to this, some index of the
_address) pairs. The index is
An index is a collection of (key_value, record
represented using a separate data structure. A search
for a record using a key field
Once the index entry is
shall now be carried out in the index based on that key value.
directly access the
located, the record_address part of the entry can be used to
record. File
File
Keys Address
1 10
15 10
2
3 20
20

4|Page

VEÜAXEROX
 U.KUMARA SWAMY MCA: VYSHNAVI DEGREE COLLEGE, YMC

Hashed Files
An alternative to storing the index as a hash table is to not have an index at all.
Instead, hash on the key to find the address of the desired record and use open
addressing to resolve collisions.
Files

1
Address hash
Key
function(Key)
10

20

Linear Lists
elements. The linear list is
The data structure linear list is an ordered collection of
number; the index of e, is i:
in the form eo, e1, ez...., en-1 Where 'n' is a finite natural
and n is the list length or size.
When n0, the list is empty. When n>0, eo is the zeroth element and en- is the last
element of the list.
Some examples of linear list are
1. An alphabetized list of students in a class
2. A list of exam scores
3. Alist of gold medal winners in the Olympics.
Operations on linear list:
> Creating a linear list
> Destroy a linear ist
> Determine whether the list is empty
> Determine the size of the list
> Find the alement with a given index.
> Find the index of a given example.
> Delete,erase or remove an element given its index
> Insert a new element so that it has a given index.
> Output the list elements in order, from left to right.
The Abstract Data Type of Linear List:
Alinear list may be specified as an abstract data type (ADT) in which we provide a
specification of the instance as well as of the operations that are to be performed.
AbstractDataType LineatList

Instances: ordered finite collections of zero or more elements

Operations:
enpty( ): returm true if the list is empty, false otherwise
5|Page
 VYSHNAVI DEGREE COLLEGE, YMG.
U.KUMARA SWAMY MCA
size( ): return the list size i.e number of clements in the list.
get(index): returns the indexth elements of the list.
indexOf(x): return the index of the first occurrence of x in the list, returns -1 if
x is not in the list.
erase(index): remove/ delete the indexth element, elements with higher index
have their index reduced by 1.
insert(index, x): insert x as the indexth element, elements
with index>= index
have their index increased by 1.
output(): display the list of elements from left to right.

POINTERS
another variable.
Pointer pointer is a variable that can hold the address of
Accessing the address of a variable:
dependent and therefore,
The actual location of a variable in the memory is system
We can access the address
the address of a variable is not known to us immediately.
of a variable by using address operator &.The operator & immediately preceding
with it.
a variable returns the address of the variable associated
e.g: p-&x;
elements.
The address operator can be used only witha simple variable or array
Declaring pointer variables:
type. Since pointer variable
In program, every variable must be declared for its
declared as
contain address that belong to a separate data type, they must be
pointers before we use them.
The declaration ofa pointer variable takes the following form:
data_type "pt nane;
Eg int "p;
float *x;
declares the variable p as a pointer variable that points to an integer data type.
Remember that the type int refers to the data type of the variable being pointer to by
declares x
p and not the type of the values of the pointer. Similarly, second statement
as pointer to a floating-point variable.
Initializing of pointer variables:
The process of assigning the address of a variable to a pointer variable is known as
initialization of pointer variable.
Once a pointer variable has been declared we can use the assignment operator to
initialize the variable.
int quantity=10;
int "p: rdeclaration/
p-kquantity; /'initialization/
We can also combine the initialization with the declaration.

6 | Page

VECAX EROX
 VYSHNAVI DEGREE COLLEGE, YMG.
U.KUMARA SWAMY MCA
int 'y=&quantity:
For e-g: float a;
int x, "p:
p=&n; /wrong/
will result in wrong output because we are trying to assign the address of float
variable to an integer pointer.
Accessing a variable through its pointer:
Once a pointer has been assign the address of a variable, then we can access the
variable by using asterisk () operator, usually known as the indirection operator.
Consider following example
int num, "p,n;
num=179;
p=#
n=p:
The first line declares numn and n as integer variables and p as a pointer variable
pointing to an integer. The second line assigns the values 179 to num and the third
line assigns the address of num to the pointer variable p. The fourth line contains the
indirection operator ". When the operator *is placed before a pointer variable in an
expression, the pointer returns the value of the variable of which the pointer value is
the address. In this case, *p returns the value of the variable num, because p is the
address of num. the* can be remembered as 'value at address'.

ARRAYS REPRESENTATION
In an array representation, we use an array to store the list elements. We can
store several elements in single array. Individual elements of an array are located in
the array using a mathematical formula (mapping formula).
Suppose we decide to use a one-dimensional array to store the elements of
linear list. The array has positions (locations) element[0, element[1].
element[arayLength-1|where arrayLength is the length or capacity of the array.
Each array position can be used to store a single list element. We need to map the
elements of the list to positions in the array. The most natural mapping uses the
formula
location( i) =i
Above equation states that the j element of the list is stored in position i of the
array. Following fig shows the list [5, 2,4, 8, 7] is stored in array element using above
map equation. The length of array is 10, and the size of list is 5.
element (0] [1J (2] 3) 14 5) 16) 7 (8] 19)
5 2 4 8 7

7|Page

VEOAXEROX
U.KUMARA SWAMY MCA: VYSHNAVIDEGREE COLLEGE, YMG.
In our array representation of a linear list, here listSize shows number of.
elements currently in the list, and a variable arrayLength shows the capacity of the
array element.
To insert an element in ith position, we must first move the existing all elements to
its right one position and then put the new element into ih position of the array.
We may remove the e, from the list by moving elements to its left down by 1.
2. Multi Dimensional arrays:
Multi dimensional array represernts 2D,3D..arrays which are combination of two or
more one dimensional arrays.
Now we study about only two dimensional arrays.
Two Dimensional arays (2D): Two dimensional arrays represent several rows and
columns of data. Two- dimensional arrays alternatively termed as matrices.
An example of an m xn matrix where m denotes number of rows and n
denotes number of columns is as follows:

a11 a12 a13 aln

a21 a22 a23 a2n

am1 am2 am3 amn

The subscript of any element a_ represent the ih row and jth column.
Memory representation of a matric
There are two conventions of storing any matrix in memory:
1. Row-major order
2. Colunn-major order.
In row-major onder, elements of matrix are stored on row-by-row basis, that is, all
the elements in first row, thern in second row and so on.
In column- major order, elements are stored column by column, that is, all the
elements in first column are stored in their order of rows, then in second column,
third column and so on.

a11 a11

E4 E
a12 az1

a13 a31

a21 a12

az2
a3 a32

a31 a13
a32
a33 a33

8|Page

VECIA>EROX
 U.KUMARA SWAMY MCA VYSHNAVI DEGREE COLLEGE, YMG.

Linked (List) Representation

"A linked list is a data structure consisting of a group of nodes which together
represent a sequence." Under the simplest form, each node is composed of a data
and a reference (in other words, a link) to the next node in the sequence.
In a linked representaion each element of an instance of a data object is
represented in a cell or node. Every node composed with two fields' data and Link.
Here data stores the actual information and lint or next field stores the address of the
next node in the linked list.
Let L=( eo, e, ez,..en1) be a linear list. In one possible linked representaion for
this list, each element e, is represented in a separate node. Each node has exactly one
link field that is used to locate the next element in the linear list. So the node for ei
links to that for e-1, 0sisn-l. The node for en-1 has no node to link to and so its link
field is NULL.
Here the first node is called as Head and last is Tail. The Tail node link field
contains NULL beacause of it doesn't have farther next node.
To locate the element ez, we must start at head node, then by linked we move to get
ez node. So which element may you find you must start from head itself only. Here
the links are shown as arrows.

head 2000 2800 1500 3600

2000+ 17 2800 92
15004 63 3600 45 null

There are two ways to represent a linked list in memory:

1. Static representation using array: in this a linked list maintains two arrays; one
array for data and other for links.
2. Dynamic representation using free pool of storage: in this method, there is a
memory bank (collection of free memory spaces) and memory manager (a program).
Whenever we create a node the request is placed to the nennory manager; the
memory manager will then search a space in memory bank and grant the permission
to use it.
ARRAYS
"An array is a collection of variables of the same type, referred to by a
common name." or "An array is a group of related data items that share a common
name." or "An array is a collection of similar elements."
Array ADT:
Each instance of an array is aset of pairs of the form (index, value)) No two pairs in
this set have the same index. The operations performed on the array follows:
Get an element: gets the value of the pair that has a given index.
Set an element adds a pair of the form (index, value) to the set, and if a
pair with
the same index already exists, deletes the old pair.
These two operations define the Abstract Data Type array(ADT)
AbstractDataType array
{
Instances: set of (index, value) pairs, no two pairs have the same index.
Operations:
9|Page
 VYSHNAVI DEGREE COLLEGE,YMG.
U.KUMARASWAMY MCA:
get(ndex): return the value of the pair with
this index
pairs, overwrite exiting pair if any with
the
set(index, value): add this pair to set of
same index

last week nmay be represented by

For Example, the high temperature for each day of
following array: 92), (Thursdny, 88), (Friday,
high= ( (Sunday, 82), (NMonday, 79), (Tuesday, 85), (Wednesday,
89),( Saturday, 91))
(day of week) and a value (the high
cach pair of the array is composed of an index is higlt. We can change the high
temperature for that day). The name of array
temperature recorded for Monday to 83 by performing following operation:
set(Monday, 83)
Mappings
A map is a data structure and it's majorly used for fast look ups or searching
data. It stores data in the form of key and valuejpairs where every key is mique.
have
Key and values could be almost of any data type. Generally you would first
storing
keys that are ints, floats, strings etc. A very simple example would be be strings and
names as keys and values as ids in a map. Names obviously would
id's would be ints.

Key Value
John 1
Peter 2
Sparse Matrix
Matrix: "an m x n matrix is a table with 'm' rows and 'n' columns. Here m and n are
dimensions of matrix"
A sparse matrix is a two-dimensional array having the value of majority elements as
null (zero).
1 7 0
0 6 0
2 0 5
3
In the large applications, sparse matrices are involved. By this we can reduce the
wastage of memory.
Applications: Large Database (LDB) accessing and storing. Scientific and
Engineering applications used for solve Partial Deferential Equations (PDE)
Some wel-known sparse matrices which are symmetric in form can be classified as
follows:
Sparse
Matrices(Symmetric)

Triangular matrices Band matrices

Lower Upper Dalgonal Trldiagonal aß-band

Lower-Left Lower-right Upper-left Upper-right

10 | Page
 U.KUMARA SWAMY MCA: VYSHNAVI DEGREE COLLEGE, YMG.

Wult CIemes

NulelerenlsNolelements

PPer-IefHHianyula vpperrigt
tiangulas Lower -eh# riasgulas
Nutl ClemeO
Null ClkmensNU! cemenh

Nt lenenk

touer-rigbt briangts Riagonal matrices.

Tidiagpnal maties. aB band matix

SET
Set: Set is a container of distinct objects.
When S is a set and x is anything, we can ask the question, "Is x a member of set S?"
The setS then consists of all those elements x for which x is a member of S. The
following points summarize some important notations for talking about sets.
1. The expression xE S means that the element x is a member of the set S.
2. If x1, X2,...,Xn are all the members of setS, then we can write
S= (x1, X2, ..., Xn}
Here, each of the x's must be distinct; we cannot repeat an element twice in a set.
However, the order in which the members of a set are listed is arbitrary.
1 There are no duplicate elements in a set.
2. There is no explicit notion of keys or even an order.
Examples:
1. Agroup of unique integers
2. Agroup of unique web pages
11|Page
 U.KUMARA SWAMY MCA VYSHNAVI DEGREE COLLEGE, YMG.

3. A
collection of unique books
4. Agroup of students
5. A hockey team
The Set Abstract Data Type(ADT):
fundamental methods acting ona
The set abstract data type supports the following
set A.
Abstract Data Type set

Instance: group of distinctobjects.

Operations:
assign AUB to A.
union(B): Replace A with the union ofAand B. that is,
intersect(B): and B, that is, assign AnBto A.
Replace A with the intersection of A A
-Bto A.
subtract(B): Replace A with the difference of Aand B, that is, assign

Operations on Sets:
Union of two sets A and B
A={3, 4, 2,1, 5) B=(6,7,3, 2, 4)
AUB = (1, 2, 3, 4, 5, 6, 7)
Intersection of two sets A and B
AnB = |2, 3, 4)
Subtraction of two Sets A and B
A-B= (1,5)
LINKED LISTS
which together
is a data structure consisting of a group of nodes
"A linked list of a data
simplest form, each node is composed
represent a sequence." Under the
the next node in the sequence.
and a reference (in other words, a link) to List, which composed with two fields' data
Linked
Node: "Node is building block of
and Link. " Linked list
Array a
Basis for Comparison fixed It is an ordered set consisting of
Basic It is a consistent set ofa variable number of data items.
number of data items.
Specified during declaration. No need to specify; grow and shrink
Size during excecution.
Element position is assigned during
Storage Allocation Element location is allocated during run time.
compile time. Stored randomly
Order of the elements Stored consecutively Traverse
Sequentially accessed, i.e.,
Accessing the element Direct or randomly accessed, i.e., node in the list
subscript.starting from the first
Specify the array index or by the pointer.
Slow relatively as shifting is Easier, fast and efficient.
Insertion and deletion
of element required. linear search
Binary search and linear search
Scarching More
Memory required less
Ineflective Efficient
Memory Utilization

12 |Page
 U.KUMARA SWAMY MCA: VYSHNAVI DEGREE COLLEGE,YMC.

Linked lists have following drawbacks:

1) Random access is not allowed. We have to access elements sequentially starting from
the first node. So we cannot do binary search with linked lists.
2) Extra memory space for a pointer is reguired with each element of the list.
3) Nodes are stored incontiguously, greatly increasing the time required to access
individual elements within the list. Difficulties arise in linked lists when it comes to
reverse traversing.
Types of Linked List:
Single Linked List(SLL)
Doubly Linked List(DLL)
Circular Liked List(CLL) eod,cle

Single linked list

"If Nodes in Linked List contain only one Link then, that Linked List is called Single
Liked List".
Singly linked lists contain nodes which have a data field as well as a next field,
which points to the next node in line of nodes. Operations that can be performed on
singly linked lists include insertion, deletion and traversal.
2000 2800 1500 3600
head
20004 17 2800 92 1500 63 3600 45 null

Singly Linked List operations:

1. Creation
2. Insertion (at starting, at middle, at end)
3. Deletion (1st node, middle node, last node) )
4. Traverse(Display)
1. Creation: First we create starting node and that node address is stored one
variable called head. Then next we link farther nodes to head node.
Implementation: define a class with two attributes one is data and another one is
link (next) reference object of class. The link reference object can stores address of
next node.
public class Node
public int data;
public Node next;

2. Insertion: Insertion means adding new nodes to Linked List. Insertion may
perform at starting, at ending, and at middle by user choice.
At staring First we assign the address of head node to next field of our newNode,
and then next we rename our newNode as a head.
At ending The next fied of tail node is actually contains null, now the address of
our newNode is link to tail node next field, and then rename our newNode node as
a tail.

13 | Page
 U.KUMARA SWAMY MCA VYSHNAVI DEGREE COLLEGE, YMG.

At middle(user choice): First we traverse up to previous position of node to be

inserted. And then newNode next field assign with address of current node's next
field and current node's next field link with our neoNode.
void insetAtMiddle) void
Inseting at middle: insertAtStarting)
34 76
head 45 65 current=head:
n=1;
new Node next=head
head=newNode,
while(n<choice-1)
P
newNode G 50 current=current.next;
void insertAtEnd)
n++;
34 76
tail.next=new Node,
head 5 newNode.next=current.next: tail=newNode;

current. next=newNode:

newNode 50

list. Deletion
3. Deletion: Deletion is nothing but removing node from linkedlast node, and
operation may perform in different positions like first node,
middle node by user choice.
is assign with lead's next
First node: when we want to delete first node head node
node.
node to tail node. Then current node's
Last node: First we traverse up to previous
is renamed as tail.
next field assign with null. And next current node
Middle(user choice): First we traverse up to
previous position of node to be
deleted. And then current node's next field
assign with address of current node's
next field of next.
34 76
head 45 65

void deleteMiddle)
void deleteFirst)
int n=1;
head=head.next; Current=head;
while(n<choice-1)

void dletelast) Current=current.next;

Current=head; Current.next=current.next.next;

while(curTent.next.next!=nulu)

CurrentCurrent.next;

Current.next=null;
tail=current;

pisp Linked List. From the head node

4. Traverse: Traverse means displaying the data in follows:
tillthe tail node we traverse by one reference object like current as
Doid traDerset )
Current=head;
while(current!=null)

14| Page
 U.KUMARA SWAMY MCA. VYSHNAVI DEGREE COLLEGE, YMG.

System.out.println(current.data);
Currenl=Currenl.next;

Double Linked List

"If Nodes in Linked List contain two Links then, that Linked List is called Doubly
Liked List"

first

In adoubly linked list, each node contains, besides the next-node link, a second link
field pointing to the previous node in the sequence. The two links may be called
forvards and backoards, or next and prev(previous).
Operations on Double Linked List:
1. Creation
2. Insertion (at starting, at middle, at end)
3. Deletion (1st node, middle node, last node) )
4. Traverse(Display)
1. Creation: First we create starting node and that node address is stored one
variable called head. Then next we link farther nodes to head node.
Implementation: define a class with three attributes one is data and another two
are prev and next reference object of class.
public class Node

public int data;

public Node preo;
public Node next;

2/ Insertion: Insertion means adding new nodes to Linked List. Insertion may
perform at starting, at ending. and at middle by user choice.
field of head, and then
At staring: First we assign the address of newNode to prev
newNode as a head.
head is assign to next field of newNode. Finally we rerame our
null, now the address of
At ending: The next field of tail node is actually contains
prev field
our newNode is link to tail node next field, and then tail is assign to the
of newNode. Finally we rename our newNode node as a tail.
position of node to be
At middle(user choice): First we traverse up to previous
current node and
inserted. And then newNode prev field assign with address of
newNode next field with address of current node's next field.
Finally current
And current node next field of prev is link with our newNode.
node's next field assign with newNode. void insetAtMiddie0 void insertAtStarting()
Inseting at middle: current=head; head.prev=newNode,
new Node .next=head,
n=1;
while(n<choice-1) head= new Node,

current=currentnext;
n++: void insertAtEnd()
tail.next=new Node,
newNode.prev=çurrent;
newNode. next = current.next; new Node.prev=tail,
current.next.prev=new Node; tail=new Node,
15 | Page current.next=new Node
U.KUMARA SWAMY MCA VYSHNAVIDEGREE COLLEGE, YMG.
newNode 6 null
5
|1 Tail
current
Head

node from linked list. Deletion

3. Deletion: Deletion is nothing but removing
positions hke frst node, last node, and
operation may perform in different
middie node by user choice

node when we want to delete first node head node is assign with head's next
First
null.
node and head node prer fekd is assign with node
umnt to tal node. Then curent node's
Last node First we take a reference qurnent node next field assign with
is assign with current node prer feld. And
null. And next cuent node is renamed as tail.
previous position of node to be
Middle (user choice): First we traverse up to arent node's next field of next.
with
deleted. And then here we temp is assign
Finally emp node prev held is
And arrent node's not field assign with temp.
assign with curment.
8 6
|1 5
current
temp/tail
Head

void deleteMiddle0
roid deletefirsto

mt n=l
hoad-head net unent-head;
head premnull.
ohile(n<choice-1)

Current=Current.next;
Dod ditdast)

tenp = urrent.net.next;
aTenttal

GTataTant pr, Current.next=lemp;

aTOtnezt-null Lemp prev=Current;
tail-urnnt,

can traverse
4. Traverse Traverse means displaying the data in Linked List. We
current as follows:
- bidirectional forroard and backvard by reference object like
doid backwardTra( )
Doid foroanTrat)
Curent=lail:
cuat-head:
hile(curent!mull) Lohile(curent!=null)

System ou printin(aurnentdala); System out.println(curent.data); )

urnantsaurrent.net; urrent=aurrent.prev;

kast nde ’first node

Circular Linked List
In the last node of a list, the link field often contains a null reference, a special value
used to indicate the lack of further nodes. A less common convention is to make it
point to fhe first node of the list, in that case the list is said to be 'circular r
'circularly linked'; otherwise it is said to be 'open' or 'linear.
16 | Page

VEOA XEROX
 U.KUMARA SWAMY uCA. VYSHNAAVI DEGREE COLLEGE, YMG.

Circular Single Linked List:

"A linked list in which the last node points to the frst node". It is convenient to make
first point to the last node

Circular Double Linked List:

Here note that the next field of last(tail) node and prev feld of first node contains the
address of the hender node; again the next and prev fields of the header node contains
the address of last and first node, respectively.
6
1
7
Operations on Circular Linked List
In circular linked list we can perform different operations like merging searchi

splitting, deletion, adding, and traverse. And we can also do the finding the element
in circular linked list. The following algorithm does the finding
Algorithm: Search(Key)
Input: KEY the item of search
Output: Location, the pointer to a node where KEY belongs or an error message
Data structure: A single linked ist whose address of the starting node is known as
from HEADER.
Steps:
current=HEADER. next
While (current !=NULL) and (current!=HEADER) do
Current=current.next
EndWhile
If (current. data=KEY)
prínt " Key is Found"
Else
Prínt entire list is searched : KEY node 1s not found"
EndIf
Stop
Above algorithm searches the KEY in the circular linked List If KEY is found display
it otherwise the error message willbe displayed.

17 |Page
 U.KUMARASWAMY MCA VYSHNAVI DEGREE COLLEGE, YMG.

Applications of Linked List

Linked list contains many applications in implementation of Data structures like
stack, queue, tree, graph and different sorting. Apart these we have some
applications as below mentioned:
1. A polynomialcan be represented in a linked list bysimply storing the coefficicnt
and exponent of each term. Polynomial manipulations such as addition, subtraction,
multiplication etc., can easily implement using linked list. by
2. Memory management: linked lists are very much useful in managing memory
its dynamic nature.
3. Arithmetic on large number: we face problems when the large numbers are
added or multiplied the length of the number may cross the limils since its
requirement known only atrun-time. Using linked list may be a good solution.
4. Symbol table implementation: symbol table are used in compiler construction
and related areas, these are like dictionaries containing name and their associated
values. The symbol table can be efficiently designed with linked lists.
5. Representing Sparse matrices: In the large applications, sparse matrices are
involved. By this we can reduce the wastage of memory. These sparse matrices are
implemented by using linked list efficiently.
Doublg
lirl cd

18 | Page

VECAXERX
 L.KUMARA SWAMY MCA VYSHNAVIDEGREE COLLEGE, YMG.

Unit-V
SORTING AND SEARCHING
Sorting, a set of items into order is very common task in computer science. Arrang1ng
le clements in ascending order or descending order is called as Sorting
Sorting takes an unsorted collection and makes it an ordered one. Sorting is based on
the comparison between 2 items.
Ingeneral complex data can be compared and sorted in many ways (algorithms) to
sort the elements. Such algorithms are:
1. Selection sort
2. Insertion sort
3. Bubble sort
4. Merge sort
5. Quick sort
6. Heap sort
1. Selection Sort
Selecetion sort is used arranging the elements in ascending order. The idea behind the
selection sort is that we put a list in order by placing each item in turn. In other
words, we put the smallest item at the start of the list then the next smallest item at
the second position in the list and so on until the list in order.
Steps involves in selection sort:
> Choose the largest/smallest element by comparing with all elements in the array
and place the element in its correct place.
> In every iteration one element will sorted.
> Repeat the process until all items are sorted.
1" Iteration 2nd Iteration 3nd Iteration 4tn Iteration

1 1 1 1

6 6 2 2 2
5 5 4 4

2 2 6 5

4 4 4 5 6

Best case: When the given list is already sorted, in this case the number of swaps is
zero.

Worst case: When the first item in the list is the largest and the rest of the list is in
order. In this case, we perform one swap on each pass.
Average case: Average case is also same as the best case.
Disadvantage: It is not stop early, if the list is sort. It looks at every element in the
list.

2. Insertion sort
Insertion sort is simple sort algorithm. Insertion Sort is used for arranging the
elements in ascending order.
Steps involves in insertion sort:

19 | Page
U.KUMARA SWAMY MCA VYSHNAVI DEGREE COLLEGE, YMO
element in each iteration and place it to a
V Insertion sort algorithm takes one
appropriate place. finds the place.
It checks the value with its preceding elements and
selected element is larger, it leaves the element in place, and moves to th.
If
next element.
elements one step next to make
V If selected element is smaller, shifts all larger
hole and insert the selected element in correct position.

E.x: 6

4 6 1 3 1|3

2 5 6
2 4 6 3
25 4 6 13

2 4 5 1 3
2
2 4
2 4 5 6 3
2 3 4

- 2 456 3
2 4 5 6 3
2 3 4 5 6

1 2 3 4 5 6 12|45|6
Cases for insertion sort:
Best case: When an array is already sorted, in this case the algorithm has to only
iterate over the list to check each element. No shifting will be made for the already
sorted array.
Worst case: When an array is sorted in reverse order, in this case the algorithm has
to iterate over the list to check each element. The shifting will be made after
comparing each element to n elements (total elements).
Average case: Insertion sort is impractical for sorting large arrays.
Advantages:
For small data lists insertion sort is known as one of the best algorithm in respect
to simplicity, stability and memory usage.
Insertion sort is the fastest algorithm for small data lists even faster than quick
Sort.

It requires fewer comparisons than bubble sort.

Disadvantage:
20| Page

VEæA >EROX
 U.KUMARA SWAMY MCA. VYSHNAVIDEGREE COLLEGE,YMG.

data lists
Insertion sort does not give better result in big

3. Bubble sort
order. Bubble sort is also known as
Bubble sort is to place elements in ascending
sinking sorl.
Steps involves in Bubble Sort:
1. In this algorithm, we keep comparing the adacent pair.
2. If they are not in right order, then swap them each other position.
3. When there are no elements swapped in one full iteration of element list, then it
indicates that bubble sort is completed.

15|3|17 4 1 3|15 4 1 173|4|1|15173|1|4 15 17

3 1517 4 1 |315 4 117 34|1| 15 1713415 17

3 15 17| 4|1 3 4 15 1 17 3 1415|17

3 15 4 17| 1 | 3 4 115 17 |
3 15 4 1 17
1st Iteration 2nd Iternation 3rd Iteration 4th Iteration

Cases:
Best case: It occurs when the list is already sorted.
Worst case: It occurs when the list is in reverse order.
Average case: It is similar to worst case.
Advantages:
It stops once, it determines that the list is sorted.
V It is good to use for small number of input elements (less than 1000).

4. Merge Sort
Merge sort was invented by John Neumann in the year of 1945. Merge sort is a neat
algorithm because "it is the sort that sorts recursively. It requires very few
comparisons and swaps. It relies on "divide and conquer" strategy.
Performance
Merge sort starts by dividing the given list in half. Again it divides each halves in
halí. The algorithm repeats until all of the sub-ist (sub-arrays) has exactly one
element in them.
Merge sort can be completed in three steps, are:
1. Divide
2. Conquer
3. Merge
Divide: Dividing the array in half forming two sub-arrays.

21 | Page

VEOAXRY
 VYSHNAVIDEGREE COLLEGE,
YMG.
U.KUMARA SWAMY MCA:
one
Dividing all the sub-arrays until, all the sub-arrays has exactly
Conquer.
sub-arrays have a single element.
element in them and stopping when the
(combine;: The sub-arrays are gradually merged back together, until we get
Merge
our original list with sorted order.

3243
10
se27
43

10
27 38

273843
10273843 82
+last)/2 and the number of swaps
The number of comparisons in this sort is (first
the indexes of the first and last
indicates
is 2(last-first+1). Where first and last
elements of the array respectively.
5. Quick sort
In fact quick sort is very fast sorting
It arranges the elements into ascending order.it works
algorithm It is bit tricky to understand, but very well. It was invented by
CARHoare in 1960.
one element in the list as
1. The basic idea behind the quick sort is speify any swapping items that
"pivot point Then go through all of the elements in the list
are on the wrong side of the pivot.
smaller than pivot to the left and the
2 In other words, swap the elements that are
elements that are larger than pivot to the right.
whatever it belongs in
3. Once you were done all possible swaps, move the pivot to
the list.
Next, select any
4 Now, we can ignore the pivot since it is in the right position
element as pivot point and repeat the same process.
pivot
7 5 1 2

2 1(P) 5 8 7

1 8 (p) 5 7 2
2 5

CASES: Best case occurs, when the list is already sorted. For this quick sort
algorithm, the best case resembles the average case in terms performance. That D

22 | P age

EAEROX
 U.KUMARA SWAMY MCA: VYSHNAVIDEGREE COLLEGE, YMG.
number of comparisons in best case is as same as average case but differs in swaps.
We have no swaps tor best case, but for the average case.
Worst case occurs when the pivot is always largest or smallest elements on each pass
through the list.
6. Heap sort
Heap sort was invented by J. W. J. Williams in 1964.
Heap Property: Alnodes are either (greater than or equal to] or [less than or equal to]
each of its children. If the parent nodes are greater than their children, heap is called
a Max-Heap, and if the parent nodes are smaller than their child nodes, heap is
called Min-Heap.
Steps involved in the Heap sort:
First we built the max heap.
Swap the first element of list to last. Decrease the range of list by one.
Sift the néw element to its appropriate index in the heap tree.
Repeat the process until the range of list is one element.

36 15 | 2
nc d c

ed

6 5 132 2 5 1 36

5 3 1 2 6
2 3 1 5 6

3
156 1 2 3 56

35 6

23 | Page
|1|23 5 6

VEDA XEROX
 U.KUMARA SWAMY MCA VYSHNAVI DEGREE COLLEGE, YMG.

SEARCHING
finding for the
Searching means finding. In java searching is nothing but that we do every
elements in the prescribed collection. Searching is the regular taska common task in
elements) is
day. In the same way searching for items (array
computer programs.
In java, they are two types of searching algorithms. They are
1. Sequential Search
2. Binary search
Sequential Search: most
search algorithm is Linear Search. A Linear search is the
The simplest
Sequential Search is also known as
Linear search. The
basic of all search algorithms. easy to
about the linear search is that it is easy to work with and
good thing
understand.
element in the list sequentially until the desired
>It is a process that checks every
element is found. element
element is present in the given list we compare search
To check if an
with every element in the list. doesn't contain the
number is found, success occurs otherwise the list
> If the our search fails.
required element which we are searching for. It means
Example:
integers in an array:(1,2,3,4), we want to find 2 in the
Suppose we have a list of four
list. i.e., Our search
to the algorithm, we start at the first item in the list, Then
to 1. Here it does not match.
According
is1. Now we compare 2
term is2 and array item with second array item 2 in the list. We
another comparison i.e.,
we will go for the is found. It means the specified number
is found,
compare 2 to 2. Here our
match
go
the second comparison, we will
Success OCCurs.

our match is not found in

In case the list. After
comparison. It repeats up to the last item in
through another number is still not found,
comparisons in the list, if the required
completion of all
fails.
then we will consider it as search
Performance of Sequential Search: number of
comparing search algorithms, we only look at the
When
comparisons. There are three cases:
1. Best Case: The
the array.
best case oCcurs when the search term is in the first slot in
The
number comparisons in this case are only
one.
the
occurs whern the search term is in the last slot in
2. Worst Case: The worst case equal to tne
number of comparisons in this case is
array, or is not in the array. The worst
items, then it takes N comparisons in the
size of the array. If our array has N
case.
3. Average Case: numnber of
the search term is somewhere in the middle of the array. The
On average,
comparisons in this case is approximately N/2.
Benefits of Sequential Search:
. Linear search don't require the collection to be sorted.

24 | Page
 U.KUMARA SWAMY MCA. VYSHNAVI DEGREE COLLEGE, YMG.

Lincar search is easy to work with.

Linear search is easy to understand.
Drawbacks of Sequential Search:
Sequential search has an average and worst-case performance.
o It is a slow process when compared to rest of search algorithms.
o It takes huge comparisons than binary search.
BINARY SEARCH
Binary search is also known as half interval search. This search algorithm use
the ordering of a list.
The idea behind the binary search is that each time we make a comparison, we
eliminate half of the list, untilwe either find the search term or determine that the
term is not in the list.
YWe do this by looking at the middle item in the list, and determining if our search
term is higher or lower than the middle item.
Ifit is lower, we eliminate the upper half of the list and repeat our search starting
at the point half way between the first item and the middle item.
/ Ifit is ligher, we eliminate the lower half of the list and repeat our search at the
point half way between the middle item and the last item.
Performance of Binary Search:
The best case for binary search still occurs when we find the search term on
the first try. In this case, the search term would be in the middle of the list.
The worst case for binary search occurs when the search term is not in the list,
or when the search term is one item away from the middle of the list or when the
search term is the first or last term in the list.
Example:
Suppose we have a ist of four integers (1,4,5,6}. We want to find 2 in the list.
According to the algorithm, we start the second itemn in the list, which is 4. Our
search term is 2, is less than 4, so we throw out the last three items in the list
and
concentrate our search on the frst item on the list, 1. We compare 2 and 1, and find
that 2 is greater than 1. at this point there are no more items left to search. So we
determine that 2 is not in the list.
Benefits of Binary Search:
1. It isa fast process when compared to the rest of all search algorithms.
2. Binary search is much more efficient than the linear search.
3. It takes less comparisons to search when compared to the linear search.
4. Every iteration eliminates half of the remaining possibilities. This makes binary
search very efficient even for large collections.
Drawbacks Of Binary Search:
1. Binary search always requires a sorted collection.
2. Binary search somewhat complicated when compared to sequential search.

25 | Pa ge