UNIT 1 DS Ai& ds
UNIT 1 DS Ai& ds
UNIT 1 DS Ai& ds
UNIT-I
4 MARKS
Data is derived from a Latin word “datum” which means collection. So, data can be defined as
collection of facts and figures. A data item refers to a single unit of values. Data is classified into two
types:
1. Group data item
Data item that can be subdivided into different segments is called group data item. For
example: name is a group data item because it can be subdivided into different segments, i.e. first
name, middle name and last name.
2. Elementary data item
The data item that cannot be subdivided into different segments is called elementary
data item. For example: account no, ID number, etc
Field
Record
File
Data item
Attribute and entity
Entity set
Elementary item
Data
3. Define data structure and mention the need for data structure
Data structure is a way of organizing all data types in order to represent the logical
relationship between existing elements of data.
In other words, data Structure is a systematic way to organize data in order to use it efficiently.
DATA STRUCTURES
Primitive Non-primitive
or
composite
Linear Non-Linear
An array is a set of finite number of data items of same type. It means an array can contain one
type of data only, either all integers , all floating numbers or all characters. It is stored in consecutive
memory locations.
In other words Array is a group of related data items,that share a common name with same data
type. An individual variable in the array is called an array element.
We can define an arrayname, rollno to represent a set of roll numbers of a group of students.
A particular value is indicated by a number called index number.
An index number is present in brackets after array name.
Array size
Array name
Data type of array elements
Example:
6 MARKS
Traversing:
Accessing each record exactly once so that certain items in the record may be processed. (this
accessing or processing is sometimes called ‘visiting’ the records)
Searching:
Finding the location of the record with a given key value, or finding the locations of all records,
which satisfy one or more conditions.
Sorting:
The arrangement of data in ascending or descending order is called sorting.
Insertion:
Adding new record to structure is called inserting.
Deletions:
Removing a record or set of records from data structures is called deletion process.
Merging:
When two or more than two records are combined, this process is called merging.
Copying:
The creation of duplicate data item is called copying process.
Advantages of ADT
ADT is reusable and ensures robust data structure.
It reduces coding efforts.
It specifies error conditions associated with operations.
Elementary data item: The data item that cannot be sub divided into different segments is called
elementary data item.
Example :account no, id number, etc
Data− Data are values or set of values.
Data Item − Data item refers to single unit of values. EX : roll number, name, address etc
Group Items − Data items that are divided into sub items are called as Group Items.
Elementary Items − Data items that cannot be divided are called as Elementary Items.
Attribute and Entity − An entity is that which contains certain attributes or properties, which
may be assigned values. For example : student is an entity. The attributes of the student may be
roll number, name ,address etc
Entity Set – Entities of similar attributes form an entity set.
Field – Field is a collection of related characters. Field is a single elementary unit of information
representing an attribute of an entity.
Record − Record is a collection of field values of a given entity.
File − File is a collection of records of the entities in a given entity set.
5. Define data structures .Mention the characteristics and a need for data structure
Data structure is a way of organizing all data types in order to represent the logical
relationship between existing elements of data.
In other words, data Structure is a systematic way to organize data in order to use it efficiently.
Interface -Each data structure has an interface. Interface represents the set of operations that a data
structure supports. An interface only provides the list of supported operations, type of parameters they
can accept and return type of these operations.
Implementation − Implementation provides the internal representation of a data structure.
Implementation also provides the definition of the algorithms used in the operations of the data
structure.
10 MARKS
DATA STRUCTURES
Primitive Non-primitive
or
composite
Linear Non-Linear
Primitive data types are the data types available in most of the programming languages.
These data types are used to represent single value.
It is a basic data type available in most of the programming language.
when the data is to be stored in the memory in linear form, it is called as linear data structure
Linear data structure traverses the data elements sequentially.
In linear data structure, only one data element can directly be reached.
It includes array, linked list, stack and queues.
Types Description
Arrays Array is a collection of elements. It is used in mathematical problems like matrix,
algebra, etc. Each element of an array is referenced by a subscripted variable or
value, called subscript or index enclosed in parenthesis.
Linked list Linked list is a collection of data elements. It consists of two parts: Info and link.
Info gives information and link is an address of next node. Linked list can be
implemented by using pointers
Stack Stack is a list of elements. In stack, an element may be inserted or deleted at one end
which is known as top of the stack. It performs two operations: push and pop. push
means adding an element in stack and pop means removing an element in stack. It is
also called Last-in-First-Out (LIFO).
Queue Queue is a linear list of element. In queue, elements are added at one end called rear
and the existing elements are deleted from other end called front. It is also called as
First-in-First-out (FIFO)
Type Description
Tree Tree is a flexible, versatile and powerful non-linear data structure. It is used to represent
data items processing hierarchical relationship between the grandfather and his children &
grandchildren. It is an ideal data structure for representing hierarchical data.
Graph Graph is a non-linear data structure which consists of a finite set of ordered pairs called
edges. Graph is a set of elements connected by edges. Each elements are called a vertex
and node.
Asymptotic analysis are input bound i.e., if there's no input to the algorithm it is concluded to
work in a constant time. Other than the "input" all other factors are considered constant.
Big- Oh notation:
A function t(n) is said to be ain O(g(n)) denoted t(n) ε O(g(n)), if t(n) is bounded above
by some constant multiple of g(n) for all large n, i.e., if there exists some positive constant c and
some non negative integer n0 such that
T(n)≤c g(n) for n≥n0
// PUSH operation
public void push(int element) {
if (top < maxSize - 1) {
stack[++top] = element;
System.out.println("PUSHED: " + element);
} else {
System.out.println("STACK OVERFLOW");
}
}
// POP operation
public int pop() {
if (top >= 0) {
System.out.println("POPPED: " + stack[top--]);
return stack[top + 1];
} else {
System.out.println("STACK UNDERFLOW");
return -1;
}
}
// PUSH operations
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.push(50);
// Print stack
stack.printStack();
// POP operations
stack.pop();
stack.pop();
stack.pop();
// Print stack
stack.printStack();
Output:
PUSHED: 10
PUSHED: 20
PUSHED: 30
PUSHED: 40
PUSHED: 50
STACK ELEMENTS:
10 20 30 40 50
POPPED: 50
POPPED: 40
POPPED: 30
STACK ELEMENTS:
10 20
POPPED: 20
POPPED: 10
STACK UNDERFLOW
STACK UNDERFLOW
STACK IS EMPTY
DATA STRUCTURES
Primitive Non-primitive
or
composite
Linear Non-Linear
Array:
An array is a set of finite number of data items of same type. It means an array can
contain one type of data only, either all integers , all floating numbers or all characters. It is
stored in consecutive memory locations.
The general format is : type variable - name[size];
Array size
Array name
Data type of array elements
Example:
M[0] M[1] M[2] M[3] M[4] M[5] M[6]
Mar
k
2300 2302 2304 2306 2308 2310 2312
Linked list:
A linked list, or an one-way list, is a linear collection of data element, called nodes,
where the linear order is given by means of pointers. That is, each node is divided into two
parts.
The first part contains the information of the element i.e., INFO or DATA.
The second part contains the link field, which contains the address of the next node in
the list.
NODE
INFO LINK
The linked list consists of a series of nodes, which are not necessarily adjacent in the
memory.
Example: The linked list with 4 nodes.
7
5 8 9
Start
Or
Head Info field Link field
Stack:
A stack is a linear data structure, also called a last in first-out (LIFO) system , in which
insertions and deletions can take place only at one end, called top. i.e., the elements are
removed from the stack in then reverse order of that in which they were inserted into the stack.
A stack is a limited access data structure-elements can be added and removed from the stack
only at the top.
A stack consists of two operations:
a) Push
b) Pop
Push: It adds the element into the stack
Pop: It removes the element from the stack
push pop
top
Queue:
A queue is a linear data structure which is also called a first-in first-out (FIFO) system,
since the first element in queue will be the first element out of the queue.
In queue deletions can take place only at one end of the list, the “front” of the list, and
insertions can take place at other end of the list, the “rear” of the list.
The front and rear are two terms used to represent the two ends of the list when it is
implemented as queue.
Eg: This structure operates in much the same way as a line of people waiting at a bus
stop. The first person in line is the first person to board the bus. Another analogy is with
automobiles waiting to pass through an intersection- the first car in line is the first car through.
Dequeue(Deletion)
Enqueue(Insertion)
Front rear
When the data is to be stored in the computer memory in dispersed order, it is called as non-
linear data structure.
Non-Linear data structure is opposite to linear data structure.
In non-linear data structure, the data values are not arranged in order and a data item is connected
to several other data items.
It uses memory efficiently. Free contiguous memory is not required for allocating data items.
It includes trees and graphs.
Graph:
A graph is a non-linear data structure, which is having a point to point
relationship among the nodes. Each node of the graph is called a vertex and link or line
between them is called and edge.
A graph G is an ordered pair of sets (V,E) where V is a set of vertices and E is a set of
edges.
V={v1, v2,....,vn} is a set of vertices
E={e1,e2,.....,em} is a set of edges
V1 node
e1 e2
e5
V2 V3 V5
e3 e4 edge
V4
Tree:
Its is a non-linear data structure. The tree is used to represent the hierarchical relationship
between the data items.
Tree is a data structure that is hierarchical in nature.
A tree, is a finite set of nodes together with a finite set of directed edges that define parent-child
relationships.
Each directed edges that define parent-child relationships. Each directed edge connects a parent
to its child.
For example,
E B
D C F H G
Nodes={A,B,C,D,E,F,G,H}
Edges={(A,B),(A,E),(B,F),(B,G),(B,H),(E,C),(E,D)}
EX: Suppose we have an array of size 10 and assume elements stored are 1,2,3,23,34,54,56,21,32,33
and assume we want to search the number 23. So here the number 23 is key element. The key is
searched through the array starting from the first element till end. When it is compared with the fourth
element in it is present in the list (array) of numbers. So search is successful. This type of searching is
called linear search. In order to apply linear search, the list may not be in any particular order but when
binary search is applied the list must be ordered one.
Sorting:
The arrangement of data in ascending or descending order is called sorting. The sorting can be
done using insertion, selection or bubble sort technique.
EX : Suppose we have an array of size 10 and assume elements stored are 1,2,3,23,34,54,56,21,32,33.
The elements of the array are not in proper order. If they are arranged in ascending order the list
(array) becomes 1,2,3,21,23,32,34,54,56.
Insertion:
Adding new record to structure is called inserting. The element can be added anywhere in the
data structure.
EX: Suppose we have an array of size 20 used to store marks obtained by the students in computer
science subject. If we have already added 15 students marks according to an ascending order, then we
can add another student marks at appropriate place, by shifting the already stored element accordingly.
Then it is called insertion operation.
Deletion:
Removing a record or set of records from data structures is called deletion process. We can
delete an element from data structure from any position
.
EX : Suppose we have an array of size 20 used to store marks obtained by the students in
computer science subject. If we have already added 15 students marks according to an ascending
order, then we can delete one students marks from any place, by shifting the already stored elements
accordingly. Then it is called deletion process.
Merging:
When two or more than two records are combined, this process is called merging.
EX : Suppose we have a list of size 6, containing the elements 1,2,3,4,71,87 and we have
another list of size 5, containing the elements 9,13,21,65,67. Here both the list are in ascending order.
We can produce the third list of size 11 that will also be in ascending order, containing the element
1,2,3,4,9,13,21,65,67,71,87. The third list is called the merged list of the first and second lists. In order
to merge two lists into single list one needs to compare each element from both the lists and one of
them will go to the merged list.
Copying:
The creation of duplicate data item is called copying process. All data structures can copied.