License: Lesser GPL. Contact me at qwertie256, at, gmail.com if you would like the source code. Here's an example usage:
VList<int> oneTwo = new VList<int>(1, 2);
VList<int> threeFour = new VList<int>(3, 4);
VList<int> list = oneTwo;
VList<int> list2 = threeFour;
ExpectList(list, 1, 2);
ExpectList(list, 1, 3, 4, 2);
ExpectList(list2, 3, 4, 1, 2);
// oneTwo and ThreeFour are unchanged:
ExpectList(oneTwo, 1, 2);
ExpectList(threeFour, 3, 4);
static void ExpectList<T>(IList<T> list, params T expected)
for (int i = 0; i < expected.Length; i++)
I thought that I would use the RVList to implement Loyc's AST to help make it possible to take AST snapshots easily, but I now suspect it's not a good idea. I am still working on the problem.
Performance characteristicsSimilarly to a persistent linked list,
- Adding an item to the front of a VList or the end of an RVList is always O(1) in time, and often O(1) in space (though, unlike a linked list, it may be much more)
- Removing an item from the front of a VList or the end of an RVList is O(1) in time, although space not necessarily reclaimed.
- Adding or removing an item at the end of a VList or the front of an RVList is O(N) and requires making a copy of the entire list.
- Inserting or removing a list of M items at the end of a VList or the front of an RVList is O(N + M).
- Changing an item at an arbitrary position should be avoided, as it performs as poorly as inserting or removing an item at that position.
- Access by index averages O(1) in ideal conditions
- Getting the list length is typically O(log N), but O(1) in my version
- If a sublist points somewhere within a larger list, its index within the larger list can be obtained in between O(1) and O(log N) time. Consequently, reverse enumeration is possible without creating a temporary stack or list.