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
Step4-:repeat step 5 and 6 while numlist #null
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.
If top=max,then write overflow and exit
If top=0,then:write overflow and exit
If TOP=0,then write overflow and exit
Ans(4). PUSH(city stack,berlin,top)
If TOP=MAX then write overflow and exit
Repeat step 3 while top1#0
Set count:=count+1 & top1:=top1-1
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.
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:=F(copies F in the info part of node 3)
1)set ptr:=start and set item:=0
2)if item=info[start] then set loc:=null and goto step 7
3)set save:=start and ptr:=link[ptr]
4)repeat step 5 & 6 while ptr:!=null
5)if item=info[ptr] then set locp:=save & loc:=ptr and goto step 7
6)set save:=ptr and ptr:=link[ptr]
8)set link[loc]:=avil and avail:=loc set ptr:=start and
9)if avail=null then write overflow and exit
10)set new:=avail and set avail!=link[link]
12)set link[new]:=locp[link] and link[locp]:=new
1) [OVERFLOW?] if AVAIL=NULL,then:write:OVERFLOW, and Exit.
2) [remove first node from the AVAIL list]
Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
3) INFO[NEW]:=J[copies j into new node]
4) set LINK[NEW]:=LINK and LINK[NEW]:=NULL
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]
Q8. Consider the following Stack:
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.
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
This procedure inserts 50 elements onto the stack.
1) Set TOP:=TOP+1
2) Set STACK[TOP]:=50
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.