DIFFERENCE BETWEEN ABSTRACT DATA YPES, DATA TYPES

AND DATA STRUCTURES

To avoid the confusion between abstract data types, data types, and data
structures, it is relevant to understand the relationship between the three

 An abstract data type is the specification of the data type which

specifies the logical and mathematical model of the data type.
 A data type is the implementation of an abstract data type:
 Data structure refers to the collection of computer variables that are
connected in some specific manner.
Thus, there seems to be an open relationship between the three, that is, a data
type has its root in the abstract data type and a data structurecomprises a set
of computer variables of same or different data types.

REFINEMENT STAGES
The best approach to solve a complex problem is to divide it into smaller parts
such that each part becomes an independent module which is easy to manage.
An example of this approach is the System Development Life Cycle (SDLC)
methodology. This helps in understanding the problem, analyzing solutions,
and handling the problems efficiently.
The principle underlying writing large programs is the top-down refinement.
While writing the main program, we decide exactly how the work will be divided
into various functions and then, in the refinement process, it is further decided
what will be the task of each function, and what inputs areto be given and
results to be obtained. The data and actions of the functions are specified
precisely. Similarly, the purpose of studying Abstract data types is to find out
some general principles that will help in designing efficient programs. There
exists a similarity between the process of top down refinement of algorithms and
the top-down specification of the data structures. In algorithm design, we
begin with the problem and slowlyspecify more details until we develop a
complete program. In data specification, we begin with the selection of
mathematical concepts and abstract data types required for our problem, and
slowly specify more details until finally we can describe our data structures in
terms of programming language.
The application or the nature of problem determines the number of refinement
stages required in the specification process. Different problems have different
number of refinement stages, but in general, there are four levels of refinement
processes:
 Conceptual or abstract level
 Algorithmic or data structures
 Programming or implementation
 Applications
Conceptual Level
At this level we decide how the data is related to each other, and what operations
are needed. Details about how to store data and how various operations are
performed on that data are not decided at this level

Algorithmic or Data Structure Level

At data structure level we decide about the operations on the data as needed
by our problem. For example, we decide what kind of data structure will be
required to solve the problem-contiguous list will be preferred for finding the
length of a list, or for retrieving any element, whereas for the evaluation of
any expression into prefix or postfix, stacks will be used.
Programming or Implementation Level
At implementation level, we decide the details of how the data structures will
be represented in the computer memory. For example, we decide whether
the linked lists will be implemented with pointers or with the cursors in an
array.
Application Level
This level settles all details required for particular application such asnames
for variables or special requirements for the operations imposed byapplications

The first two levels are often called conceptual. The middle two levels can be
called algorithmic as they are concerned with representing data and the
operations performed on the same. Last level is basically concerned with
programming

at the conceptual level, the queue has been selected as an abstract data type
and further at the next level circular queue has been selected, as this could
provide the best solution. Last level shows the operations which can be
performed on the data, for the Airport simulation,

Q) What is Data Structure? What are the different types of

Data Structures?
Data means collection of raw facts like 12, ‘a’, 34.45 etc., any processed data
is referred as information. Any user may require data to be processed. In
order to manage data in a most efficient manner one would require better
approaches and such approaches might be referred as data structures.
A data structure is a mathematical & logical representation of data in order
to organize the data in a most efficient manner.

Data structures are basically of following types:

 Linear Data structures
 Non linear Data structures
(OR)
 Static Data structures
 Dynamic Data structures
(OR)
 Homogeneous Data Structures
 Heterogeneous Data Structures
Linear Data structures: A linear data structure is a means where data may
be organized in sequential manner or in linear order.

Example: “Arrays, Stacks, Queues and linked lists” are the examples
for linear data structures.

Non-linear Data structures: A non-linear data structure is a means where

data may be organized in quite a different manner. It doesn’t follow any linear
form.

Example: “Trees & Graphs” are the examples for the non-linear data
structures.

Static Data structures: A static data structure is fixed in its size as it is

specified during the compile time.
Example: “Arrays, Stacks & Queues” are the examples for static data
structures.

Dynamic Data structures: A dynamic data structure is created during the

runtime. It provides better flexibility to the user as it allows the user to
increase or decrease the size during the execution of the program. Hence we
say that dynamic data structures may vary during the runtime. Moreover,
dynamic data structures allow the user to add, delete and rearrange data
items at runtime.
Example: Linked lists, Trees & Graphs

Homogeneous Data Structures: It is a data structure where items of

similar kind or same type of items are placed/arranged.
Example: Arrays, Stacks, Queues are the examples of this kind.
Heterogeneous Data Structure: It is a data structure where items of different
can be placed and operated. Linked Lists, Trees & Graphs may be the examples
of Heterogeneous data structures

Q) What is primitive and non-primitive data structures?

Primitive Data Structures:

Primitive Data Structures are the basic data structures that directly operate
upon the machine instructions. They have different representations on
different computers. They are:
 Integers,
 Floating point numbers,
 Character constants,
 String constants
 Pointers
Non-primitive Data Structures:
Non-primitive data structures are more complicated data structures and are
derived from primitive data structures.
They emphasize on grouping same or different data items with relationship
between each data item.
These are:
 Arrays
 Lists
 Files
