· A stack can be implemented as a constrained version of a linked list. A stack is referenced via a pointer to the top element of the stack. The link member in the last node of the stack is set to NULL to indicate the bottom of the stack.

Example:

Fig-2.1.2

- stackptr points to the top of the stack.

Note that stacks and linked lists are represented identically. The difference is that insertions and deletions occur anywhere in a linked list, but only at the top of a stack.

Operations on Stack

Push ( ):

Description: Here STACK is an array with MAX locations. TOP points to the top most element and ITEM is

the value to be inserted.

1. If (TOP == MAX) Then [Check for overflow]

2. Print: Overflow

3. Else

4. Set TOP = TOP + 1 [Increment TOP by 1]

5. Set STACK[TOP] = ITEM [Assign ITEM to top of STACK]

6. Print: ITEM inserted

[End of If]

7. Exit

Pop ( ):

Description: Here STACK is an array with MAX locations. TOP points to the top most element.

1. If (TOP == 0) Then [Check for underflow]

2. Print: Underflow

3. Else

4. Set ITEM = STACK[TOP] [Assign top of STACK to ITEM]

5. Set TOP = TOP - 1 [Decrement TOP by 1]

6. Print: ITEM deleted

[End of If]

7. Exit

BACK

Unit-02/Lecture-02

Representation of Stack

Array Implementation of stack

#define maxstack 100

struct stack{

int items[maxstack];

int top;

};

int isEmpty(struct stack s){

return (s.top < 0);

}

int isFull(struct stack s){

return (s.top >= maxstack-1);

}

void push (struct stack *s, int x){

if (s->top >= maxstack-1)

printf(“The stack is full.\n”);

else {

s->top = s->top +1;

s->items[s->top] = x;

}}

int pop (struct stack *s){

int x;

if (s->top < 0)

printf(“Stack is empty.\n”);

else{

x = s->items[s->top];

s->top = s->top –1;

return x;

}}

int main()

{struct stack S;

int c, i;

S.top = -1;

while ((c=getchar() )!='\n')

push(&S, c);

while (!isEmpty(S))

printf("%c", pop(&S));

printf("\n");

}

Linked List (One way List) [RGPV/Dec2013 (2)]

We understood that the sequential representation of the ordered list is expensive while inserting or deleting arbitrary elements stored at fixed distance in a fixed memory.

The linked representation reduces the expense because the elements are not stored at fixed distance and they are represented randomly and the operations such as insertion and deletion are required change in link rather than movement of data.

A linked list is a linked representation of the ordered list. It is a linear collection of data elements termed as nodes whose linear order is given by means of link or pointer. Every node consist of two parts. The first part is called INFO, contains information of the data and second part is called LINK, contains the address of the next node in the list. A variable called START, always points to the first node of the list and the link part of the last node always contains null value. A null value in the START variable denotes that the list is empty.

NODE

START

NULL

Fig-2.2.1

Along with the linked list in the memory, a special list is maintained which consists of list of unused memory cells or unused nodes. This list is called list of available space or availability list or list of free storage or free storage list or free pool. A variable AVAIL is used to store the starting address of the availability list.Sometimes, during insertion, there may not be available space for inserting a data into a data structure, then the situation is called OVERFLOW. Programmers generally handle the situation by checking whether AVAIL is NULL or not.The situation where one wants to delete data from a data structure that is empty is called UNDERFLOW. The situation is encountered when START is NULL.

Linked Representation of Stack

Consider the stack of integers S = 29,7,11 (29 is the top, 11 the bottom). The logical order of the values in a stack is very clear; first comes the top element, next comes the element just below the top element, etc. In a linked implementation, this relationship will be explicitly represented: the memory cell containing the top element will also contain a pointer to the second element, the memory cell containing the second element will contain a pointer to the third element, etc. What about the memory cell containing the bottom element?

What about S itself? It will be a variable in our program, explicitly declared. So it will be a box. What is in the box? Well, one thing for sure, we need to store a pointer to the top element. In addition, we could store anything else we like.

