Linked Lists: Two Marks Important Questions and Answers

Data Structures using C++ Program

Chapter 5: Linked Lists

Two Marks Questions with Answers

1. Differentiate between arrays and linked list.

Answer:

 In arrays any element can be accessed randomly with the help of index of array, whereas in lists any element can be accessed by sequential access only.

Insertions and deletions of data is difficult in arrays on the other hand insertion and deletion of data is easy in lists.

2.  State the advantages of circular list over doubly linked list.

Answer:

In circular list the next pointer of last node points to head node, whereas in doubly linked list each node has two pointers: One previous pointer and another is next pointer. The main advantage of circular list over doubly linked list is that with the help of single pointer field we can access head node quickly. Also some amount of memory get saved because in circular list only one pointer field is reserved.

3. What is a linked list ?

Ans  :

A linked list is a set of nodes where each node has two fields 'data' and 'link'. The data field is used to store actual piece of information and link field is used to store address of next node.

4. What is the advantage of doubly linked list over a singly linked list ?

Answer:

 The doubly linked list has two pointer fields. One field is previous link field and another is next link field.

Because of these two pointer fields we can access any node efficiently whereas in singly linked list only one pointer field is there which stores forward pointer, which makes accessing of any node difficult one.

5. Why is linked list used for polynomial arithmetic ?

Answer:

Following are the reasons for which linked list is used for polynomial arithmetic ‒

i) We can have separate coefficient and exponent fields for representing each term of polynomial. Hence there is no limit for exponent. We can have any number as an exponent.

ii) The arithmetic operation on any polynomial of arbitrary length is possible using linked list.

6. Explain the term dynamic memory.

Answer:

The dynamic memory allocation means one can allocate the memory of required size, as well as de allocate (free) it. So that freed memory can be utilized further. Also the memory can be reallocated.

7. Represent the polynomial 10x³ + 7x² + 6x + 5 with the help of array.

Answer:

For single dimensional array the polynomial can be arranged like this.

The index acts like a exponent and value acts as a coefficient of the term. Let us take array a[5]

8. Define sentinel nodes, header node and tail node.

Ans. :

 • In some implementations an extra 'sentinel' or 'dummy' node may be added before the first data record or after the last one. This node is called as sentinel node. This type of node does not hold or reference any data managed by the data structure.

• The head node is the starting node of the linked list.

• The tail node is the terminating or the last node of the linked list.

9. List the applications of linked list.

Answer:

Various applications of linked list are:

1. Linked list can be used to implement linear data structures such as stacks and

qeues.

2. Linked list is useful for implementing the non‒linear data structures.

3. Linked list.

4. Polynomial representation, and operations such as addition, multiplication and evaluation can be performed using linked list.

10. Write a procedure to insert an element in the beginning of a list ADT implemented using a singly linked list.

• There are three possible cases when we want to insert an element in the linked list ‒

a) Insertion of a node as a head node

b) Insertion of a node as a last node

c) Insertion of a node after some node.

We will see the case

a) first ‒

void sll:: insert head()

{

   node *New,*temp;

   New new node;

   cout<<"\n Enter The element which you want to insert";

   cin>>New‒>data;    // There is no node in the linked list. That means the linked list is empty

   if(head= NULL)

   head=New;

   else

   {

      temp=head;

      New‒>next = temp;

      head=New;

   }

}

If there is no node in the linked list then value of head is NULL. At that time if we want to insert 10 then