Q) What is Linear and Non-Linear data structures?
Data structure is a way to organize a data in computer so that it can be
used efficiently.
In computer science, Data Structure is classified into two categories :
 Linear Data Structure
 Non Linear Data Structure

Linear Data Structures: The data structure where data items are organized
sequentially or linearly where data elements attached one after another is
called linear data structure. Data elements in a liner data structure are
traversed one after the other and only one element can be directly reached
while traversing. All the data items in linear data structure can be traversed
in single run.
These kind of data structures are very easy to implement because memory of
computer is also organized in linear fashion.
Examples of linear data structures are:
 Arrays,
 Stack,
 Queue
 Linked List.
 An arrays is a collection of data items having the same data types.
 A Stack is a LIFO (Last In First Out) data structure where element that
added last will be deleted first. All operations on stack areperformed from
on end called TOP. A Queue is a FIFO (First In First Out) data structure
where element that added first will be deleted first.
 In queue, insertion is performed from one end called REAR anddeletion
is performed from another end called FRONT.
 A Linked list is a collection of nodes, where each node is made up of a data
element and a reference to the next node in the sequence.
Non Linear Data Structures: The data structure where data items are not
organized sequentially is called non linear data structure. In other words, A
data elements of the non linear data structure could be connected to more
than one elements to reflect a special relationship among them. All the data
elements in non linear data structure can not be traversed in single run.
Examples of non linear data structures are:
 Trees
 Graphs
 A tree is collection of nodes where these nodes are arranged
hierarchically and form a parent child relationships.
 A Graph is a collection of a finite number of vertices and an edges that
connect these vertices. Edges represent relationships among vertices
that stores data elements.
Difference Between Linear and Non Linear Data Structure:

Linear Data Structure Non-Linear Data Structure

Every item is related to its previous Every item is attached with many
and next item. other items.

Data is arranged in linear sequence. Data is not arranged in sequence.

Data items can be traversed in a Data can not be traversed in a

single run. single run.

Examples: Array, Stack, Queue,

Examples: Tree, Graph.
Linked List.

Implementation is Easy. Implementation is Difficult.

Q) Explain about Arrays?

Array is a collection of similar kind of items or elements. In other words, an array
is a linear list in which a group of elements are identified by a unique name. In
some other way, a group of elements that have common name is said to be an
array. An array can be called as linear list or simply list.

Types of Arrays: Arrays are of three different types. They are:

 Single Dimensional arrays

 Double Dimensional arrays
 Multi-dimensional arrays.
Single dimensional arrays have only one subscript or index where as multi-
dimensional arrays may have more than one subscript or index.
For Example:
int a[20];
float b[10]; //single dimensional or one dimensional arrays
int a[3][3]; // double dimensional or table or two dimensional
int a[3][3][3]; // multi-dimensional

Note: There may be any number of subscripts for arrays.

Declaration of Arrays:
Syntax:
datatype array_name [no. of items];
OR
datatype array_name [index];
Ex:
int a [10]; // integer array

char str[ 8 ]; // character array

Data type array name index

Note:

 Array name should not contain any spaces.

 Index of the array should not be zero or less than zero.
 Array size is fixed.
 Array index starts from zero always.
Symbolic representation of two dimensional arrays follow:

For example, consider int a [3][4];

11 33 22 55 44 88 66 55 77 99 100 101

0 1 2 3 0 1 2 3 0 1 2 3

Initialization of array:

int a[5]={11,12,13,14,15};
int a[]={11,22,33};
char a[7]={“sairam”};
float b[4]={1.2,3.5,7};

Two Dimensional Array:

These arrays are also called double dimensional array. Another name of two-
dimensional array is Tabular or Rectangular Array. These arrays are in row
and column form, so these are also called Row-Column array or square Array.
These arrays have two subscripts and also called double subscripted array.
We can write the double dimensional array in the matrix form as below and
so these are also known as matrix array. The syntax used for declaration of
two dimensional array is as:

data-type array-name [row size] [column size];

For example, some of the valid double dimensional arrays are written as
below:
int a[10][10];
float b[50][50];
char name[10][20];

Also you can declare two-dimensional array in static form i.e. these type of array
declarations have fixed value or constant value. The syntax used for static two
dimensional array is as follows:

