CircularListT Class

[SerializableAttribute]
public class CircularList<T> : ISupportsRangeList<T>, 
	ISupportsRangeCollection<T>, ICollection<T>, IEnumerable<T>, IEnumerable, IReadOnlyCollection<T>, 
	IList<T>, IReadOnlyList<T>, IList, ICollection

<SerializableAttribute>
Public Class CircularList(Of T)
	Implements ISupportsRangeList(Of T), ISupportsRangeCollection(Of T), 
	ICollection(Of T), IEnumerable(Of T), IEnumerable, IReadOnlyCollection(Of T), 
	IList(Of T), IReadOnlyList(Of T), IList, ICollection

[SerializableAttribute]
generic<typename T>
public ref class CircularList : ISupportsRangeList<T>, 
	ISupportsRangeCollection<T>, ICollection<T>, IEnumerable<T>, IEnumerable, IReadOnlyCollection<T>, 
	IList<T>, IReadOnlyList<T>, IList, ICollection

[<SerializableAttribute>]
type CircularList<'T> = 
    class
        interface ISupportsRangeList<'T>
        interface ISupportsRangeCollection<'T>
        interface ICollection<'T>
        interface IEnumerable<'T>
        interface IEnumerable
        interface IReadOnlyCollection<'T>
        interface IList<'T>
        interface IReadOnlyList<'T>
        interface IList
        interface ICollection
    end

Inheritance

Object    CircularListT

Implements

ISupportsRangeCollectionT, ISupportsRangeListT, ICollectionT, IEnumerableT, IListT, IReadOnlyCollectionT, IReadOnlyListT, ICollection, IEnumerable, IList

Type Parameters

T

The type of elements in the list.

Circularity means a dynamic start/end position in the internal store. If inserting/removing elements is required typically at the first/last position, then using CircularListT could be a good choice because these operations have an O(1) cost. Inserting/removing at other positions have generally O(n) cost, though these operations are optimized for not moving more than n/2 elements.

CircularListT is fully compatible with ListT as it implements all the public members of ListT.

CircularListT can be a good option instead of LinkedListT, too. Generally LinkedListT is considered to be a good choice when elements should be inserted/removed at the middle of the list. However, unless a direct reference is kept to a LinkedListNodeT to be removed or before/after which the new element has to be inserted, then the insert/remove operation will be very slow in LinkedListT, as it has no indexed access, and the node has to be located by iterating the elements. Therefore, in most cases CircularListT outperforms LinkedListT in most practical cases.

Adding elements to the first/last position are generally O(1) operations. If the capacity needs to be increased to accommodate the new element, adding becomes an O(n) operation, where n is Count. Though when elements are continuously added to the list, the amortized cost of adding methods (Add, AddLast, AddFirst or Insert at the first/last position) is O(1) due to the low frequency of increasing capacity. For example, when 20 million items are added to a CircularListT that was created by the default constructor, capacity is increased only 23 times.

Inserting more elements are also optimized. If the length of the CircularListT is n and the length of the collection to insert is m, then the cost of InsertRange to the first or last position is O(m). When the collection is inserted in the middle of the CircularListT, the cost is O(Max(n, m)), and in practice no more than n/2 elements are moved in the CircularListT. In contrast, inserting a collection into the first position of a ListT moves all the already existing elements. And if the collection to insert does not implement ICollectionT, then ListT works with an O(n * m) cost as it will insert the elements one by one, shifting the elements by 1 in every iteration.

CircularListT provides an O(1) solution also for emptying the collection: the Reset method clears all elements and resets the internal capacity to 0 in one quick step. The effect is the same as calling the Clear and TrimExcess methods in a row but the latter solution has an O(n) cost.

When a list is populated only by the Add method or by the indexer, and then it is never modified, ListT class can have a slightly better performance. Though when the list is enumerated as an IEnumerableT implementation (occurs for example, when the list is used in LINQ queries or when used as an IListT instance), then CircularListT can be a better choice than ListT because the enumerator of ListT class has worse performance when it is boxed into an IEnumeratorT reference. While the GetEnumerator method of CircularListT returns a value type enumerator (similarly to the ListT class), when the enumerator is obtained via the IEnumerableT interface, the CircularListT returns a reference type to avoid boxing and to provide a better performance.

Reference