In terms of actually coding this in C, some things are already settled.

The memory cells for stack elements contain two pieces of information, a value and a `next' pointer, therefore they will have to be records/structures.
S is probably a different type than the `elements' in the stack, because it has no associated value, just a pointer to the top stack element.

Knowing these two things, it is now easy to write the TOP operation - all it has to do is follow the pointer from S and look up the value stored in that memory cell.

An important question is, how will we represent the EMPTY stack? There are actually several possibilities.

In S we could store the number of elements that it contains, in which case the empty stack would be represented by setting this value to zero.
Or we could have a boolean (logical) variable telling us whether or not S is empty.
The simplest solution is to set S's TOP pointer to NULL when S is empty (of course we are sure it will be non-NULL when S is non-empty).

A typical input to the POP operation is the stack S (as above):

That is our before diagram. Here is what S will look like after the POP:

That is our after diagram. All we have to do, to design the inner workings of the POP operation, is to list all the differences between the before and after diagrams. How many can you see?

The memory cell containing 29 is gone.
In S, the TOP pointer is pointing at a different cell.

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	Define multi stack	Dec.2013	2
Q.2	What is the disadvantage of representing a stack or queue by link list?	June 2014	3

BACK

Unit-II

Application of Stack (Recursion)

Unit 02/Lect 03

Stacks are used in recursion programs
Stacks are used in function calls

· Stacks are used in interrupt implementation

There are two important applications of stacks.

a) Recursion

b) Arithmetic Expression

(a) Recursion

Recursion is and important facility in many programming languages. There are many problems whose algorithmic description is best described in a recursive manner.

A function is called recursive if the function definition refers to itself or does refers to another function which in turn refers back to the same function. In-order for the definition not to be circular, it must have the following properties:

(i) There must be certain arguments called base values, for which the function does not refer to itself.

(ii) Each time the function does refer to itself, the argument of the function must be closer to a base value.

A recursive function with those two properties is said to be well defined.

Let us consider the factorial of a number and its algorithm described recursively:

We know that N! = N * (N-1)!

(N-1)! = N-1 * (N-2)! and so on up to 1.

FACT(N)

1. if N=1

return 1

2. else

return N * FACT(N-1)

3. end

Let N be 5.

Then according to the definition FACT(5) will call FACT(4), FACT(4) will call FACT(3), FACT(3) will call FACT(2), FACT(2) will call FACT(1). Then the execution will return back by finishing the execution of FACT(1), then FACT(2) and so on up to FACT(5) as described below.

1) 5! = 5 * 4!

2) 4! = 4 * 3!

3) 3! = 3 * 2!

4) 2! = 2 * 1!

5) 1! = 1

6) 2! = 2 * 1 = 2

7) 3! = 3 * 2 = 6

8) 4! = 4 * 6 = 24

9) 5! = 5 * 24 = 120

From above example it is clear that every sub function contain parameters and local variables. The parameters are the arguments which receive values from objects in the calling program and which transmit values back to the calling program. The sub-function must also keep track of the return address in the calling program. This return address is essential since control must be transferred back to its proper place in the calling program. After completion of the sub-function when the control is transferred back to its calling program, the local values and returning address is no longer needed. Suppose our sub-program is a recursive one, when it call itself, then current values must be saved, since they will be used again when the program is reactivated.

Thus, in recursive process a data structure is required to handle the data of ongoing called function and the function which is called at last must be processed first. i.e the data accessed last must be processed fist i.e Last in first out principle. So, a stack may be suitable data structure that follows LIFO to implement recursion.

(b) Arithmetic Expression [RGPV/June 2012 (7)] [RGPV/Dec 2013 (7)]

This section deals with the mechanical evaluation or compilation of infix expression. The stack is find to be more efficient to evaluate an infix arithmetical expression by first converting to a suffix or postfix expression and then evaluating the suffix expression. This approach will eliminate the repeated scanning of an infix expressions in order to obtain its value.

A normal arithmetic expression is normally called as infix expression. E.g A+B

