CircularListT Class

Implements an IListT where inserting/removing at the beginning/end position are O(1) operations. CircularListT is fully compatible with ListT but has a better performance in several cases.

Definition

Namespace: KGySoft.Collections
Assembly: KGySoft.CoreLibraries (in KGySoft.CoreLibraries.dll) Version: 8.2.0
C#
[SerializableAttribute]
public class CircularList<T> : ISupportsRangeList<T>, 
	ISupportsRangeCollection<T>, ICollection<T>, IEnumerable<T>, IEnumerable, IReadOnlyCollection<T>, 
	IList<T>, IReadOnlyList<T>, IList, ICollection
Inheritance
Object    CircularListT
Implements
ISupportsRangeCollectionT, ISupportsRangeListT, ICollectionT, IEnumerableT, IListT, IReadOnlyCollectionT, IReadOnlyListT, ICollection, IEnumerable, IList

Type Parameters

T
The type of elements in the list.

Remarks

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 of 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 of 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.

Constructors

CircularListT Creates a new instance of CircularListT.
CircularListT(IEnumerableT) Creates a new instance of CircularListT with the elements of provided collection.
CircularListT(Int32) Creates a new instance of CircularListT that is empty and has the specified initial capacity.

Properties

Capacity Gets or sets the actual size of the internal storage of held elements.
Count Gets the number of elements contained in the list.
Item Gets or sets the element at the specified index.

Methods

Add Adds an item to the end of the CircularListT.
AddFirst Adds an item to the beginning of the CircularListT.
AddLast Adds an item to the end of the CircularListT.
AddRange Adds a collection to the end of the CircularListT.
AsReadOnly Returns a read-only IListT wrapper for the current collection.
BinarySearch(T) Searches the entire sorted list for an element using the default comparer and returns the zero-based index of the element.
BinarySearch(T, IComparerT) Searches the entire sorted CircularListT for an element using the specified comparer and returns the zero-based index of the element.
BinarySearch(Int32, Int32, T, IComparerT) Searches a range of elements in the sorted CircularListT for an element using the specified comparer and returns the zero-based index of the element.
Clear Removes all items from the CircularListT.
Contains Determines whether the list contains the specific item.
ConvertAllTOutput Converts the elements in the current list to another type, and returns a CircularListT containing the converted elements.
CopyTo(T, Int32) Copies the entire CircularListT to a compatible one-dimensional array, starting at a particular array index.
CopyTo(Int32, T, Int32, Int32) Copies a range of elements from the CircularListT to a compatible one-dimensional array, starting at the specified index of the target array.
EnsureCapacity Ensures that the Capacity of the CircularListT is at least the specified capacity.
Exists Determines whether the CircularListT contains elements that match the conditions defined by the specified predicate.
Find Searches for an element that matches the conditions defined by the specified predicate, and returns the first occurrence within the CircularListT.
FindAll Retrieves all the elements that match the conditions defined by the specified predicate.
FindIndex(PredicateT) Searches for an element that matches the conditions defined by the specified predicate, and returns the zero-based index of the first occurrence within the CircularListT.
FindIndex(Int32, PredicateT) Searches for an element that matches the conditions defined by the specified predicate, and returns the zero-based index of the first occurrence within the range of elements in the CircularListT that extends from the specified index to the last element.
FindIndex(Int32, Int32, PredicateT) Searches for an element that matches the conditions defined by the specified predicate, and returns the zero-based index of the first occurrence within the range of elements in the CircularListT that starts at the specified index and contains the specified number of elements.
FindLast Searches for an element that matches the conditions defined by the specified predicate, and returns the last occurrence within the CircularListT.
FindLastIndex(PredicateT) Searches for an element that matches the conditions defined by the specified predicate, and returns the zero-based index of the last occurrence within the CircularListT.
FindLastIndex(Int32, PredicateT) Searches for an element that matches the conditions defined by the specified predicate, and returns the zero-based index of the last occurrence within the range of elements in the CircularListT that extends from the first element to the specified index.
FindLastIndex(Int32, Int32, PredicateT) Searches for an element that matches the conditions defined by the specified predicate, and returns the zero-based index of the last occurrence within the range of elements in the CircularListT that contains the specified number of elements and ends at the specified index.
ForEach Performs the specified action on each element of the CircularListT.
GetEnumerator Returns an enumerator that iterates through the CircularListT.
GetRange Creates a shallow copy of a range of elements in the source CircularListT.
IndexOf(T) Determines the index of a specific item in the CircularListT.
IndexOf(T, Int32) Searches for the specified object and returns the zero-based index of the first occurrence within the range of elements in the CircularListT that extends from the specified index to the last element.
IndexOf(T, Int32, Int32) Searches for the specified object and returns the zero-based index of the first occurrence within the range of elements in the CircularListT that starts at the specified index and contains the specified number of elements.
Insert Inserts an item to the CircularListT at the specified index.
InsertRange Inserts a collection into the CircularListT at the specified index.
LastIndexOf(T) Determines the index of the last occurrence of a specific item in the CircularListT.
LastIndexOf(T, Int32) Searches for the specified object and returns the zero-based index of the last occurrence within the range of elements in the CircularListT that extends from the first element to the specified index.
LastIndexOf(T, Int32, Int32) Searches for the specified object and returns the zero-based index of the last occurrence within the range of elements in the CircularListT that contains the specified number of elements and ends at the specified index.
Remove Removes the first occurrence of the specific item from the CircularListT.
RemoveAll Removes all the elements from the CircularListT that match the conditions defined by the specified predicate.
RemoveAt Removes the item from the CircularListT at the specified index.
RemoveFirst Removes the first element of the see CircularListT.
RemoveLast Removes the last element from the CircularListT.
RemoveRange Removes count amount of items from the CircularListT at the specified index.
ReplaceRange Removes count amount of items from the CircularListT at the specified index and inserts the specified collection at the same position. The number of elements in collection can be different from the amount of removed items.
Reset Removes all items from the list and resets the Capacity of the list to 0.
Reverse Reverses the order of the elements in the entire CircularListT.
Reverse(Int32, Int32) Reverses the order of the elements in the specified range.
Sort Sorts the elements in the entire CircularListT using the default comparer.
Sort(ComparisonT) Sorts the elements in the entire CircularListT using the specified ComparisonT.
Sort(IComparerT) Sorts the elements in the entire CircularListT using the specified comparer.
Sort(Int32, Int32, IComparerT) Sorts the elements in a range of elements in CircularListT using the specified comparer.
ToArray Copies the elements of the list to a new array.
TrimExcess Sets the capacity to the actual number of elements in the list, if that number (Count) is less than the 90 percent of Capacity.
TrueForAll Determines whether every element in the CircularListT matches the conditions defined by the specified predicate.