static data-type array-name [row size][column size = {list of value};

For example, suppose you want to assign some fixed value to a variable
array named table by using the static two-dimensional array as.

static int table [2][3] = {15, 7, 12, 2, 20, 8};

Here the values assigned to the tabular array-name is as:
table[0][0] = 15
table[0][1] = 7
table[0][2] = 12
table[l][0] = 2
table[l][1] = 20
table[l][2] = 8
Also we can write the above statement as:
static int table[ ][ ] = {15, 7, 12, 2, 20, 8};
Above statement fails in some cases.
Another way to write the above statement is as follows:
static int table[][]={ {5, 7, 12} , {2, 20, 8} };
char table[2][30]={“kumar”,”dheeraj”};

Multi Dimensional Array:

It is a collection of double dimension arrays. Each double dimension array
is identified by with ‘i’ each array is identified by ‘j’ and each valueis
identified by with ‘k’
Syntax:
Datatype variable[no_of_dd_arrays][row_size][col_size];

Eg:
int a[3][2][4];
Operations on Arrays:

1. Creation of array
2. Initialization of array
3. Accepting data into array
4. Displaying contents of array
5. Insertions
6. Deletions
7. Search
8. Sort

Advantages of arrays:
 As arrays store all the elements in continuous locations, it becomes
easy to access all the elements. 
 Arrays allow the user to store elements of same type in sequential
manner.
 Array elements can be accessed randomly (need not to follow any
order).
 Arrays avoid no. of variables & their naming.
Disadvantages of arrays:
 Array size is fixed. The user cannot grew or shrink the size
dynamically. 
 Optimum utilization of memory may not be achieved (i.e., there is a
scope for wasting the memory).
 Arrays allow only similar kind of items as data.
Characteristics of a Data Structure
 Correctness:
Data structure implementation should implement its interface correctly.
 Time Complexity:
Running time or the execution time of operations of data structure must be
as small as possible.
 Space Complexity:
Memory usage of a data structure operation should be as little as possible.
 Operations on Data Structures: The operations involve in data
structure are as follows.
 Create: Used to allocate/reserve memory for the data element(s).
 Destroy: This operation de allocate /destroy the memory space
assigned to the specified data structure.
 Selection: Accessing a particular data within a data structure.
 Update: For updating (insertion or deletion) of data in the data
structure.
  Searching: Used to find out the presence of the specified data item in
the list of data
 Sorting: Process of arranging all data items either in ascending or in
descending order.
 Merging: Process of combining data items of two different sorted lists
of data items into a single list.

A stack is a linear list in which insertions & deletions are made at one end
called top. Stack follows LIFO manner in order to store data. LIFO means Last
In First Out. As an example to stack, consider a set of plates placed one over
the other or a pile of books.

A stack may be referred as linear data structure or static data structure or

homogeneous data structure.

Stack is used in many computer applications. It is used in system software like

operating systems, compilers. More over a stack may be implemented either
using arrays or using linked list.

Operations on Stack:
 Push
 Pop
 Show
  Is empty
 Is Full

Push() : This allows storing data one after the other.

Pop() : This operation allows deleting data one after the other.
Show() : This operation allows displaying data stored in the stack.
Isempty() : To check whether the stack is empty or not.
Isfull() : To check whether the stack is full or not.
.
Push:
In the push operation, initially top is initialized to –1. From there, items are stored
one after the other by incrementing ‘top’ by 1. As and when ‘top’ reaches the
maximum position, the push (or insertion) operation is stopped.

4 4 4 4 4 50 4

3 3 3 3 40 3 40 3

2 2 2 30 2 30 2 30 2

1 1 20 1 20 1 20 1 20 1

0 10 0 10 0 10 0 10 0 10 0

Top = -1 top = 0 top = 1 top = 2 top = 3 top = 4

For each insertion, we check out whether the stack is full or not. If it is
FULL stop the process otherwise continue pushing items.
Procedure to perform push operation:

Procedure: Push ( stk, item)

begin
If (top = MAX-1) then
Display “ Stack is OVERFLOW”
else
begin
1. Increment top by 1.
2. Assign stk [ top ] = item.
End
End.

Note: Here ‘MAX’ is the value of maximum number of items that can be
stored in a stack.
POP:
In pop operation, the elements of stack are removed one after other by
decrementing the value of top. Once after removing the last item from the stack,
pop operation is terminated. For each deletion, we check out whether the
stack is empty or not.

50 4 4 4 4 4 4

40 3 40 3 3 3 3 3

30 2 30 2 30 2 2 2 2

20 1 20 1 20 1 20 1 1 1

10 0 10 0 10 0 10 0 10 0 0

Top = 4 top = 3 top = 2 top = 1 top = 0 top = -1

Procedure: Assume ‘stk’ as a stack.

Procedure: Pop( stk)

Begin
If (top = -1) then
Display “Stack is UNDERFLOW”
Else
Begin
1. Assign item = stk [ top ].
2. Decrement ‘top’ by 1.
3. Print ‘item’
End
End.
Show:

The stack allows display from top to bottom i.e., from top pointer only the
user can list the items.

For the above example, the items are: 50 40 30 20 10 5

Applications of Stack:
 Used in operating systems, compilers other system software
 Processor itself maintains a stack in order to execute applications.
 Used for expression evaluations.
 Used in regular function calls, nested function calls and recursive
function calls.
Q)Write an algorithm for infix to Postfix expression?
Step 1: start
Step 2: Initially push a left parenthesis ‘(‘ into the stack and ‘)’ added to
the given expression.
Step 3: Repeat the following procedure while the stack is not empty.
Step 4: If an operand is encountered added to the postfix expression.
Step 5: If a ‘(‘ is encountered, pushes onto the stack.
Step 6: If an operator is encountered, Repeatedly pop from the stack and
each operator is added to the postfix expression until the same
precedence operator occur on the stack.
(the operator is less than in the stack)
Step 7: If ‘)’ is encountered repeatedly pop from the stack and added to the
postfix expression until ‘(‘ and next remove the ‘(‘.
Step 8: stop.
To convert infix to post fix expression
1) (a+(b*c-(d/e^f)*g)*h)

ans) abc*def^/g*-h*+