A Polish mathematician found a way to represent the same expression called polish notation or prefix expression by keeping operators as prefix. E.g +AB

We use the reverse way of the above expression for our evaluation. The representation is called Reverse Polish Notation (RPN) or postfix expression. E.g. AB+

The arithmetic expression evaluation is performed in two phases, they are

Ø Conversion of infix to postfix expression

Evaluation of arithmetic expressions

· Notation can be infix, postfix or prefix.

Infix: operator is between operands

A + B

Postfix : operator follows operands

AB+

Prefix: operator precedes operands

+AB

· Operators in a postfix expression are in correct evaluation order.

Postfix Expressions

Infix Postfix

a + b * c abc*+

(precedence of * is higher than of +)

a + b * c / d abc*d/+

(precedence of * and / are same and they are left associative)

Parentheses override the precedence rules:

(a + b) * c

ab+c

· More examples

Infix Postfix

(a + b) * (c – d) ab+cd-*

a – b / (c + d * e) abcde*+/-

((a + b) * c – (d – e))/(f + g) ab+c*de - - fg+/

Order of precedence for 5 binary operators:

power (^)

multiplication (*) and division (/)

addition (+) and subtraction (-)

The association is assumed to be left to right except in the case of power where the association is assumed from right to left.

i.e. a + b + c = (a+b)+c = ab+c+

a^b^c = a^(b^c) = abc^^

S.NO

RGPV QUESTIONS

Year

Marks

Q.1

Define the following

Polish notation, Infix notation,reversh Polish notation

June 2012

Q.2

Convert the following expression into postfix and prefix form.

(A+B)*C/D+E^F^G

B*(-C)*D+A^D

Dec 2013

BACK

Application Of Stack(Infix,postfix,prefix)

Unit 02/Lect 04

Algorithm of Converting an Infix Expression to Postfix

[RGPV/Dec2011 (10)] [RGPV/June2011 (10)]

[RGPV/Dec 2014]

Transform ( ):

Description: Here I is an arithmetic expression written in infix notation and P is the equivalent postfix

expression generated by this algorithm.

1. Push “(“ left parenthesis onto stack.

2. Add “)” right parenthesis to the end of expression I.

3. Scan I from left to right and repeat step 4 for each element of I

until the stack becomes empty.

4. If the scanned element is:

(a) an operand then add it to P.

(b) a left parenthesis then push it onto stack.

(i) Pop from stack and add to P each operator

which has the same or higher precedence then

the scanned operator.

(ii) Add newly scanned operator to stack.

(d) a right parenthesis then:

(i) Pop from stack and add to P each operator

until a left parenthesis is encountered.

(ii) Remove the left parenthesis.

[End of Step 4 If]

[End of step 3 For Loop]

5. Exit.

BACK

Evaluating a Postfix Expression

Evaluate ( ):

Description: Here P is a postfix expression and this algorithm evaluates it.

1. Add a “)” right parenthesis at the end of P.

2. Scan P from left to right and repeat steps 3 & 4 for each element

of P until “)” is encountered.

3. If an operand is encountered, push it onto stack.

4. If an operator  is encountered then:

(a) Pop the top two elements from stack, where A is the

top element and B is the next to top element.

(b) Evaluate B  A.

[End of Step 4 If]

[End of step 2 For Loop]

5. Set VALUE equal to the top element on the stack.

6. Exit.

S.NO

RGPV QUESTIONS

Year

Marks

Q.1

Write an algorithm to convert infix to postfix expression. Explain with example

Dec 2011

June2011

Q.2

Convert the following infix expression to prefix expression and give various steps in evolution using stack

(5*3^2)/(3+(7+3)/10)

Dec 2014

BACK

QUEUE(Representation of Queue)

Unit 02/Lect 05

QUEUE : [RGPV/June 2011(10)]

Queue is a linear data structure in which insertion can take place at only one end called rear end and deletion can take place at other end called top end. The front and rear are two terms used to represent the two ends of the list when it is implemented as queue. Queue is also called First In First Out (FIFO) system since the first element in queue will be the first element out of the queue.

