### 1. Explain the concept of header nodes in the design of one-way and two-way linked lists.

Ans. : Header node is the first node in the linked list.

In case of one way linked list, there is 2 parts in the node. First is the information part which contains NULL and the second is the link part which contains the address of the second node.

Where as In case of two way linked list , there are three parts. The first part is BACK,which contain the address of the previous node.the second part is the info part which contain the data part.the last part is also the link part which contain the address of the next node.

### 2.Can we perform binary search in linked list, if no then illustrate.the reason.

Ans. No, we can not perform binary search in linked list.

suppose we have 10 nos. in the array, for any no. to be searched we'll check it first with the middle no. i.e. 5th no.
If it matches OK, otherwise if it is less than it, u'll check the middle no. of 1 & 5 i.e. 3 and so on.
If it is greater then we will check it with the middle no. of 5 & 10 i.e. 7 and so on. The search is carried till the no. is found or till middle no. equal to bounding no, i.e. no. not found.
Coming to linked list, it is a way to store information without using arrays. The problem with array is we should know the maximum size in advance, in order to avoid it we use linked lists.
i.e. we'll create a node containing information & the address of next node.

### 3.Differentiate between static memory allocation and dynamic memory allocation. Illustrate various memory management functions

Ans. Dynamic memory allocation is at runtime. Static memory allocation is before run time, but the values of variables may be changed at run time.
Static memory allocation saves running time, but can't be possible in all cases.

### 4.Can we break the cycle of link list, if yes how is it possible?

Ans: we can not break the cycle of link list.Because cycle of link list is possible in circular header list and it is a header list where the last node point back to the header node.

header list in memory,the avail list will always be maintained as an ordinary linked list .And if we break the cycle then the link list will be no more then circular link list.

### 5.Suppose NUMLIST is the linked list in the memory consisting of numerical values. Write a procedure for each of the following:

a) Finding the maximum MAX of the values in NUMLIST

b) Finding the average AVG of the values in NUMLIST

Ans(a).step 1-:node *numlist

Step3-: Int max=0

Step4-: Repeat step 5and 6 while numlist#null

Step5-: If(numlist.score>max)

Step6-: max=numlist.score

Write max

Step7-: exit

Ans(b).step1-:node*numlist

Step3-:int num=0,sum=0;

Step4-:repeat step 5 and 6 while numlist #null

Step5-:num:=num+1

Step6-:sum:=sum+num

Write sum

Step7-:numlist=sum/num

Step8-:exit

### 6.Consider the stack of city names:

CITYSTAK: London, Paris, New Delhi, Moscow…

### a) Describe following operations:

(i) PUSH(CITYSTAK, Athens)

(ii) POP(CITYSTAK, ITEM)

(iii)POP (CITYSTAK, ITEM)

(iv)PUSH (CITYSTAK, Berlin)

### b) Write a procedure to obtain the capacity of CITYSTAK represented by its top pointer TOP.

Ans(a)(1).push(city stak,Athens,top)

If top=max,then write overflow and exit

Set top:=top+1

City stak[top]:'athens'

Exit

Ans(2).pop(city stak,item,top)

If top=0,then:write overflow and exit

SET ITEM:=citystack[TOP]

TOP:=TOP-1

Exit

Ans(3).POP(citystack,ITEM,TOP)

If TOP=0,then write overflow and exit

Set ITEM:=citystack[TOP]

TOP:=TOP-1

Exit

Ans(4). PUSH(city stack,berlin,top)

If TOP=MAX then write overflow and exit

SET TOP:=TOP+1

Citystack[TOP]:=”EERISM”

Exit

Ans(b): stakcity(top1,top,count)

Set count:=0,top1=top

Repeat step 3 while top1#0

Set count:=count+1 & top1:=top1-1

Write count

Exit

### Q7. Consider the following Link List:

Assume that Element A,B,C, and D Are present in the information part of the nodes of above link list 8,4,3,7 respectively.

i. Write down a algorithm to delete info C from the link list and Add info F in the same Node.

ii. Write down a algorithm to delete C from the link list and also deallocate the memory allocated to C. and Add F in the link list at the place of the C with new memory allocation

iii. Add a new element J in the link list at the end of the list.

iv. Write down a algorithm to traverse the above link list.

Ans:i)DELETE(INFO,ITEM).

This algorithm deletes from a linked list the info part of node 3 and add F in the same.

1) Set ITEM:=C(copies the info part of node 3 in the item)

2) Set INFO[3]:=F(copies F in the info part of node 3)

3) return

ii) DEL(ptr,start,loc,locp,item,sum)

1)set ptr:=start and set item:=0

2)if item=info[start] then set loc:=null and goto step 7

4)repeat step 5 & 6 while ptr:!=null

5)if item=info[ptr] then set locp:=save & loc:=ptr and goto step 7

8)set link[loc]:=avil and avail:=loc set ptr:=start and

9)if avail=null then write overflow and exit

11)info[new]:='F'

13)Exit

1) [OVERFLOW?] if AVAIL=NULL,then:write:OVERFLOW, and Exit.

2) [remove first node from the AVAIL list]

3) INFO[NEW]:=J[copies j into new node]

5) exit.

1) Set PTR:=START[initializes pointer PTR]

2) Repeat steps 3 and 4 while PTR!=NULL

3) Apply PROCESS to INFO[PTR]

4) Set PTR:=LINK[PTR][PTR now points to the next node]

[End of step 2 loop]

5) exit

Q8. Consider the following Stack:

45

30

25

20

15

i. Write down algorithm to POP first two elements of this stack.

ii. Write down algorithm to Push 50 onto the stack

iii. Differentiate Stack and Array.

i)Pop(STACK,TOP,ITEM,ITEM1)

This procedure deletes the first two element in the stack and assigns it to the variable ITEM,ITEM1.

1) Set TOP:=45

2) Set ITEM:=45.[assigns top element to the ITEM]

3) Set TOP:=TOP-1[decrease TOP by 1]

4) Set ITEM1:=30.[assigns 2nd top element to the ITEM1]

5) Set TOP:=TOP-1

6) Return.

ii)PUSH(STACK,TOP,ITEM,MAXSTK)

This procedure inserts 50 elements onto the stack.

1) Set TOP:=TOP+1

2) Set STACK[TOP]:=50

3) Return.

iii)STACK-A stack is a list of elements in which an element may be inserted or deleted only at one end,called the TOP of the stack.this means,in particular,that elements are removed from a stack in the reverse order of that in which they were inserted into the stack.

Two basic operations performed on the stacks are:-

a)”PUSH” is the term used to insert an element into stack.

b)”POP”is the term used to delete an element from a stack.

ARRAY:- an array is a list of finite no. in of homogeneous elements of the same type. In this we have no such restriction we can do addition or deleted at any location.

Please be aware that the free essay that you were just reading was not written by us. This essay, and all of the others available to view on the website, were provided to us by students in exchange for services that we offer. This relationship helps our students to get an even better deal while also contributing to the biggest free essay resource in the UK!