Skip to main content

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 problem

Let LL be the doubly linked list with values [10,20,30,40,50][10, 20, 30, 40, 50], and let II 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 II and leaves II at the same element as before; DELETE-AT(I) invalidates II and no other iterator, and returns an iterator to the former successor (or past-the-end if II 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

Hint

INSERT-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

Back to Data Structures

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.