Queue is a Linear Data Structure which follows First in First out mechanism.

It means: the first element inserted is the first one to be removed

Queue uses two variables rear and front. Rear is incremented while inserting an element into the queue and front is incremented while deleting element from the queue

rear

front

Insert(A) Insert(B) Insert(C) Insert(D) Delete()

Fig-2.5.1

Valid Operations on Queue: [RGPV/Dec 2012 (7)]

Inserting an element in to the queue
Deleting an element in to the queue
Displaying the elements in the queue

Note:

· While inserting an element into the queue, queue is full condition should be checked

· While deleting an element from the queue, queue is empty condition should be checked

Array implementation of Queue

Like stacks, queues may be represented in various ways, usually by means of one way list or linear arrays. Generally, they are maintained in linear array QUEUE. Two pointers FRONT and REAR are used to represent front and last element respectively. N may be the size of the linear array. The condition when FRONT is NULL indicate that the queue is empty. The condition when REAR is N indicated overflow.

We can use a primitive array to store items as a queue. Just keep track of two indices: enqueue new items to index enqueueHere,

dequeue items from index dequeueHere
Leads to problem: enqueueHere may reach the last array index,Solutions:

Shift all values to front of array and update front and back

Think of array as circular.

BACK

Fig-2.5.2

Operations on queue

Insert ( ):

Description: Here QUEUE is an array with N locations. FRONT and REAR points to the front and rear of

the QUEUE. ITEM is the value to be inserted.

1. If (REAR == N) Then [Check for overflow]

2. Print: Overflow

3. Else

4. If (FRONT and REAR == 0) Then [Check if QUEUE is empty]

(a) Set FRONT = 1

(b) Set REAR = 1

5. Else

6. Set REAR = REAR + 1 [Increment REAR by 1]

[End of Step 4 If]

7. QUEUE[REAR] = ITEM

8. Print: ITEM inserted

[End of Step 1 If]

9. Exit

Delete ( ): BACK

Description: Here QUEUE is an array with N locations. FRONT and REAR points to the front and rear of

the QUEUE.

1. If (FRONT == 0) Then [Check for underflow]

2. Print: Underflow

3. Else

4. ITEM = QUEUE[FRONT]

5. If (FRONT == REAR) Then [Check if only one element is left]

(a) Set FRONT = 0

(b) Set REAR = 0

6. Else

7. Set FRONT = FRONT + 1 [Increment FRONT by 1]

[End of Step 5 If]

8. Print: ITEM deleted

[End of Step 1 If]

9. Exit

BACK

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	What are the limitations of linear queue. Write the advantages of queue over stack.	June 2011	10
Q.2	Design and implement algorithms that maintain a queue which can be subjected to insertion and deletion.	Dec 2012	7

BACK

Circular Queue, D-Queue Priority Queue

Unit 02/Lect 06