2) 5,6,2,+,*,12,4,/,-

ans) 5 5

6 5,6

2 5,6,2

+ 5,8

* 40

12 40,12

4 40,12,4

/ 40,3

- 37
To convert Infix to Postfix
((A+B)*(D^(E-F)))

EXPRESSION STACK POST

( (

(( ((

A (( A

+ ((+ A

B ((+ AB

) ( AB+

* (* AB+

( (*( AB+

D (*( AB+D

^ (*(^ AB+D

( (*(^( AB+D

E (*(^( AB+DE

- (*(^(- AB+DE

F (*(^(- AB+DEF

) (* AB+DEF-
(^

) AB+DEF-^
(*

) AB+DEF-^*
 .
Example
Infix to prefix
6+9+(4*2+4^2)
Reverse Infix Expression:

)2^4+2*4(+9+6

Scan tokens one at a time from left to right.

Character Stack Ouput

) )
2 ) 2
^ )^ 2
4 )^ 24
+ )+ 24^
2 )+ 24^2
* )+* 24^2
 4 )+* 24^24
( 24^24*+
+ + 24^24*+
9 + 24^24*+9
+ ++ 24^24*+9
6 ++ 24^24*+96
Scanning complete.
Pop remaining 2 operators from stack,
one at a time, and append to output.
+ 24^24*+96+
24^24*+96++
Reverse final output.
Prefix: ++69+*42^42
A+B)*(C+D)
Reverse Infix Expression:

)D+C(*)B+A(

Scan tokens one at a time from left to right.

Character Stack Ouput

) )
D ) D
+ )+ D
C )+ DC
( DC+
* * DC+
) *) DC+
B *) DC+B
+ *)+ DC+B
 A *)+ DC+BA
( * DC+BA+
Scanning complete.
Pop remaining operator from stack
and append to output.
DC+BA+*
Reverse final output.
Prefix: *+AB+CD

Types of Queues:

There are different types of queues. The list follows:

 Queues
 Circular Queues
 Double Ended Queues (De-Queues)
 Priority Queues
Queues

A queue is a linear list where items may be inserted or deleted in FIFO manner.
FIFO means First In First Out. That is, the item placed in the first, will be accessed
and removed first from the queue. Similarly the item placed last will be accessed
and removed last. A queue uses two pointers called front, rear to perform
storage & retrieval operations.

In other words, queue has two ends: front and rear. All the insertions into queue
are made at ‘rear’ end and all the deletions are done at ‘front’ end.

A queue is called as linear data structure or static data structure or

homogeneous data structure. The no. Of items in a queue is fixed. The operating
system itself maintains an instruction queue while executing user programs.
A queue of people is the regular example for queues.

Operations on Queues:
 Create or Initialize a queue.
 Insert an item into a queue (Insertq () or Enqueue())
 Delete an item from a queue (Deleteq()).
 Display all the items (show ()).
 Check whether Queue is empty or not (isempty())
 Check whether Queue is full or not (isfull())
Initially declaration & initializing the front and rear pointers is to be done.

Enqueue:(Insertq) Storing elements one after the other into the queue is possible
at this level of operation using the rear pointer. Increment each time an item is
placed in the queue.

Dequeue Operation(Deleteq): Removal elements from the queue one by one is

done at this level of operation using the front pointer. Increment front whenever
an item is removed from the queue.

Show: Displaying elements of the queue are performed in this operation because
unless the user doesn’t know what is the content of the queue, he is unable to
process other operations.

The process of adding an element into the queue is known as Enqueue. The
following steps should be taken to enqueue (insert) data into a queue .

Procedure: enqueue (que, item)

Begin
If (rear = MAX-1)
Display “ Queue is OVERFLOW”
Else
Begin
a. Increment rear by 1.
b. Assign q [rear] = item
End
End.
Symbolic Representation of Insertions follows:

0 1 2 3 4 0 1 2 3 4

10

r =-1 f = 0 f=r=0

10 20 10 20 30

f r f r

10 20 30 40 10 20 30 40 50

f=0 r=3 f=0 r=4

Dequeue Operation(Deletions):
This operation allows removing of elements from the queue one by one. Here we use
front end (or pointer) to remove each item. For each removal front is incremented
by 1. The process of removing items from the queue is done untilthe queue
becomes EMPTY. That is, when the queue becomes empty, the deletion process
is terminated.

Symbolic Representation of Deletion operation:

0 1 2 3 4 0 1 2 3 4
10 20 30 40 50 20 30 40 50

f r f r
0 1 2 3 4 0 1 2 3 4
30 40 50 40 50

f r f r
0 1 2 3 4 0 1 2 3 4
50

f, r queue is empty !! f=0 r=-1

The following is the procedure to delete an item from the queue:

Assume front = 0, rear = 4.

Procedure: Deleteq ( que)

Begin
if((front==0)&&(rear==-1))

PRINT Queue is underflow

else

if(front==rear)
BEGIN
front=0;rear=-1;
END
else
front=front+1;

End.
Applications of queue
There are various applications of computer science, which are performed using data
structure queue. This data structure is usually used in simulation, various
features of operating system, multiprogramming platform systems and different
type of scheduling algorithm are implemented using queues. Round robin
technique is implemented using queues. Printer server routines, various
applications software are also based on queue data structure.
 The operating system itself uses a queue called an Instruction Queue & a Message
Queue.
 In a network, there will be a print queue that manages the documents to be printed
Circular Queues( It is also called as “Ring buffer”.)
In regular queues, there is a situation where the user cannot insert items through
the positions are free. That is, for example, consider a queue with full of data.

f r

10 20 30 40 50 60 70

Perform Deletion operation on the above queue for 3 times. The following is the
resultant queue.
 40 50 60 70
f r
Now there are 3 empty locations, but still the user cannot store any more items
because the rear pointer cannot be incremented further.
In order to overcome the above problem and to reutilize the empty locations,
circular queues have come into picture.

Step1: Empty CQueue

Step2: Inserting ‘10’ element into CQueue

Step3: Inserting the ‘20’ element into CQueue

Step4: Inserting the ‘30’ and ‘40’ elements into CQueue

Step5: Inserting the ‘50’ and ‘60’ elements into CQueue

Step6: Inserting the ‘70’ element into

CQueue
If we try to insert ‘70’ element in queue. It displays “queue is full” message.

Removing values from the CIRCULAR QUEUE:

Step1: Removing ‘10’ element from the CQueue
Step2: Removing ‘20’ element from the Queue

Step3: Removing ‘30’ and ’40’ element from the Queue

Circular Queue Behavior:

Step4: inserting ‘70’ element into the Queue

So that in CIRCULAR QUEUE we can again insert new values at the deleted
positions
Algorithm to insert an element in a circular queue
Step 1: IF (REAR+1)%MAX = FRONT
Write " OVERFLOW "
Goto step 4
[End OF IF]

Step 2: IF FRONT = -1 and REAR = -1

SET FRONT = REAR = 0
ELSE IF REAR = MAX - 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]

Step 3: SET QUEUE[REAR] = VAL

Step 4: EXIT

Dequeue Operation
The steps of dequeue operation are given below:

First, we check whether the Queue is empty or not. If the queue is empty, we cannot perform
the dequeue operation.
When the element is deleted, the value of front gets decremented by 1.
If there is only one element left which is to be deleted, then the front and rear are reset to -1.
Algorithm to delete an element from the circular queue

Step 1: IF FRONT = -1
Write " UNDERFLOW "
Goto Step 4
[END of IF]

Step 2: SET VAL = QUEUE[FRONT]

Step 3: IF FRONT = REAR

SET FRONT = REAR = -1
ELSE
IF FRONT = MAX -1
SET FRONT = 0
ELSE
SET FRONT = FRONT + 1
[END of IF]
[END OF IF]

Step 4: EXIT
Double Ended Queue
A double-ended queue is a queue where items can be inserted & deleted at either
end. That is, we can insert elements from both rear & front ends. Again there are
2 types of double-ended queues. They are:

 An input-restricted deque is one where deletion can be made from both

ends, but insertion can be made at one end only.

 An output-restricted deque is one where insertion can be made at both

ends, but deletion can be made from one end only.

Initializing a DeQue: Consider the DeQueue with size is 5

Step1: Empty DeQueue

Inserting Using Rear:

Step2: Inserting ‘10’ element into Queue

Step3: Inserting the ‘20’ element into Queue

Step4: Inserting the ‘30’ element into Queue

Step5: Inserting the ‘40’ element into Queue

Step6: Inserting the ‘50’ element into Queue

Removing values using Front:

Step1: Removing ‘10’ element from the Queue

Step2: Removing ‘20’ element from the Queue

The above insertions and deletions are done as like normal QUEUE. Now we can
see the insertions and deletions are not doing by the normal QUEUE….they
are:

Inserting using Front:

Step1: inserting ‘60’ element using Front

Step2: inserting ‘70’ element using Front

Deletion from Rear:

Step1: Deleting ‘50’ element from Rear

Step2: Deleting ‘40’ and ‘30’ elements from Rear

Priority Queue
Often the items added to a queue have a priority associated with them; this priority
determines the order in which they are removed from the queue. Higher priority
items are removed first. Such a queue is said to be priority queue. Priority queues
are used in Process Control Systems.

Applications:
 Band width management : pq can be used to manage the limited resources
such as band width on transmission line from a network router 
 Discrete event simulation: pq is to manage events in a discrete event
simulation . The events are added to the queue with their simulation
time used as priority 
 Relationship to store the algorithms: the semantics of pq naturally suggested
to storing methods (heap sort)

LINKED LIST:-
DEF:-”Linked list is a dynamic and linear data structure”. A linked list is a list of
elements in which the elements of the list can be placed anywhere in memory, and these
elements are linked with each other using an explicit link field, that is, by storing the
address of the next element in the link field of the previous element.
Dynamic Allocation:-

• The process of allocating memory at runtime is known as dynamic

allocation.
• Dynamic memory management techniques allow us to allocate additional memory
spaceor to release unwanted space at run time.
• Linked list is one of the basic types of dynamic data structures.
• It provides flexibility in adding, deleting or rearranging data items at runtime.
• Dynamic memory management techniques use the memory management
functionswhich are used for allocating and freeing memory during program
execution.

Types of linked list:-

1. Singly Linked List

2. Doubly Linked List
3. Circular Linked List
 There are three common types of Linked List.
1. Singly linked list:-
In this type of linked list two nodes are linked with each other in sequential
linear manner. Movement in forward direction is possible. Hence it is also called as
linear linked list or one way list.

The diagrammatic representation of a single linked list is as follows:

2. Double linked list: -

A double linked list is one in which all nodes are linked together by
multiple links. Each node in a double linked list has three parts. Two pointers one
which points to leftand other which points to right and third part is a data part. In this
list we can traverse in forward and backward direction.
The diagrammatic representation of this list is as follows.

3. Circular linked list :-Circular linked list is one which has no beginning and no end.
A single linked list can be made a circular linked list by simply storing the address of
last node to the first node of the list.
The diagrammatic representation of this list is as follows.

Advantatages of linked list:-

Some of the advantages of linked list are in the following ways.

1) Linked list can be increased or decreased because of dynamic data

structure.
2) Linked list have efficient memory utilization (dynamic memory
allocation)
3) Insertion and deletion easily performed.
4) Many complex applications can be easily carried out with linked list.
5) Faster Access time, can be expanded in constant time without memory overhead

Disadvantages of linked list:-

1) It occupy more space because every node contain a pointer to share the
address ofnext node
2) Searching a particular element in a list is a time consuming one.
Applications of linked list:-

1) Linked list are used to implement data structures such as stacks, queues, trees and
graphs
2) Linked list are used to represent very large numbers and operations of large number.
3) Linked list are used to represent to represent manipulate polynomial.

1. Singly linked list:

A single linked list is a very flexible dynamic data structure. Here items can
be addedor deleted from any position. A simple way to represent a linked list to
expand each node that contains link or pointers to the next node. Each node
consists of TWO parts Namely
1. link part
2. Data part
 Operations on a single linked list:-

The operations that are performing on a single linked list are in the following ways.
1 .Create a list
2 .Insert an element into the list
3 .Delete an element from the list
4 .Traverse a list

1) Create a list: -To create a linked list first of all we have to check whether the list is
emptyor not. Initially the value of a header will be null. If the header is null then create
new node andassign the address of the node to header. If the header is not null then
established the links between last existing and the new node.
Algorithm:-
Step 1:- start

Step 2:- Create a node

Newnode->data=element

Newnode->link=null

Step 3:- if (header ==null) then

Header=new
node else

Step 4:- p=header

Step 5:-repeat step 6 until p-> link=null

Step 6:-p=p->link

Step 7:- p->link=new

nodeStep 8:- End

2) Inserting an element into the list:-

Insertion in a linked list can be placed at three positions in a list. While
insertinga node into the list we have to know the location where the node is to be
inserted
i . Insertion at the front of list.
 ii. Insertion in the middle of the list
iii. Insertion at the end of the list.

i) Inserting an elemnent at front of the list:-Insertion of a node can be placed at the

beginning of the list which in turn headerpoints to this node. Before inserting a node
we have to check whether header is null or not. Ifit is null then new node itself is the
first node .Otherwise we can place new node just before existing nodes.

Algorithm:- Step 1:- start

Step 2:-Create a newnode

Newnode->data=element

Newnode->link=null

Step 3:-if (head ==null) then

Head=newnode

else

Step 4:-Newnode -> link=head

Step 5:-Head=newnode

Step 6:- End

ii ) Insertion at the end of the list:-

Insertion at the end of the list is very simple just locate the last node
pointer andplace the node in the pointer->next. If the list is empty then the new node
 becomes first node. If the list is non empty then the last node pointer contains the
address of new node & new nodenext contains null value.

Algorithm:-

Step 1:- start

Step 2:- Create a new node

New node->data=element

New node->link=null

Step 3:- if( head==null) then

Head=newn
ode else

Step 4:- p=head

Step 5:- repeat

step 5 until p-> link=null

Step 6:- p=p->link

Step 7:- p->link=newnodeStep

8:- End
iii) Insertion of the node middle position:-
Inserting an element in a list after a specified position of a node then we have
to findout the location of the specified node or element. If the node which you are
going to place isat the beginning then header points to the new node or if the position
 you specified is the lastnode then place new node and it becomes last node. If not,
