Chapter 15 Exercises: Dynamic Data Structures: Linked Lists, Stacks, and Queues

Chapter 15 Exercises: Dynamic Data Structures: Linked Lists, Stacks, and Queues

Part A: Recall & Terminology

Exercise A1. Define the following terms in your own words: (a) linked list, (b) head pointer, (c) tail pointer, (d) LIFO, (e) FIFO.

Exercise A2. What is the difference between a singly-linked list and a doubly-linked list? What extra cost does the doubly-linked version incur per node?

Exercise A3. Why must the Head parameter be passed as var in InsertAtHead? What would happen if it were passed by value?

Exercise A4. Explain why you cannot perform binary search on a linked list, even if the list is sorted.

Exercise A5. What is a dangling pointer? Give an example of how one arises in code that manipulates a linked list.

Exercise A6. In a queue implementation using a linked list with Front and Rear pointers, why must we set Rear := nil when dequeuing the last element?

Exercise A7. Name three real-world applications of stacks and three real-world applications of queues.

Part B: Tracing & Prediction

Exercise B1. Trace the following code and draw the linked list after each operation. Show the final state of the list and the value of Count.

var Head: PNode;
begin
  Head := nil;
  InsertAtHead(Head, 30);
  InsertAtHead(Head, 20);
  InsertAtHead(Head, 10);
  InsertAtTail(Head, 40);
  DeleteNode(Head, 20);
  InsertAtHead(Head, 5);
end;

Exercise B2. Trace the following stack operations. After each operation, write the contents of the stack (top to bottom) and the return value (if any).

Push(10)
Push(20)
Push(30)
Pop         -> ?
Peek        -> ?
Push(40)
Pop         -> ?
Pop         -> ?
IsEmpty     -> ?
Pop         -> ?
IsEmpty     -> ?

Exercise B3. Trace the following queue operations. After each operation, write the contents of the queue (front to rear) and the return value (if any).

Enqueue(A)
Enqueue(B)
Dequeue     -> ?
Enqueue(C)
Enqueue(D)
Dequeue     -> ?
Front       -> ?
Dequeue     -> ?
Dequeue     -> ?
IsEmpty     -> ?

Exercise B4. The following code contains a memory leak. Identify the line where the leak occurs and explain how to fix it.

procedure RemoveHead(var Head: PNode);
begin
  if Head <> nil then
    Head := Head^.Next;
end;

Exercise B5. What does the following function return? Trace it with the list 10 -> 20 -> 30 -> 40 -> nil.

function Mystery(Head: PNode): Integer;
var
  Current: PNode;
  Result: Integer;
begin
  Result := 0;
  Current := Head;
  while Current <> nil do
  begin
    if Current^.Data > Result then
      Result := Current^.Data;
    Current := Current^.Next;
  end;
  Mystery := Result;
end;

Part C: Code Completion & Short Programs

Exercise C1. Write a function SumList(Head: PNode): Integer that returns the sum of all values in a singly-linked list.

Exercise C2. Write a procedure InsertSorted(var Head: PNode; Value: Integer) that inserts a new node into a singly-linked list that is already sorted in ascending order, maintaining the sorted order.

Exercise C3. Write a function ListLength(Head: PNode): Integer that returns the number of nodes in a singly-linked list. Then write a recursive version ListLengthRec.

Exercise C4. Write a procedure ReverseList(var Head: PNode) that reverses a singly-linked list in place (without allocating any new nodes).

Hint: Use three pointers — Previous, Current, and NextNode — and rewire the links one at a time.

Exercise C5. Write a function NthFromEnd(Head: PNode; N: Integer): PNode that returns a pointer to the Nth node from the end of a singly-linked list. For example, if the list is 10 -> 20 -> 30 -> 40 and N = 2, return the node containing 30.

Hint: Use two pointers, separated by N nodes.

Exercise C6. Write a complete program that uses a stack to check whether a string is a palindrome (reads the same forwards and backwards). Push each character, then pop and compare with the original string.

Exercise C7. Write a procedure Interleave(var Q1, Q2: TQueue) that merges two queues by alternating elements. If Q1 contains [1, 3, 5] and Q2 contains [2, 4, 6], Q1 should end up containing [1, 2, 3, 4, 5, 6] and Q2 should be empty.

Exercise C8. Using only stack operations (push, pop, peek, isEmpty), write a procedure SortStack(var S: TStack) that sorts a stack so that the smallest element is on top. You may use one additional temporary stack.

