Programming and Data Structures

528 Programming and Data Structures

SU MM AR Y

1) The list implemented using an array is called static list. A list is a series of linearly arranged

numbers of the same type. The list can be of basic data type or custom data type.

2) Static implementation can be done using arrays.

3) The simple list can be created using an array in which elements are stored in successive memory

locations.

4) In the list, we have n, (n -1) as predecessor and (n+1) as successor elements. In other words, for

any number in the list, there exist a left element to it as predecessor and the right element as

successor. The first element does not have a predecessor and the last element does not have a

successor.

5) A linear list belonging to list subclass is called a stack. The insertion of an element onto the stack

is called as 'push' and deletion operation is called 'pop.'

6) A queue is a non-primitive, linear data structure, and a subclass of list data structure. It is an

ordered, homogenous collection of elements in which elements are appended at one end called

rear end and elements are deleted at other end called front end.

7) In a single linked list, two successive nodes of the linked list are linked with each other in a

sequential linear manner.

8) In a double linked list, the data structure holds two pointer fields. In the single linked list, the

address of only the next element is pointed. In addition, in a double linked list the addresses of

next as well as preceding elements are linked with the current node.

EXERC ISES

A) Answ er the following questions.

1) Explain stack and queues.

2) Explain representation of stack and queues.

3) Distinguish between a stack and a queue.

4) Make a distinction between static and dynamic implementations.

5) Explain insertion and deletion processes with stack and queues.

6) Explain a single linked list.

7) What is a header? Explain its role in the linked list.

8) Explain insertion and deletion operations with a single linked list.

9) Explain a double linked list.

10) What are the applications of stacks and queues? Explain briefly.

11) What are the different types of queues available? Explain their representation with linked

lists.

B) Select the appropriate option for each o f the following questions.

1) The stack is based on the rule

a) first in last out b) last in first out

c) both (a) and (b) d) first in first out

2) The push () operation is used

a) to insert an element b) to remove an element

c) to move an element d) all of the above

Linear Data Structure 529

3) The pop operation removes

a) the element lastly inserted

c) any element randomly

4) The top pointer is increased

a) when push () operation is done

c) both (a) and (b)

b) first element of the stack

d) none of the above

b) when pop () operation is done

d) none of the above

5) If push is performed on a stack holding elements equal to its capacity then such a situation

is called

a) stack overflow b) stack underflow

c) illegal operation d) none of the above

6) From the given options one is not a stack application

(a) template

(c) reverse string

7) Queue follows the rule

a) FIFO

c) LILO

8) The rear end of the queue is used

a) to insert an element

c) both (a) and (b)

b) recursion

d) conversion of number

b) LIFO

d) FILO

b) to remove an element

d) none of the above

9) When an element is inserted in a queue, the position of rear

a) increases

c) remains constant

10) Linked list can be implemented by

a) static implementation

c) early binding

11) The header is used to point

a) first node of the list

c) NULL value

12) Traversing means

a) visiting all the nodes of the list

c) randomly accessing the elements d) none of the above

13) In the linked list when an element is inserted

a) memory is allocated to a node b) memory is deallocated from the node

c) neither memory allocated nor deallocated

d) none of the above

14) In the doubly linked list the previous pointer of the first node

a) has null value b) contains the address of the next node

c) contains the address of the header

d) none of the above

b) decreases

d) none of the above

b) dynamic implementation

d) none of the above

b) last node of the list

d) none of the above

b) shifting all the nodes at forward