place it at the middle of the list. Algorithm:- Step 1:- start
Step 2:- Create a newnode
Newnode-
>data=element
Newnode->link=null

Step 3:- if (head==null) then

Header=newnode

else

Step 4:- p=head

Step 5:- repeat step 6 until p->link=null

Step 6:- if (p->data==element))then

newnode->link=p-> link

P -> link =new node

Step 7:- p=p -> link

Step 8:- End

3) Deletion of a node from a list:-

 Node can be deleted in THREE places.
They are i .Deletion at
beginning of the list.
ii.Deletion at the
middle of thelist.
iii.Deletion at the end
of the list.
Deletion of a node requires a location in the list and disconnecting the address
of the node to be deleted. Suppose we want to delete an element from any position first
of all we have to check whether the list is empty or not.
i. Deletion at beginning of the list:-

Step 1:- start

Step 2:- p=head

Step 3:- head=head->link

step 4:- free p

Step 5:- stop

Deletion at the middle of the list:-

 Algorithm:-

Step 1: Start

Step 2:-p=head , q=head

Step 3:-repeat steps 4 and 5 until ( p->data !=x)Step 4:-q=p

Step 5:-p=p->link

Step 6:-q->link = p->link

Step 7:-free p;

Step 8:-stop

Deletion at the end of the list:-

