Data Structures · Arrays, linked structures, stacks, queues, and amortization
Let L be the doubly linked list with values [10, 20, 30, 40, 50], and let I be a…
Problem
Data Structures practice problemLet be the doubly linked list with values , and let be a bidirectional iterator currently at 30 (so DEREF(I) = 30). Iterators support ADVANCE (forward one), RETREAT (backward one), DEREF, and the list supports INSERT-BEFORE(I, x) and DELETE-AT(I). Adopt the following validity rules: INSERT-BEFORE does not invalidate and leaves at the same element as before; DELETE-AT(I) invalidates and no other iterator, and returns an iterator to the former successor (or past-the-end if was last).
Trace the following program. After each numbered line, write the list contents and the value of DEREF at each currently valid iterator named below, or write “invalid” or “past-the-end”.
```
I ← iterator at 30
J ← BEGIN(L) // at 10
K ← END(L) // past-the-end
1 INSERT-BEFORE(I, 25)
2 ADVANCE(I)
3 DELETE-AT(J)
4 RETREAT(I)
5 INSERT-BEFORE(K, 60)
6 M ← DELETE-AT(I)
7 ADVANCE(M)
```
Hint
HintINSERT-BEFORE never invalidates its argument iterator; DELETE-AT invalidates only its argument and hands back the successor.
Check your work
Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.
The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Data Structures sample problem: Try the free sample problem.
More Data Structures practice problems
- Let V be a dynamic array of n elements stored in a buffer of capacity c, with the…Abstract data types, representation, and invariants
- A ring buffer (circular array) of fixed capacity C ≥ 1 stores a sequence of at most C…Abstract data types, representation, and invariants
- Consider BST deletion of a node zSearch trees and balanced trees
- Let T be a BST whose nodes contain only key, left, and right fields (no parent…Search trees and balanced trees
- Consider a hash table T of size m = 11 that resolves collisions by chainingHash tables and probabilistic performance
- Throw n balls independently and uniformly into n binsHash tables and probabilistic performance
- `Bubble-Down`(A,i,n) is specified as follows on a 1-based array that is a complete…Heaps, priority queues, and disjoint sets
- The fat-node method of partial persistence stores, in each field of each node, a…Graph representations and traversals
- A duplicate minimum must sit on the min-stack, or one pop forgets the otherArrays, linked structures, stacks, queues, and amortization