Exercise C9. Write a function HasCycle(Head: PNode): Boolean that detects whether a singly-linked list contains a cycle (i.e., some node's Next pointer points back to an earlier node).

Hint: Use Floyd's cycle detection algorithm — two pointers, one moving one step at a time and the other moving two steps. If they ever meet, there is a cycle.

Exercise C10. Write a TStringStack — a stack that stores strings instead of integers. Implement Push, Pop, Peek, and IsEmpty. Use it to reverse the words in a sentence.

Part D: Analysis & Design

Exercise D1. A music player needs to manage a playlist where the user can: - Add songs to the end of the playlist - Skip to the next song - Go back to the previous song - Remove the current song

Which data structure would you choose? Justify your answer by analyzing the time complexity of each operation under your chosen structure.

Exercise D2. A web browser's back/forward navigation can be modeled with two stacks. Describe how you would implement this. What goes on each stack? What happens when the user clicks "Back"? "Forward"? Types a new URL?

Exercise D3. Compare the memory usage of an array of 1000 integers versus a singly-linked list of 1000 integers, assuming Integer is 4 bytes and a pointer is 8 bytes.

Array: ? bytes total
Linked list: ? bytes total (data + pointers + allocation overhead)

What is the percentage overhead of the linked list?

Exercise D4. You need to implement a "recently used files" list for a text editor. The list should: - Show the 10 most recently opened files - When a file is opened, move it to the front (if already in the list) or add it to the front (if not) - If the list exceeds 10 items, remove the oldest

Design this using a linked list. Specify the type declarations and outline each operation. What is the time complexity of each?

Exercise D5. A hospital emergency room uses a priority queue where patients with more severe conditions are seen first, regardless of arrival time. A regular FIFO queue is not appropriate. Describe how you would modify the linked list queue to support priorities. What is the time complexity of enqueue and dequeue in your design?

Part E: Challenge Problems

Exercise E1: Merge Two Sorted Lists. Write a function MergeSorted(A, B: PNode): PNode that takes two sorted singly-linked lists and merges them into a single sorted list. Do not allocate any new nodes — rewire the existing nodes' Next pointers. This is the merge step of merge sort applied to linked lists.

Exercise E2: LRU Cache. Implement a Least Recently Used (LRU) cache using a doubly-linked list and an array acting as a hash table. The cache should store key-value pairs (Integer keys, string values) and support: - Get(Key) — returns the value, or empty string if not found. Moves the accessed item to the front. - Put(Key, Value) — inserts or updates. If the cache is full (capacity N), evict the least recently used item (at the tail).

Both operations should be O(N) in the worst case (due to the array-based hash table), but aim for O(1) amortized.

Exercise E3: Queue Using Two Stacks. Implement a queue using only two stacks (no linked list operations, only push/pop/isEmpty). When should elements be transferred from one stack to the other? What is the amortized time complexity of enqueue and dequeue?

Exercise E4: Expression Parser. Extend the expression evaluator from Case Study 1 to handle: - Parentheses: (3 + 4) * 2 - Unary minus: -5 + 3 - Exponentiation: 2 ^ 3 (right-associative) - Variables: x + y * 2 (prompt the user for values)

Exercise E5: Polynomial Arithmetic. Represent a polynomial as a sorted linked list of terms, where each node contains a coefficient and an exponent. Implement: - AddPoly(A, B: PNode): PNode — adds two polynomials - MultiplyPoly(A, B: PNode): PNode — multiplies two polynomials - PrintPoly(Head: PNode) — displays the polynomial in standard form (e.g., 3x^2 + 2x - 1)

Part M: Mastery

Exercise M1: Text Editor Buffer. Implement a simple text editor buffer using a doubly-linked list of lines. Support the following commands:

I <text> — Insert a line after the current line
D — Delete the current line
U / D — Move the cursor up/down one line
P — Print all lines with the current line marked
Z — Undo the last operation (use a stack)

The editor should handle an arbitrary number of lines and support multi-level undo. Write a complete, compilable program.

Exercise M2: Josephus Problem. N soldiers stand in a circle. Starting from soldier 1, every Kth soldier is eliminated until one remains. Implement this using a circular linked list. Your program should: - Accept N and K as input - Print the order of elimination - Print the survivor's original position - Test with the classic case: N=41, K=3 (the original Josephus problem)

Exercise M3: PennyWise Enhancement. Extend the PennyWise project checkpoint to support: - Redo stack: After undoing, the user can redo. Redo is cleared whenever a new expense is added. - Sorted insertion: Expenses are kept sorted by date (most recent first). If two expenses have the same date, sort by amount (largest first). - Category filter: The user can view expenses for a single category, displayed as a linked list traversal. - Save/Load: Persist the expense list to a typed file and reload it on startup. The undo/redo stacks are not saved.