i. Deletion at the end of the

list:-Algorithm:-
Step 1:- Start

Step 2:- p=head , q=head

Step 3:-repeat steps 4 and 5 until (p->link != NULL)

Step 4:-q=p;

Step 5:-p=p->link

Step 6:-free p

Step 7:- q->link=NULL

Step 8:-Stop
 3) Traversing of a linked list:-
Traversing a node in the list is possible only in one direction. Traversing of a linked list begins at the
first node of the list. To traverse a linked list we have to create a temporary variable of type node to
hold the address of the first node after compilation of the node it points to next node. It will be
continued until the address of the last node becomes null

Step 1:- start

Step 2:- p=head

Step 3:- repeat the steps 4 & 5 until p! =null

Step 4:- print “p->data”;

Step 5:- p=p->link

Step 6:- end

2.Double linked list

Double linked list is a list in which all the nodes have multiple links that are linked
together in some order these multiple l inks helps us in accessing both previous and
successive nodes. Each node in a double linked list has 3 parts.

1. Left pointer(link1) 2. Data part 3. Right pointer(link2)

* In double linked list we can insert in both directions.

* The pointer pointing to the preceded node is called left link. The pointer pointing
the nextnode is called right link.Structure of double linked list is as follows:
The diagrammatic representation of double linked list is:
Operations on a Double linked list:-