Extension Methods

AddRangeT Adds a collection to the target ICollectionT.
(Defined by CollectionExtensions)
AsThreadSafeT Returns a LockingCollectionT, which provides a thread-safe wrapper for the specified collection. This only means that if the members are accessed through the returned LockingCollectionT, then the inner state of the wrapped collection remains always consistent and not that all of the multi-threading concerns can be ignored.
See the Remarks section of the LockingCollectionT class for details and some examples.
(Defined by CollectionExtensions)
AsThreadSafeT Returns a LockingListT, which provides a thread-safe wrapper for the specified list. This only means that if the members are accessed through the returned LockingListT, then the inner state of the wrapped list remains always consistent and not that all of the multi-threading concerns can be ignored.
See the Remarks section of the LockingListT class for details and some examples.
(Defined by ListExtensions)
Convert Converts an Object specified in the obj parameter to the desired targetType.
See the Examples section of the generic ConvertTTarget(Object, CultureInfo) overload for an example.
(Defined by ObjectExtensions)
ConvertTTarget Converts an Object specified in the obj parameter to the desired TTarget.
(Defined by ObjectExtensions)
ForEachT Similarly to the List<T>.ForEach method, processes an action on each element of an enumerable collection.
(Defined by EnumerableExtensions)
GetRandomElementT Gets a random element from the enumerable source using a new FastRandom instance.
(Defined by EnumerableExtensions)
GetRandomElementT Gets a random element from the enumerable source using a specified Random instance.
(Defined by EnumerableExtensions)
In Gets whether item is among the elements of set.
See the Examples section of the generic InT(T, T) overload for an example.
(Defined by ObjectExtensions)
IndexOf Searches for an element in the source enumeration where the specified predicate returns .
(Defined by EnumerableExtensions)
IndexOf Searches for an element in the source enumeration.
(Defined by EnumerableExtensions)
IndexOfT Searches for an element in the source enumeration.
(Defined by EnumerableExtensions)
IndexOfT Searches for an element in the source enumeration where the specified predicate returns .
(Defined by EnumerableExtensions)
InsertRangeT Inserts a collection into the target IListT.
(Defined by ListExtensions)
IsNullOrEmpty Determines whether the specified source is or empty (has no elements).
(Defined by EnumerableExtensions)
IsNullOrEmptyT Determines whether the specified source is or empty (has no elements).
(Defined by EnumerableExtensions)
JoinT Concatenates the items of the source collection into a new string instance using the specified separator between the items.
(Defined by EnumerableExtensions)
JoinT Concatenates the items of the source collection into a new string instance using the specified separator between the items.
(Defined by EnumerableExtensions)
RemoveRangeT Removes count amount of items from the specified collection at the specified index.
(Defined by ListExtensions)
ReplaceRangeT Removes count amount of items from the target IListT at the specified index, and inserts the specified collection at the same position. The number of elements in collection can be different from the amount of removed items.
(Defined by ListExtensions)
ShuffleT Shuffles an enumerable source (randomizes its elements) using a new FastRandom instance.
(Defined by EnumerableExtensions)
ShuffleT Shuffles an enumerable source (randomizes its elements) using the provided seed with a new FastRandom instance.
(Defined by EnumerableExtensions)
ShuffleT Shuffles an enumerable source (randomizes its elements) using the provided seed with a new FastRandom instance.
(Defined by EnumerableExtensions)
ShuffleT Shuffles an enumerable source (randomizes its elements) using a specified Random instance.
(Defined by EnumerableExtensions)
ToCircularListT Creates a CircularListT from an IEnumerableT.
(Defined by EnumerableExtensions)
ToStringKeyedDictionaryT Creates a StringKeyedDictionaryTValue from an IEnumerableT instance using the specified keySelector delegate and a comparer.
(Defined by EnumerableExtensions)
ToStringKeyedDictionaryT, TValue Creates a StringKeyedDictionaryTValue from an IEnumerableT instance using the specified key and value selector delegates and a comparer.
(Defined by EnumerableExtensions)
TryAdd Tries to add the specified item to the collection.
(Defined by EnumerableExtensions)
TryAddT Tries to add the specified item to the collection.
(Defined by EnumerableExtensions)
TryAddRange Tries to add the specified collection to the target collection.
(Defined by EnumerableExtensions)
TryAddRangeT Tries to add the specified collection to the target collection.
(Defined by EnumerableExtensions)
TryClear Tries to remove all elements from the collection.
(Defined by EnumerableExtensions)
TryClearT Tries to remove all elements from the collection.
(Defined by EnumerableExtensions)
TryConvert Tries to convert an Object specified in the obj parameter to the desired targetType.
See the Examples section of the ConvertTTarget(Object, CultureInfo) method for a related example.
(Defined by ObjectExtensions)
TryConvert Tries to convert an Object specified in the obj parameter to the desired targetType.
See the Examples section of the ConvertTTarget(Object, CultureInfo) method for a related example.
(Defined by ObjectExtensions)
TryConvertTTarget Tries to convert an Object specified in the obj parameter to the desired TTarget.
See the Examples section of the ConvertTTarget(Object, CultureInfo) method for a related example.
(Defined by ObjectExtensions)
TryConvertTTarget Tries to convert an Object specified in the obj parameter to the desired TTarget.
See the Examples section of the ConvertTTarget(Object, CultureInfo) method for a related example.
(Defined by ObjectExtensions)
TryGetCount Tries to get the number of elements in the source enumeration without enumerating it.
(Defined by EnumerableExtensions)
TryGetCountT Tries to get the number of elements in the source enumeration without enumerating it.
(Defined by EnumerableExtensions)
TryGetElementAt Tries to get an item at the specified index in the collection.
(Defined by EnumerableExtensions)
TryGetElementAtT Tries to get an item at the specified index in the collection.
(Defined by EnumerableExtensions)
TryInsert Tries to insert the specified item at the specified index to the collection.
(Defined by EnumerableExtensions)
TryInsertT Tries to insert the specified item at the specified index to the collection.
(Defined by EnumerableExtensions)
TryInsertRange Tries to insert the specified collection into the target collection.
(Defined by EnumerableExtensions)
TryInsertRangeT Tries to insert the specified collection into the target collection.
(Defined by EnumerableExtensions)
TryRemove Tries to remove the specified item from to the collection.
(Defined by EnumerableExtensions)
TryRemoveT Tries to remove the specified item from to the collection.
(Defined by EnumerableExtensions)
TryRemoveAt Tries to remove an item at the specified index from the collection.
(Defined by EnumerableExtensions)
TryRemoveAtT Tries to remove an item at the specified index from the collection.
(Defined by EnumerableExtensions)
TryRemoveRange Tries to remove count amount of items from the specified collection at the specified index.
(Defined by EnumerableExtensions)
TryRemoveRangeT Tries to remove count amount of items from the specified collection at the specified index.
(Defined by EnumerableExtensions)
TryReplaceRange Tries to remove count amount of items from the target at the specified index, and to insert the specified collection at the same position. The number of elements in collection can be different from the amount of removed items.
(Defined by EnumerableExtensions)
TryReplaceRangeT Tries to remove count amount of items from the target at the specified index, and to insert the specified collection at the same position. The number of elements in collection can be different from the amount of removed items.
(Defined by EnumerableExtensions)
TrySetElementAt Tries to set the specified item at the specified index in the collection.
(Defined by EnumerableExtensions)
TrySetElementAtT Tries to set the specified item at the specified index in the collection.
(Defined by EnumerableExtensions)

See Also