Return to Question

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time?

• GetElement(k): Return the $k$th element of the list.

• InsertAfter(x,y): Insert the new element y into the list immediately after x.

• Delete(x): Remove x from the list.

For the last two operations, you can assume that x is given as a pointer directly into the data structure; InsertElement returns the corresponding pointer for y. InsertAfter(NULL, y) inserts y at the beginning of the list.

For example, starting with an empty data structure, the following operations update the ordered list as shown below:

• InsertAfter(NULL, a) $\implies$ [a]
• InsertAfter(NULL, b) $\implies$ [b, a]
• InsertAfter(b, c) $\implies$ [b, c, a]
• InsertAfter(a, d) $\implies$ [b, c, a, d]
• Delete(c) $\implies$ [b, a, d]

After these five updates, GetElement(2) should return d, and GetElement(3) should throw an exception.

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time?

• GetElement(k): Return the $k$th element of the list.

• InsertAfter(x,y): Insert the new element y into the list immediately after x.

• Delete(x): Remove x from the list.

For the last two operations, you can assume that x is given as a pointer directly into the data structure; InsertElement returns the corresponding pointer for y. InsertAfter(NULL, y) inserts y at the beginning of the list.

For example, starting with an empty data structure, the following operations update the ordered list as shown below:

• InsertAfter(NULL, a) $\implies$ [a]
• InsertAfter(NULL, b) $\implies$ [b, a]
• InsertAfter(b, c) $\implies$ [b, c, a]
• InsertAfter(a, d) $\implies$ [b, c, a, d]
• Delete(c) $\implies$ [b, a, d]

After these five updates, GetElement(2) should return d, and GetElement(3) should return an error.

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time?

• GetElement(k): Return the $k$th element of the list.

• InsertAfter(x,y): Insert the new element y into the list immediately after x.

• Delete(x): Remove x from the list.

For the last two operations, you can assume that x is given as a pointer directly into the data structure; InsertElement returns the corresponding pointer for y. InsertAfter(NULL, y) inserts y at the beginning of the list.

For example, starting with an empty data structure, the following operations update the ordered list as shown below:

• InsertAfter(NULL, a) $\implies$ [a]
• InsertAfter(NULL, b) $\implies$ [b, a]
• InsertAfter(b, c) $\implies$ [b, c, a]
• InsertAfter(a, d) $\implies$ [b, c, a, d]
• Delete(c) $\implies$ [b, a, d]

After these five updates, GetElement(3) should return d, and GetElement(4) should return an error.

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time?

• GetElement(k): Return the $k$th element of the list.

• InsertAfter(x,y): Insert the new element y into the list immediately after x.

• Delete(x): Remove x from the list.

For the last two operations, you can assume that x is given as a pointer directly into the data structure; InsertElement returns the corresponding pointer for y. InsertAfter(NULL, y) inserts y at the beginning of the list.

For example, starting with an empty data structure, the following operations update the ordered list as shown below:

• InsertAfter(NULL, a) $\implies$ [a]
• InsertAfter(NULL, b) $\implies$ [b, a]
• InsertAfter(b, c) $\implies$ [b, c, a]
• InsertAfter(a, d) $\implies$ [b, c, a, d]
• Delete(c) $\implies$ [b, a, d]

After these five updates, GetElement(2) should return d, and GetElement(3) should throw an exception.

Is there a data structure with

• $O(1)$ amortised time access to the $k$-th element and
• $O(1)$ amortised time insertion and deletion at—or next to—a known position?

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time?

• GetElement(k): Return the $k$th element of the list.

• InsertAfter(x,y): Insert the new element y into the list immediately after x.

• Delete(x): Remove x from the list.

For the last two operations, you can assume that x is given as a pointer directly into the data structure; InsertElement returns the corresponding pointer for y. InsertAfter(NULL, y) inserts y at the beginning of the list.

For example, starting with an empty data structure, the following operations update the ordered list as shown below:

• InsertAfter(NULL, a) $\implies$ [a]
• InsertAfter(NULL, b) $\implies$ [b, a]
• InsertAfter(b, c) $\implies$ [b, c, a]
• InsertAfter(a, d) $\implies$ [b, c, a, d]
• Delete(c) $\implies$ [b, a, d]

After these five updates, GetElement(3) should return d, and GetElement(4) should return an error.