UNIT -2

1.what is meant by ADT?

ADT- Abstract Data Types

An abstract Data type is a set of operations. Abstract Data Types are

Mathematical abstractions.

Operations:
 Union
 Intersection
 Size
 Complement
 Find

Example:

Objects such as set, lists and graphs along their operations can be
Viewed as ADT’s

2.what is the basic idea behind ADT?

The various operations of ADT such as union, intersection, size etc,

are written once in the program and any other part of the program that
needs to perform an operation of ADT can do so by calling the appropriate
function.

3.what is meant by LIST ADT?

List ADT is a sequential storage structure. It is a collection of nodes.

Each node consists of two fields.
Fields:

Data Field : Holds the Data items

Link Field : Which points to the next item(NODE)

NODE
Data Link
General Form:

A1,A2,………….An

Where
n -> size of the list
Ai-1 -> precedes Ai for i>n
Ai+1 -> succeeds for i<n

4. Give the advantages and disadvantages of array implementation of

List

Advantages:

 It is easy to create a list and print the elements

 Finding the kth element consumes less time

 The data are stored in contiguous memory location.

Disadvantages:

 Performance is very low

 Cost of insertion and deletion of a list is high

 When the program starts up , it is must to estimate the maximum

number of Items.

 It is not possible to free the excess memory.So wastage of memory

space.

5.Define Linked Lists?

It is Linear Data Structure.Each Data Structures is said to be a node

and it consist of two fields

Fields

Data Field: Holds the Data item

Link Field: Points the address of the next node
 NODE
Data Link
DaData

TYPES

 Singly Linked List

 Doubly Linked List
 Singly Circularly Linked List
 Doubly circularly Linked List

Head

10 20 30 Null

6.Give the Advantages and Disadvantages of Linked List?

Advantages:

 Memory for a node is dynamically allocated

 No wastage of memory space

 It provides flexibility and efficiently rearrange the items

Disadvantages:

 Usage of Malloc and Free are Expensive

7.Define Self Referential Node?

If the list contains a member field which points to the parent

structure then it is called Self Referential Linked List.
 8.Define Singly Linked List?

It is a Linear Data Structures in which consists a pointer field that

points the address of its net node and the Data item.

In a linked List the address of the first node is pointed by a pointer is

HEAD.

Last node points to NULL,that indicates the end of the List.

Head

10 20 30 Null

9.Define Doubly Linked list?

It is a Linear Data structure which consists of three Fields

Fields:

Previous pointer:- Previous pointer points to the address of the previous

node.
Data Field:-Holds the Data items

Next Pointer:- Next pointer points to the address of the Next Node.

NODE
Previous Next
Pointer Field Data Field Pointer Field

Head

10 20 30 Null
 10.Give the applications of linked list?

 Polynomial ADT
 Radix Sort
 Bucket Sort
 MultiLists

11. What is Pointer?

Pointer is a variable which stores the address of the next

element in the List.

Head

100

10 200 20 300 30 Null

100 200 300

12.what is the need for the HEADER?

HEADER of the linked list is the first element in the list and it
stores the number of elements in the List.It points to the First data element
of the List.

Head

100

10 200 20 300 30 Null

13. what is meant by Availability List?

A pool or list of free nodes that are maintained in conjunction

with Linked allocation is called Availability List.
14.What is Stack ADT?

Stack is a Linear or ordered list in which insertion and deletion

are occur only at one end of the List called the TOP of the Stack.

Stack is also referred as LAST -IN- FIRST- OUT ( LIFO )

Pop(s) Push(x,s)
STACK S
Top(s)

Implementation of STACK:

 Array Implementation
 Linked List Implementation

15.Give the Disadvantages of Stack?

Disadvantages:

 Array implementation requires the maximum size of the List in

prior.

 Insertion and Deletion operations are expensive.

16. Give the applications of STACK?

 Expression conversion
 Expression Evaluation
 Function call
 Balancing Symbols
 Recursion
 Towers of Hanoi
 17.Define QUEUE ADT?

A Queue is a Linear Data Structure in which insertion and Deletion

takes place in Different end of the List.

Enqueue (REAR) : Insertion takes place at one end called REAR.

Dequeue (FRONT) : Deletion takes place at other end called FRONT.

Dequeue(x,Q) Enqueue(x,Q)
QUEUE Q

Implementation of QUEUE:

 Array implementation
 Linked List Implementation
 Circular Queue implementation

18.what is circular Queue( Array) Implementation?

When the Queue full Q-FRONT and Q-REAR reaches the end of the
array. It is wrapped around the Beginning.

10 20

Q-FRONT Q-REAR

X 10 20

Q-REAR Q-FRONT
 19.Give the applications of QUEUE?

 Job Scheduling
 Categorizing Data

20. Define Polynomial ADT?

ADT for a single polynomial by using a list

n
F(x)= AiXi

i=0

Coeff Exp Next

EX:

X5+2X3+X

1 5 2 3 1 1 NULL

21.Give the RANK of the Expression?

 The Rank of a symbol Si is ‘ONE’

 The Rank of an Operator Oi(1-n)

where n -> Degree of Oi.

 The Rank of an Arbitrary sequence of symbols and operators is

the sum of the ranks of the individual symbols and operators.