Jawaharlal Nehru Technological University Hyderabad B.Tech III DATA STRUCTURES Previous Question Paper (November/December - 2020 - R16)

A Doubly Linked List (DLL) is a complex type of linked list in which each node contains a data field and two pointers, typically named prev and next, which point to the previous and next nodes in the sequence, respectively. This bidirectional traversal capability distinguishes it from a singly linked list.

The primary operations performed on a Doubly Linked List include:

• Insertion: New nodes can be inserted at the beginning, end, or after a specific node. When inserting, the pointers of the new node must be correctly linked to the existing nodes, and the prev and next pointers of adjacent nodes must be updated to maintain the integrity of the list.
• Deletion: To delete a node, the next pointer of the preceding node is updated to point to the node following the one being deleted, and the prev pointer of the succeeding node is updated to point to the node preceding the one being deleted.
• Traversal: DLLs support bidirectional traversal. One can traverse the list forward starting from the head using the next pointers, or backward starting from the tail using the prev pointers.
• Searching: Searching for a specific value involves traversing the list node by node until the data is found or the end of the list is reached.
• Display: This operation involves printing the contents of the list, usually by iterating through the nodes from the head to the tail.

The main advantage of a DLL is the ease of deletion and insertion at any given position, as the previous node is directly accessible, unlike in a singly linked list where a separate pointer to the previous node must be maintained during traversal.

To evaluate a postfix expression, we use a stack data structure to store operands. The algorithm processes the expression from left to right, pushing operands onto the stack and performing operations when an operator is encountered.

Algorithm Steps:

1. Create an empty stack.
2. Scan the postfix expression from left to right.
3. If the scanned character is an operand, push it onto the stack.
4. If the scanned character is an operator, pop the top two elements from the stack. Let the first popped element be A and the second popped element be B.
5. Perform the operation B operator A.
6. Push the result of the operation back onto the stack.
7. Repeat steps 2-6 until the end of the expression is reached.
8. The final value remaining on the stack is the result of the expression.

Example: Evaluate the postfix expression 5 4 6 + * 4 -

The final result after processing all symbols is 46.