# DST Unit 2 – Array and Linked Lists questions

## Topic : Array & Array Representation (Key Note and Questions)

Key Note:

• An array is a collection of similar type of data (like int, float or char) which is stored in contiguous memory locations.
• A one-dimensional array is a liner array which has only one row and many columns.
• One-dimensional array can be defined as int arr; means this array arr can store 10 integer value column wise.
• Multi-dimensional array is an array of arrays.
• Two-dimensional array can be considered as multidimensional array. Two-dimensional array can be declared as int arr[m][n].
• Where m is number of rows and n is number of columns.
• Multi-dimensional array can be declared as int arr[n][m][o].

### Questions

1. What is an array? Discuss its type.
2. Explain the Single and Multidimensional Arrays with example.
3. What is row-major order? Explain with example.
4. What is column-major order? Explain with example.
5. Derivation of index formulae for 1-D, 2-D, 3-D and n-D Array.
6. Write an algorithm to multiply two matrices and determine complexity of the algorithm.
7. Determine addressing formula to find the location of (i,j)th element of a m*n matrix stored in column-major order.
8. Consider the linear arrays AAA[5:50],BBB[-5:10] and CCC[1:8]
9. What is sparse matrices? Explain the representation of sparse matrix.
10. Explain the upper triangle and lower triangular sparse matrices. Suggest a space efficient representation for sparse matrices and determine the address determination formulas for it.
11. Write a note on Compaction, Overflow and Underflow in Array term.

## Topic : Linked List (Key Note and Questions)

Key Note:

• Linked List is a linear data structure that stores elements at non-contiguous memory locations.
• Linked List is also dynamic in nature.

## Topic : Singly Linked List (Key Note and Questions)

Key Note:

• Singly Linked List is a unidirectional List where elements can be traversed in only one direction from head to tail
• On Singly Linked List we can perform various operations like list traversal, searching for an element.
• Also we can perform insertion operation on singly linked list like insert element at head, at tail or at particular place.
• Deletion operation on singly linked list like delete at head, at tail or at given particular position.

### Questions

1. What is Singly linked list? Write its Advantage, Application and explain its node structure.
2. Write the Algorithm and Program in C to Create and Traverse a Singly linked list.
3. Write the Algorithm & Program in C to Insert a node at the beginning, at End and at given location of the Singly linked list.
4. Write the Algorithm and Program in C to Search an element of the Singly linked list.
5. Write the Algorithm and Program in C to Delete a node at the beginning, at end and at given location of the Singly linked list.
6. Write the Algorithm and Program in C to Reverses the Singly linked list.

## Topic: Circular Linked List (Key Note And Questions)

Key Note:

• Circular Linked List is a some modified version of singly linked list.
• In singly linked list last element point to null but in circular last elements point to again first element.
•  On Circular Linked List we can perform various operations like list traversal, searching for an element.
• Also we can perform insertion operation on Circular linked list like insert element at head, at tail or at particular place.
• Deletion operation on Circular linked list like delete at head, at tail or at given particular position.

## Topic: Doubly Linked List or Two Way Linked List (Key Note And Questions)​

Key Note:

• Doubly Linked List is a bi-directional List where elements can be traversed in both back and forth direction from head to tail and back tail to head.
• On Doubly Linked List we can perform various operations like list traversal, searching for an element.
• Also we can perform insertion operation on Doubly linked list like insert element at head, at tail or at particular place.
• Deletion operation on singly linked list like delete at head, at tail or at given particular position.

### Questions

1. What is Doubly Linked List? Write its Advantage, Application and explain its node structure.
2. Write the Algorithm and Program in C to Create and Traverse doubly linked list.
3. Write the Algorithm and Program in C to Insert a node at the Beginning, at End and at Specific Location of the doubly linked list.
4. Write the Algorithm and Program in C to Search an element of the Doubly linked list.
5. Write the Algorithm and Program in C to Delete a node from the beginning, from end and from a given location of the doubly linked list.
6. Write the Algorithm and Program in C to Reverse the doubly linked list.

## Topic: Doubly Circular Linked List (Key Note And Questions)​​

Key Note:

• Doubly Linked List is a bi-directional List  as well as circular means, elements can be traversed in both back and forth direction from head to tail and back tail to head.
• And Instead of pointing last element at null in doubly circular last element points to first node.
• On Doubly Circular Linked List we can perform various operations like list traversal, searching for an element.
• Also we can perform insertion operation on Doubly Circular Linked list like insert element at head, at tail or at particular place.
• Deletion operation on Doubly Circular Linked list like delete at head, at tail or at given particular position.

### Questions

1. What is Doubly Circular Linked List? Explain its node structure.
2. Write the algorithm and program in C to create Doubly Circular Linked List.
3. Write the algorithm and program in C to insert a node at the Beginning of the Doubly Circular Linked List.
4. Write the algorithm and program in C to insert a node at the end of the Doubly Circular Linked List.
5. Write the algorithm and program in C to insert a node at the specific location of the Doubly Circular Linked List.
6. Write the algorithm and program in C to traverse the Doubly Circular Linked List.
7. Write the algorithm and program in C to search an element of the Doubly Circular Linked List.
8. Write the algorithm and program in C to delete a node at the beginning of the Doubly Circular Linked List.
9. Write the algorithm and program in C to delete a node at the specified location of the Doubly Circular Linked List.
10. Write the algorithm and program in C to delete a node at the end of the Doubly Circular Linked List.
11. Write the algorithm and program in C that reverses the order of all elements in the Doubly Circular Linked List.

## Topic: Polynomial Representation

1. Explain the Polynomial representation.
2. Explain the Addition of Single variable polynomial.
3. Explain the Subtraction of Single variable polynomial.
4. Explain the Multiplications of Single variable polynomial.
5. Explain the Addition of Two variable polynomial.
6. Explain the Subtraction of Two variable polynomial.
7. Explain the Multiplications of Two variable polynomial.
8. Explain the method to represent the polynomial equation using linked list. Write and explain method to add two polynomial equations using linked list.