Jawaharlal Nehru Technological University Hyderabad B.Tech II DATA STRUCTURES Previous Question Paper (September - 2021 - R13)

A Doubly-Linked List (DLL) is a linear data structure where each node contains three fields: data, a pointer to the next node, and a pointer to the previous node. This bidirectional linking allows for traversal in both forward and backward directions, unlike a singly-linked list.

The primary operations performed on a DLL include insertion, deletion, and traversal. Below are the Java-style methods for these operations:

1. Insertion at Beginning: Create a new node, set its next pointer to the current head, set the head's previous pointer to the new node, and update the head to the new node.
2. Insertion at End: Traverse to the last node, set its next pointer to the new node, and set the new node's previous pointer to the last node.
3. Deletion: To delete a node, update the next pointer of the preceding node to point to the successor of the target node, and update the previous pointer of the successor node to point to the predecessor of the target node.
4. Traversal: Start from the head and follow the next pointers until null to print forward, or start from the tail and follow previous pointers to print backward.

The main advantage of a DLL is the ability to delete a node in O(1) time if the pointer to the node is given, as the previous node is directly accessible. However, it requires extra memory for the additional pointer in each node.

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, where insertion and deletion occur at the same end, known as the top. Using an array, the stack is implemented by maintaining an integer variable top initialized to -1.

The primary operations are:

• Push: Adds an element to the top. It first checks if the stack is full (overflow condition: top == MAX-1). If not, it increments top and inserts the element.
• Pop: Removes the top element. It checks if the stack is empty (underflow condition: top == -1). If not, it retrieves the element and decrements top.
• Peek/Top: Returns the value at the top without modifying the stack.

In the context of recursive procedures, the system uses a Call Stack to manage function calls. When a function is called, the system pushes a new Activation Record (or stack frame) onto the stack. This frame contains:

1. Local variables of the function.
2. Parameters passed to the function.
3. The return address, which tells the processor where to resume execution after the function finishes.

As a recursive function calls itself, each call creates a new frame on top of the previous ones. Once the base case is reached, the function begins to return, and the system pops the top frame from the stack, restoring the local environment of the previous caller. This mechanism ensures that each recursive instance maintains its own independent state, allowing the program to backtrack correctly through the sequence of calls until the initial invocation completes.