KGy SOFT

CircularListT Class

KGy SOFT Core Libraries Help
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.
See the Remarks section for details.
Inheritance Hierarchy

SystemObject
  KGySoft.CollectionsCircularListT

Namespace:  KGySoft.Collections
Assembly:  KGySoft.CoreLibraries (in KGySoft.CoreLibraries.dll) Version: 5.0.0-rc.1
Syntax

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

Type Parameters

T
The type of elements in the list.

The CircularListT type exposes the following members.

Constructors

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

  NameDescription
Public propertyCapacity
Gets or sets the actual size of the internal storage of held elements.
Public propertyCount
Gets the number of elements contained in the list.
Public propertyItem
Gets or sets the element at the specified index.
Top
Methods

  NameDescription
Public methodAdd
Adds an item to the end of the CircularListT.
Public methodAddFirst
Adds an item to the beginning of the CircularListT.
Public methodAddLast
Adds an item to the end of the CircularListT.
Public methodAddRange
Adds a collection to the end of the CircularListT.
Public methodAsReadOnly
Public methodBinarySearch(T)
Searches the entire sorted list for an element using the default comparer and returns the zero-based index of the element.
Public methodBinarySearch(T, IComparerT)
Searches the entire sorted CircularListT for an element using the specified comparer and returns the zero-based index of the element.
Public methodBinarySearch(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.
Public methodClear
Removes all items from the CircularListT.
Public methodContains
Determines whether the list contains the specific item.
Public methodConvertAllTOutput
Converts the elements in the current list to another type, and returns a CircularListT containing the converted elements.
Public methodCopyTo(T, Int32)
Copies the entire CircularListT to a compatible one-dimensional array, starting at a particular array index.
Public methodCopyTo(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.
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Public methodExists
Determines whether the CircularListT contains elements that match the conditions defined by the specified predicate.
Public methodFind
Searches for an element that matches the conditions defined by the specified predicate, and returns the first occurrence within the CircularListT.
Public methodFindAll
Retrieves all the elements that match the conditions defined by the specified predicate.
Public methodFindIndex(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.
Public methodFindIndex(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.
Public methodFindIndex(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.
Public methodFindLast
Searches for an element that matches the conditions defined by the specified predicate, and returns the last occurrence within the CircularListT.
Public methodFindLastIndex(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.
Public methodFindLastIndex(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.
Public methodFindLastIndex(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.
Public methodForEach
Performs the specified action on each element of the CircularListT.
Public methodGetEnumerator
Returns an enumerator that iterates through the CircularListT.
Public methodGetHashCode
Serves as the default hash function.
(Inherited from Object.)
Public methodGetRange
Creates a shallow copy of a range of elements in the source CircularListT.
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Public methodIndexOf(T)
Determines the index of a specific item in the CircularListT.
Public methodIndexOf(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.
Public methodIndexOf(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.
Public methodInsert
Inserts an item to the CircularListT at the specified index.
Public methodInsertRange
Inserts a collection into the CircularListT at the specified index.
Public methodLastIndexOf(T)
Determines the index of the last occurrence of a specific item in the CircularListT.
Public methodLastIndexOf(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.
Public methodLastIndexOf(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.
Public methodRemove
Removes the first occurrence of the specific item from the CircularListT.
Public methodRemoveAll
Removes all the elements from the CircularListT that match the conditions defined by the specified predicate.
Public methodRemoveAt
Removes the item from the see CircularListT at the specified index.
Public methodRemoveFirst
Removes the first element of the see CircularListT.
Public methodRemoveLast
Removes the last element from the CircularListT.
Public methodRemoveRange
Removes count amount of items from the CircularListT at the specified index.
Public methodReplaceRange
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.
Public methodReset
Removes all items from the list and resets the Capacity of the list to 0.
Public methodReverse
Reverses the order of the elements in the entire CircularListT.
Public methodReverse(Int32, Int32)
Reverses the order of the elements in the specified range.
Public methodSort
Sorts the elements in the entire CircularListT using the default comparer.
Public methodSort(IComparerT)
Sorts the elements in the entire CircularListT using the specified comparer.
Public methodSort(ComparisonT)
Sorts the elements in the entire CircularListT using the specified ComparisonT.
Public methodSort(Int32, Int32, IComparerT)
Sorts the elements in a range of elements in CircularListT using the specified comparer.
Public methodToArray
Copies the elements of the list to a new array.
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Public methodTrimExcess
Sets the capacity to the actual number of elements in the list, if that number (Count) is less than the 90 percent of Capacity.
Public methodTrueForAll
Determines whether every element in the CircularListT matches the conditions defined by the specified predicate.
Top
Extension Methods

  NameDescription
Public Extension MethodAddRangeT (Defined by CollectionExtensions.)
Public Extension MethodAsThreadSafeTOverloaded. (Defined by CollectionExtensions.)
Public Extension MethodAsThreadSafeTOverloaded. (Defined by ListExtensions.)
Public Extension MethodConvert(Type, CultureInfo)Overloaded.
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.)
Public Extension MethodCode exampleConvertTTarget(CultureInfo)Overloaded.
Converts an Object specified in the obj parameter to the desired TTarget.
(Defined by ObjectExtensions.)
Public Extension MethodForEachT
Similarly to the List<T>.ForEach method, processes an action on each element of an enumerable collection.
(Defined by EnumerableExtensions.)
Public Extension MethodGetRandomElementT(Boolean)Overloaded.
Gets a random element from the enumerable source using a new Random instance.
(Defined by EnumerableExtensions.)
Public Extension MethodGetRandomElementT(Random, Boolean)Overloaded.
Gets a random element from the enumerable source using a specified Random instance.
(Defined by EnumerableExtensions.)
Public Extension MethodIn (Defined by ObjectExtensions.)
Public Extension MethodIndexOf(FuncObject, Boolean)Overloaded.
Searches for an element in the source enumeration where the specified predicate returns .
(Defined by EnumerableExtensions.)
Public Extension MethodIndexOf(Object)Overloaded.
Searches for an element in the source enumeration.
(Defined by EnumerableExtensions.)
Public Extension MethodIndexOfT(FuncT, Boolean)Overloaded.
Searches for an element in the source enumeration where the specified predicate returns .
(Defined by EnumerableExtensions.)
Public Extension MethodIndexOfT(T)Overloaded.
Searches for an element in the source enumeration.
(Defined by EnumerableExtensions.)
Public Extension MethodInsertRangeT (Defined by ListExtensions.)
Public Extension MethodIsNullOrEmptyOverloaded.
Determines whether the specified source is  or empty (has no elements).
(Defined by EnumerableExtensions.)
Public Extension MethodIsNullOrEmptyTOverloaded.
Determines whether the specified source is  or empty (has no elements).
(Defined by EnumerableExtensions.)
Public Extension MethodRemoveRangeT
Removes count amount of items from the specified collection at the specified index.
(Defined by ListExtensions.)
Public Extension MethodReplaceRangeT
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.)
Public Extension MethodShuffleTOverloaded.
Shuffles an enumerable source (randomizes its elements) using a new Random instance.
(Defined by EnumerableExtensions.)
Public Extension MethodShuffleT(Int32)Overloaded.
Shuffles an enumerable source (randomizes its elements) using the provided seed with a new Random instance.
(Defined by EnumerableExtensions.)
Public Extension MethodShuffleT(Random)Overloaded.
Shuffles an enumerable source (randomizes its elements) using a specified Random instance.
(Defined by EnumerableExtensions.)
Public Extension MethodToCircularListT
Creates a CircularListT from an IEnumerableT.
(Defined by EnumerableExtensions.)
Public Extension MethodTryAdd(Object, Boolean, Boolean)Overloaded.
Tries to add the specified item to the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryAddT(T, Boolean, Boolean)Overloaded.
Tries to add the specified item to the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryAddRange(IEnumerable, Boolean, Boolean)Overloaded.
Tries to add the specified collection to the target collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryAddRangeT(IEnumerableT, Boolean, Boolean)Overloaded.
Tries to add the specified collection to the target collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryClear(Boolean, Boolean)Overloaded.
Tries to remove all elements from the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryClearT(Boolean, Boolean)Overloaded.
Tries to remove all elements from the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryConvert(Type, Object)Overloaded.
Tries to convert an Object specified in the obj parameter to the desired targetType.
(Defined by ObjectExtensions.)
Public Extension MethodTryConvert(Type, CultureInfo, Object)Overloaded.
Tries to convert an Object specified in the obj parameter to the desired targetType.
(Defined by ObjectExtensions.)
Public Extension MethodTryConvertTTarget(TTarget)Overloaded.
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.)
Public Extension MethodTryConvertTTarget(CultureInfo, TTarget)Overloaded.
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.)
Public Extension MethodTryGetElementAt(Int32, Object, Boolean, Boolean)Overloaded.
Tries to get an item at the specified index in the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryGetElementAtT(Int32, T, Boolean, Boolean)Overloaded.
Tries to get an item at the specified index in the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryInsert(Int32, Object, Boolean, Boolean)Overloaded.
Tries to insert the specified item at the specified index to the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryInsertT(Int32, T, Boolean, Boolean)Overloaded.
Tries to insert the specified item at the specified index to the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryInsertRange(Int32, IEnumerable, Boolean, Boolean)Overloaded.
Tries to insert the specified collection into the target collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryInsertRangeT(Int32, IEnumerableT, Boolean, Boolean)Overloaded.
Tries to insert the specified collection into the target collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryRemove(Object, Boolean, Boolean)Overloaded.
Tries to remove the specified item from to the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryRemoveT(T, Boolean, Boolean)Overloaded.
Tries to remove the specified item from to the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryRemoveAt(Int32, Boolean, Boolean)Overloaded.
Tries to remove an item at the specified index from the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryRemoveAtT(Int32, Boolean, Boolean)Overloaded.
Tries to remove an item at the specified index from the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryRemoveRange(Int32, Int32, Boolean, Boolean)Overloaded.
Tries to remove count amount of items from the specified collection at the specified index.
(Defined by EnumerableExtensions.)
Public Extension MethodTryRemoveRangeT(Int32, Int32, Boolean, Boolean)Overloaded.
Tries to remove count amount of items from the specified collection at the specified index.
(Defined by EnumerableExtensions.)
Public Extension MethodTryReplaceRange(Int32, Int32, IEnumerable, Boolean, Boolean)Overloaded.
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.)
Public Extension MethodTryReplaceRangeT(Int32, Int32, IEnumerableT, Boolean, Boolean)Overloaded.
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.)
Public Extension MethodTrySetElementAt(Int32, Object, Boolean, Boolean)Overloaded.
Tries to set the specified item at the specified index in the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTrySetElementAtT(Int32, T, Boolean, Boolean)Overloaded.
Tries to set the specified item at the specified index in the collection.
(Defined by EnumerableExtensions.)
Top
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 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.

See Also

Reference