http://erikdemaine.org/papers/ResizableArraysTR/
Implement the variant that can grow/shrink on both ends. The extra space is O(√n) at any point in time. Access by index is still O(1).
Comparison to standard libraries:
There is no real alternative.
System.Collections.Generic.List<T> can't grow/shrink on the front in O(1)
System.Collections.Generic.LinkedList<T> can be changed from both ends in O(1), but does not support indexed access and wastes O(n) space
System.Collections.Generic.SortedDictionary<int, T> has O(log(n)) indexed access and wastes O(n) space
http://erikdemaine.org/papers/ResizableArraysTR/
Implement the variant that can grow/shrink on both ends. The extra space is O(√n) at any point in time. Access by index is still O(1).
Comparison to standard libraries:
There is no real alternative.
System.Collections.Generic.List<T>can't grow/shrink on the front in O(1)System.Collections.Generic.LinkedList<T>can be changed from both ends in O(1), but does not support indexed access and wastes O(n) spaceSystem.Collections.Generic.SortedDictionary<int, T>has O(log(n)) indexed access and wastes O(n) space