Tables 1 and 2 are a summary of the performance of data structures in the study that implement each of the interfaces; List, USet, and SSet as described in the Interfaces section. Fig.1. shows the dependencies between the various sections of analysis. As can be seen, a dashed arrow is indicative of a weak dependency, where only a small part of the section depends on the previous section (or the main results of the previous section).

Table 1: A summary of List and USet implementations.

List implementations
	get(i)/set(i,x)	add(i,x)/remove()
ArrayStack	O(1)	O(1+n-i)A
ArrayDeque	O(1)	O(1+min{i,n-i})A
DualArrayDeque	O(1)	O(1+min{i,n-i})A
RootishArrayStack	O(1)	O(1+n-i)A
DoublyLinkedList	O(1+min{i,n-i})	O(1+min{i,n-i})
SpaceEfficientLinkedList	O(1+min{i,n-i}/b)	O(b+min{i,n-i}/b)A
SkiplistList	O(logn)E	O(logn)E

USet implementation	find(x)	add(x)/remove(x)
ChainedHashTable	O(1)E	O(1)A,E
LinearHashTable	O(1)E	O(1)A,E

^A denotes an amortized running time.

^E denotes an expected running time.