Circular Queue : [RGPV/Dec 2011 (10)[RGPV/Dec2014]

The linear arrangement of the queue always considers the elements in forward direction. In the above two algorithms, we had seen that, the pointers front and rear are always incremented as and when we delete or insert element respectively. Suppose in a queue of 10 elements front points to 4^th element and rear points to 8^th element as follows.

1 2 3 4 5 6 7 8 9 10

QUEUE XX XX XX XX XX

FRONT REAR

When we insert two more elements then the array will become

1 2 3 4 5 6 7 8 9 10

QUEUE XX XX XX XX XX XX XX

FRONT REAR

Fig-2.6.1

BACK

Operationson Circular queue

Insert Circular ( ):

Description: Here QUEUE is an array with N locations. FRONT and REAR points to the front and rear

elements of the QUEUE. ITEM is the value to be inserted.

1. If (FRONT == 1 and REAR == N) or (FRONT == REAR + 1) Then

2. Print: Overflow

3. Else

4. If (REAR == 0) Then [Check if QUEUE is empty]

(a) Set FRONT = 1

(b) Set REAR = 1

5. Else If (REAR == N) Then [If REAR reaches end if QUEUE]

6. Set REAR = 1

7. Else

8. Set REAR = REAR + 1 [Increment REAR by 1]

[End of Step 4 If]

9. Set QUEUE[REAR] = ITEM

10. Print: ITEM inserted

[End of Step 1 If]

11. Exit

Delete Circular ( ):

Description: Here QUEUE is an array with N locations. FRONT and REAR points to the front and rear

elements of the QUEUE.

1. If (FRONT == 0) Then [Check for Underflow]

2. Print: Underflow

3. Else

4. ITEM = QUEUE[FRONT]

5. If (FRONT == REAR) Then [If only element is left]

(a) Set FRONT = 0

(b) Set REAR = 0

6. Else If (FRONT == N) Then [If FRONT reaches end if QUEUE]

7. Set FRONT = 1

8. Else

9. Set FRONT = FRONT + 1 [Increment FRONT by 1]

[End of Step 5 If]

10. Print: ITEM deleted

[End of Step 1 If]

11. Exit

BACK

Types of QUEUE

There are two types of Queue

Ø Priority Queue

Ø Double Ended Queue

Priority Queue

A priority queue is a collection of elements such that each element has been assigned a priority value such that the order in which elements are deleted and processed comes from the following rules

An element of higher priority is processed before any element of lower priority.
Two elements with the same priority are processed according to the order in which they were added to the queue.

There are various ways of maintaining a priority queue in memory. One is using one way list. The sequential representation is never preferred for priority queue. We use linked Queue for priority Queue.

Double Ended Queue [RGPV/Dec 2013 (3)] [RGPV/June 2011 (5)]

A Double Ended Queue is in short called as Deque (pronounced as Deck or dequeue). A deque is a linear queue in which insertion and deletion can take place at either ends but not in the middle.

There are two types of Deque.

1. Input restricted Deque

2. Output restricted Deque

A Deque which allows insertion at only at one end of the list but allows deletion at both the ends of the list is called Input restricted Deque.

A Deque which allows deletion at only at one end of the list but allows insertion at both the ends of the list is called Output restricted Deque.

BACK

Aplications of Queues:

Real life examples

· Waiting in line

· Waiting on hold for tech support

Applications related to Computer Science

· Threads

· Job scheduling (e.g. Round-Robin algorithm for CPU allocation)

(i) engines.

S.NO	RGPV QUESTION	YEAR	MARKS
Q.1	Explain D-queue and priority queue	June 2011 Dec 2013	5 2
Q.2	Write functions of “Finding Size, Checking Empty, Checking Full” for the implementation of a queue in circular array to indicate emptiness.	Dec 2011	10
Q.	Write an algorithm for insertion and deletion operation on circular queue.	Dec 2014	7

BACK

SINGLE LINKED LIST

Unit 02/Lect 07

Linked List: [RGPV/Dec 2012 (7)] [RGPV/Dec 2013 (7)] [RGPV/Dec 2013 (7)]

To overcome the disadvantage of fixed size arrays linked list were introduced.

A linked list consists of nodes of data which are connected with each other. Every node consist of two parts data and the link to other nodes. The nodes are created dynamically.

NODE

Data link

BACK

Fig-2.7.1

Types of Linked Lists:

Single linked list
Double linked list
Circular linked list

Valid operations on linked list:

Inserting an element at first position
Deleting an element at first position
Inserting an element at end
Deleting an element at end
Inserting an element after given element
Inserting an element before given element
Deleting given element

Algorithms

Traversing()

It refers to a operation in which all elements of the list are accessed only once. Algorithm for traversing in Link list is as follow:

1. SET PTR = START

2. REPEAT THE STEPS 3 AND 4 WHILE PTR != NULL

3. APPLY PROCESS TO INFO[PTR] //ACCESSING THE ELEMENT

4. SET PTR = LINK[PTR] //GOING TO THE NEXT LINKED NODE

5. EXIT

Insertaatfirst()

1. IF ( AVAIL == NULL) PRINT OVERFLOW AND EXIT

2. SET NEW = AVAIL AND AVAIL = LINK[AVAIL]

3. SET INFO[NEW] = ITEM

4. SET LINK[NEW] = START

5. SET START = NEW

6. EXIT

Insert Specific ( ): [RGPV/Dec 2011 (10)] [RGPV/Dec 2012 (7)]

Description: Here START is a pointer variable which contains the address of first node. NEW is a pointer

variable which will contain address of new node. N is the value after which new node is to be inserted and

ITEM is the value to be inserted.

BACK

1. If (START == NULL) Then

2. Print: Linked-List is empty. It must have at least one node

3. Else

4. Set PTR = START, NEW = START

5. Repeat While (PTR != NULL)

6. If (PTR->INFO == N) Then

7. NEW = New Node

8. NEW->INFO = ITEM

9. NEW->LINK = PTR->LINK

10. PTR->LINK = NEW

11. Print: ITEM inserted

12. ELSE

13. PTR = PTR->LINK

[End of Step 6 If]

[End of While Loop]

[End of Step 1 If]

14. Exit

S.NO	RGPV QUESTION	YEAR	MARKS
Q.1	Compare array implementation with linked list implementation. Write a function to insert a node in linear linked list after a specific node .	Dec 2011	10
Q.2	How a linked list can be implemented using arrays.	Dec 2012	7
Q.3	Explain and write an algorithm to insert a node into a linked list	Dec 2012	7
Q.4	Write a function that create a new linear linked list	Dec 2013	7
Q.5	Discuss about the implementation of fixed size block(Array) and variable size block dynamic memory allocation(linked list)	Dec 2013	7

BACK

Deletion, Searching in Linked list

Unit 02/Lect 08

Delete Last ( ):

Description: Here START is a pointer variable which contains the address of first node. PTR is a pointer

variable which contains address of node to be deleted. PREV is a pointer variable which points to previous

node. ITEM is the value to be deleted.

1. If (START == NULL) Then [Check whether list is empty]

2. Print: Linked-List is empty.

3. Else

4. PTR = START, PREV = START

5. Repeat While (PTR->LINK != NULL)

6. PREV = PTR [Assign PTR to PREV]

7. PTR = PTR->LINK [Move PTR to next node]

[End of While Loop]

8. ITEM = PTR->INFO [Assign INFO of last node to ITEM]

9. If (START->LINK == NULL) Then [If only one node is left]

10. START = NULL [Assign NULL to START]

11. Else

9. PREV->LINK = NULL [Assign NULL to link field of second last node]

[End of Step 9 If]

10. Delete PTR

11. Print: ITEM deleted

[End of Step 1 If]

12. Exit

Delete Specific ( ): [RGPV/June 2012 (7)]

BACK

Description: Here START is a pointer variable which contains the address of first node. PTR is a pointer

variable which contains address of node to be deleted. PREV is a pointer variable which points to previous

node. ITEM is the value to be deleted.

1. If (START == NULL) Then [Check whether list is empty]

2. Print: Linked-List is empty.

3. Else If (START->INFO == ITEM) Then [Check if ITEM is in 1st

node]

4. PTR = START

5. START = START->LINK [START now points to 2nd

node]

6. Delete PTR

7. Else

8. PTR = START, PREV = START

9. Repeat While (PTR != NULL)

10. If (PTR->INFO == ITEM) Then [If ITEM matches with PTR->INFO]

11. PREV->LINK = PTR->LINK [Assign LINK field of PTR to PREV]

12. Delete PTR

13. Else

14 PREV = PTR [Assign PTR to PREV]

15. PTR = PTR->LINK [Move PTR to next node]

[End of Step 10 If]

[End of While Loop]

16. Print: ITEM deleted

[End of Step 1 If]

17. Exit

BACK

Search Unsorted ( ):

Description: Here START is a pointer variable which contains the address of first node. ITEM is the value

to be searched.

1. Set PTR = START, LOC = 1 [Initialize PTR and LOC]

2. Repeat While (PTR != NULL)

3. If (ITEM == PTR->INFO) Then [Check if ITEM matches with INFO field]

4. Print: ITEM is present at location LOC

5. Return

6. Else

7. PTR = PTR->LINK [Move PTR to next node]

8. LOC = LOC + 1 [Increment LOC]

9. [End of If]

10. [End of While Loop]

11. Print: ITEM is not present in the list

12. Exit

S.NO

RGPV QUESTION

YEAR

MARKS

Q.1

Write an algorithm to delete a node in a linear linked list.

June 2012

Q.2

Write an algorithm for insertion and deletion operation on circular queue.

Dec 2014

BACK

Types of Linked list

Unit 02/Lect 09

Non-Circular Single Linked List

Fig-2.9.1

Circular Single Linked List [RGPV/June2012 (7)] BACK

Fig-2.9.2

Circular Single Linked List Ascending list contains Efficient Node

Fig-2.9.2

Fig-2.9.3

Double

Linked List with Efficient Node

Fig-2.9.4

S.NO	RGPV QUESTION	YEAR	MARKS
Q.1	Differentiate between linked list and Circular linked list	June 2012	7

BACK

Garbage Collection and Compaction

Unit 02/Lect 10

Garbage Collection :[RGPV/Dec 2014]

Garbage collection is the process of collecting all unused nodes and returning them to available space. This process is carried out in two phases:

In first phase, known as marking phase, all nodes in use are marked.

In second phase, all unmarked nodes are returned to the available space list.

The second phase is trivial when all nodes are of a fixed size. In this case, the second phase requires only the examination of each node to see whether or not it has been marked. In this situation it is only the first or marking phase that is of any interest in designing algorithm. When variable size nodes are in use, it is desirable to compact memory so that all free nodes form a contiguous block of memory. In this case, the second phase if referred to as memory compaction. Compaction of disk space to reduce average retrieval time is desirable even for fixed size.

Application of Linked List:

Polynomial Manipulation: [RGPV/June2011 (10)] [RGPV/Dec2011 (10)]

A polynomial has multiple terms with same information such as coefficient and powers. Each term of a polynomial is treated as a node of a list and normally a linked list used to represent a polynomial. The implementation of polynomial addition is the only operation that is discussed many place. Multiplication of polynomials can be obtained by performing repeated additions.

Each polynomial is stored in decreasing order of by term according to the criteria of that polynomial. i.e. The term whose powers are more are stored at first node and the least power term is stored at last. This ordering of polynomials makes the addition of polynomials easy. In fact two polynomials can be added or multiplied by scanning each of their terms only once.

Linked Dictionary: BACK

An important part of any compiler is the construction and maintenance of a dictionary containing names and their associated values. Such dictionary is also called Symbol Table. There may be several symbols corresponding to variable names, labels, literals, etc.

The constraints, which must be considered in the design of the symbol tables, are processing time and memory space. There are many phases associated with the construction of symbol tables. The main phases are building and referencing.

It is very easy to construct a very fast symbol table system, provided that a large section of memory is available. In such case a unique address is assigned to each name. The most straightforward method of accessing a symbol table is linear search technique. This method involves arranging the symbols sequentially in memory via an array or by using a simple linked list. An insertion can be easily handled by adding new element to the end of the list. When it is desired to access a particular symbol, the table is searched sequentially from its beginning until it is found. It will take n/2 comparisons to find a particular symbol. The insertion mechanism is fast but the referencing is extremely slow. The referencing will be fast if we use binary search technique. To implement a binary search on symbol table a tree representation is used.

S.NO

RGPV QUESTION

YEAR

MARKS

Q.1

Representation of polynomial using linked list.

June 2011

Dec 2011

Q.2

Write in brief about following:

1)Garbage collection

2) Back tracking.

Dec2014

BACK

REFERENCCE
BOOK	AUTHOR	PRIORITY
Data structure and algorithm	SEYMOUR LIPSCHUTZ	1
Fundamentals of data Structures	Horowitz and Sahani,	2

BACK