Linked List

TWO MARK QUESTIONS...

1) What is a linear linked list?
If each item of a list itself has the pointer to the next item, which gives an explicit ordering of elements is known as linear linked list. Each item contain the information field which contain the actual information and the next address field which is used to access the next item.

2) What is empty list or Null list?
The list having no items is called empty list or null list. The external pointer to empty list is null pointer. The empty list is initialized as list=null

3) Write the procedure for inserting an element in the list.
p=getnode( );
info(p)=x;
next(p)=list;
list=p;

4) Write the procedure for deleting an element from the list.
p=list;
list=next(p);
x=info(p);
freenode(p);

5) What are the disadvantages of representing a stack or queue by linked list?
A node in linked list occupies more storage than corresponding element as it needs an explicit pointer for next item.
Additional time is spent in managing the available list. When an node is deleted, modifications are needed to either the previous or next node or both.

6) What are the advantages of using a linked list rather than array?
While inserting or deleting element from the middle of an array, all the elements should be moved to avoid the empty locations. But, linked list does not need to move all elements, but only the node pointers of two nodes will have to be modified.

7) What is a header node?
The extra node kept in front of the list is called header node. It does not represent any item in the list. It could have the global information about the list.

8) What are the limitations of array implementation of linked list?
The number of nodes needed for execution of a program can not be predicted when the program is written.
The nodes declared at beginning should remain allocated to that program till the execution is complete.

9) What is a circular linked list?
Circular linked list is the list in which the end node of the list point to the header node.

10) What is dangling pointer?
If the link pointing the node is freed by free(pointer), the node will not be used further. But, it contain some illegal information. The value of p is a valid address and the pointer that points to it can be given a *P. This P is called dangling pointer.


OTHER QUESTIONS…
1) Write a program to implement stack using linked list. (16)
2) Write a program to implement queue using linked list (16)
3) Write the procedure to delete all occurrences of number 4 from the linked list.(8)
4) Write the procedure to insert an element in the ordered list. (4)
5) Explain the list implementation of priority queue. (6)
6) Explain about header nodes, and what are the uses of it? (6)
7) Explain how linked list could be represented in an array (10)
8) Write about how the dynamic allocation and freeing of nodes takes place with example. (8)
9) How will you implement a linked list with dynamic memory allocation? (16)
10) Compare the dynamic and array implementation of lists. (6)



WORKS FOR YOU…
1) Explain with necessary diagrams to represent how nodes could be added and deleted in a linked list, in the front, last and middle. (16)
2) Unordered lists are best suited for priority queue implementation. Is this statement true or false? State reasons for your answer. (6)
3) What is the average number of nodes accessed in searching for a particular element in an unordered list? In an ordered list? In an unordered array? In an ordered array?