The operations that are performing on a double linked list are in the following
ways.
1. . Create a list
2. Insert an element into
the list 3 . Delete an element
from the list4 . Traverse a list
1) Creation of a node:-

To create a double linked list first of all we have to check whether the list is
empty or not, if it is empty assign a new node to the header otherwise establish the links
between existing and the new node.
Algorithm:-

Step 1:- start

Step 2:- create a node

New node->data=num;

New node->left link=null;

New node->right link=null;

Step 3:- if (head = = null) then

head= new node

Return;

Step 4:- p=head

Step 5:- Repeat step 6 until p->link=null

Step 6:- p=p->right link

 Step 7:- p->right link=new node

New node->left link=p;

Step 8:- end

2) Insertion in doubly linked list:-

There are three ways for inserting element in list.
a. Insertion at the front of list.
b. Insertion in the middle of the list.
c. Insertion at the end of the list.

a. Insertion of a node at the beginning of the list:-

Elements can be inserted at the beginning. Before insertion we have to check
whether the header is empty or not, if it is empty assigned the new node to the header
otherwise assignthe starting node address to the new node and the new node left link
address to the starting node. Finally the new node assign with pointers.
Algorithm:-
Step 1:- start

Step 2:- create a new node

New node->data=num;

New node->left link=null;

New node->right link=null;

Step 3:- if (head = = null) then

head=New node;

Step 4:- else

New node->right link=head

head->leftlink=newnode
head=newnode

step 5:- stop

 a. Insertion of a node at end of the list:-
Elements can be inserted at the end. Before insertion we have to check whether the
headeris empty or not, if it is empty assigned the new node to the header otherwise
assign the last node address to the new node and the new node left link address to the
previous node.

Algorithm- Step 1:- start

Step 2:- Create a node

New node->data=num;

New node->left link=null;

 New node->right link=null

Step 3:- if( header ==null) then

Header=new node
else

Step 4:- p=header

Step 5:- repeat step 6 until

p -> right link=null

Step 6:- p=p -> right link

Step 7:- p -> right link =new node

newnode -> left link =p
newnode -> rightlink
=NULL

Step 8:- End

c) Insertion of a node at the Middle of the list:-

In this we first search element is there or not. It is Found then insert a new node and
assignthat address to the previous node and next node. Otherwise to display element
not found.

Step 1:- start

Step 2:- Create a node

New node->data=element
 New node->left link=null

newnode->right link =NULL

Step 3:- if (head==null) then

Head=new node
else

Step 4:- p=head:

step 5:- Repeat step 6 until (p->data!= item)

Step 6:- p=p->rightlink

step 7:- newnode->right link=p->right link

newnode->leftlink =p

newnode->rightlink->leftlink=newnode
Step 8:- End

4) Deletion:-

In a double linked list, the deletion operation can be performed in three

ways asfollows...

a.Deleting from Beginning of the list

b.Deleting from End of the list

c.Deleting a Specific Node

a.Deleting from Beginning of the list:-

Node can be deleted from the front. Replace the START pointer to next node
andrelease the links from the first node.
Algorithm :-

1. Start
2. If (head==null)
print “no nodes in doubly linked list”

3. p=head
4. head =head->rightlink
5. free p
6. head ->leftlink=NULL
7. Stop

b Deleting from End of the list:Node can be deleted at the end of the list. Make lastnode
left link as NULL

Algorithm:-
1. Start
2. if(head == null)
print “ D.L.L is empty”

else

3.p=head
4.repeat steps 5 until ( p->rightlink !=null)
5.p=p->rightlink
6.p->rightlink->leftlink=null
7.free p
8. Stop

4. Traversing:- In this we visit each and every element from first element to last
element
Algorithm: - Step 1:- START

Step 2:- set p=head;

Step 3:- repeat the step 4 until p!= null

Step 4:- print (p->data)

Step 5:- p=p->rightlink

Step 4:- STOP

Advantages:

1. We can traverse in both directions i.e. from starting to end and as well as
from end tostarting.
2. It is easy to reverse the linked list.
3. If we are at a node, then we can go to any node. But in linear linked list, it
is notpossible to reach the previous node.

Disadvantages:

1. It requires more space per space per node because one extra field is
required forpointer to previous node.
 2. Insertion and deletion take more time than linear linked list because more
pointeroperations are required than linear linked list.

Circular linked list

Circular linked list is a sequence of elements in which every element has link to its
next element in the sequence where the last node points to first node.That means circular
linked list is similar to the single linked list except that the last node points to the first node
inthe list
Circular linked list of two types
i .Single circular linked
list ii.Double circular
linked list

i.Single circular linked list:-

Example:-

ii. Double circular linked

list:-example:-
Operations on Single circular linked list:-

In a circular linked list, we perform the following operations...

1. Insertion
2. Deletion
3. Display
1) insertion:-
In a circular linked list, the insertion operation can be performed in three
ways. They are asfollows...
i. Inserting At Beginning of the list
ii. Inserting At End of the list
iii. Inserting At Specific location in the list
Algorithm:-

· Create new node PTR

· Set the INFO field of PTR
· If list have no node i.e. [TAIL == NULL]
o TAIL = PTR
o PTR->NEXT = PTR [PTR will point to itself]
· Else
o PTR->NEXT = TAIL->NEXT [PTR’s next will point to first node]
o TAIL->NEXT = PTR [TAIL’s next pointer will point to PTR]
 i. Inserting At End of the list:-
Node can be added at the end of the list.
· Create new node PTR
· Set the INFO field of PTR
· If list have no node i.e. [TAIL == NULL]
o TAIL = PTR
o PTR->NEXT = PTR [PTR will point to itself]
· Else
o PTR->NEXT = TAIL->NEXT [PTR will point to first node]
o TAIL->NEXT = PTR [last node will point to PTR]
o TAIL = PTR [TAIL will point to PTR which is now last node]

ii. Inserting At Specific location in the list:-

Node can be inserted at any specified position. First of all we have to check the
elementin the list whether it is there or not.
Algorithm:-
· Create new node PTR
· Set the info field of PTR
· If list have no nodes i.e. (TAIL == NULL)
o If (POS == 1)
§ Set PTR->NEXT = PTR

§ Set TAIL = PTR

o Else
§ Invalid POS. Node can’t be inserted

o
· Else if (POS == 1) (Now list is not empty also)
o Set PTR->NEXT = TAIL->NEXT
o Set TAIL->NEXT = PTR
· Else

o Set TEMP = TAIL->NEXT

o Traverse the list for (POS-1)th node of list into TEMP
· If TEMP == TAIL
§ Set PTR->NEXT = TAIL->NEXT
§ Set TAIL->NEXT = PTR
§ Set TAIL = PTR
o Else
§ Set PTR->NEXT = TEMP->NEXT
§ Set TEMP->NEXT = PTR
o End If;
· End If;

1) Deletion:-
Elements can be deleted in the following ways. First of all we have to check
whetherthe given element is existed or not. There are Three positions to delete an
element.
i. Deletion at beginning of the Circular linked list.
ii. Deletion at the middle of the Circular linked list.
 iii. Deletion at the end of the Circular linked list.
i. Deletion at beginning of the Circular linked list:- Element can be deleted
at thebeginning
Algorithm:-

 Declare TEMP
 If list have only one node
o FREE (TAIL)
TAIL = NULL
else
 TEMP = TAIL->NEXT [TEMP will point to first node]
 TAIL->NEXT = TAIL->NEXT->NEXT [TAIL’s next will now pointto second node]
 Free (TEMP) [free the first node]



i. Deletion at the end of the Circular linked list:-

Element can be deleted at the end of the list.
Algorithm:-

· Set TEMP1 = START

· If START != NULL
o If START->NEXT == NULL
§ START=START->NEXT

§ FREE (TEMP1)

o Else
§ Traverse the list so that TEMP1 points to last node
andTEMP2 points second last node

§ TEMP2->NEXT = NULL
 § FREE (TEMP1)

o End If;