[API Proposal]: LinkedList-DequeList Alternative

Start by reviewing the existing LinkedList, Queue, Stack, and IReadOnlyList APIs against the proposed RollingList design and its usage example. Determine whether the proposed collection belongs in the runtime and define the API, constraints, correctness expectations, and benchmark evidence needed for the feature to be considered complete.

Background and motivation

Reason

I would love an alternative to the current LinkedList implementation.
The most common UC for a LinkedList is just a concoction of Stack and Queue, where both pre- and append aswell as pop/dequeue operations are needed. The LinkedList however is optimized to be modifiable at any position. The way this is achieved is a clear performance threshhold, especially for unordered access, ToArray and usage on big structs.

Feature Suggestion

A type of RollingList that is implemented similarly to Queue or Stack. This allows all comforts of IReadOnlyList objects and also the fast prepend and deque of a Queue.
I have implemented something similar, but I am sure you can work your magic and make it faster.

API Proposal

using System.Collections;

namespace System.Collections.Generic;

<summary>
/// Alternative to the much more costly LinkedList's Prepend/Append Functionality
/// </summary>
/// <typeparam name="T"></typeparam>
public sealed class RollingList<T> : IReadOnlyList<T>
    where T : unmanaged
{
    private const int DefaultCapacity = 16;
    private const int DefaultGrowthCap = 9192;
    private T[] _items;
    private readonly int _growthCap;
    private int _headIndex;
    private int _postTailIndex;
    public int Count { get; private set; }

    public int Capacity => _items.Length;

    public RollingList(int capacity, int growthCap)
    {
        _items = new T[capacity];
        Count = 0;
        _growthCap = int.Max(256, growthCap);
    }

    public RollingList(T[] source, int start = 0, int count = -1, int growthCap = DefaultGrowthCap)
    {
        if (start < 0 || start >= source.Length) throw new ArgumentOutOfRangeException(nameof(start));
        if (count == -1) count = source.Length - start;
        if (count < 0 || count + start > source.Length) throw new ArgumentOutOfRangeException(nameof(count));
        _items = new T[count];
        Array.Copy(source, start, _items, 0, count);
        Count = count;
        _headIndex = 0;
        _postTailIndex = count;
        _growthCap = growthCap;
    }

    public RollingList() : this(DefaultCapacity, DefaultGrowthCap) { }

    public T this[int index]
    {
        get => _items[ValidatedIndex(index)];
        set => _items[ValidatedIndex(index)] = value;
    }
    
    public ref readonly T this[uint index] => ref _items[ValidatedIndex((int)index)];

    private int ValidatedIndex(int index)
    {
        if (InsideInclusiveRange(index, 0, Count - 1))
        {
            index += _headIndex;
            return index < _items.Length ? index : index - _items.Length;
        }
        throw new IndexOutOfRangeException();
    }


    public void PushFront(T item)
    {
        Count++;
        GrowAsNeeded();
        if (_headIndex <= 0) _headIndex = _items.Length;
        _headIndex--;
        _items[_headIndex] = item;
    }

    private void GrowAsNeeded()
    {
        if (Count <= _items.Length) return;

        var arrayLength = _items.Length;
        var newSize = arrayLength + int.Min(_growthCap, arrayLength);
        if (_headIndex == 0)
        {
            Array.Resize(ref _items, newSize);
            return;
        }

        var newArray = new T[newSize];
        var firstMoveSize = arrayLength - _headIndex;
        Array.Copy(_items, _headIndex, newArray, 0, firstMoveSize);
        if (_postTailIndex <= _headIndex)
            Array.Copy(_items, 0, newArray, firstMoveSize, _postTailIndex);
        _items = newArray;
        _headIndex = 0;
        _postTailIndex = Count - 1;
    }

    public void PushBack(T item)
    {
        Count++;
        GrowAsNeeded();
        _postTailIndex++;
        if (_postTailIndex > Capacity) _postTailIndex = 1;
        _items[_postTailIndex - 1] = item;
    }

    public void Add(T item) => PushBack(item);

    public T PopFront()
    {
        if (Count == 0) throw new InvalidOperationException();
        return PopFrontUnchecked();
    }

    private T PopFrontUnchecked()
    {
        Count--;
        var front = _items[_headIndex];
        _headIndex = _headIndex >= _items.Length - 1 ? 0 : _headIndex + 1;
        return front;
    }

    public T PopBack()
    {
        if (Count == 0) throw new InvalidOperationException();
        return PopBackUnchecked();
    }

    private T PopBackUnchecked()
    {
        Count--;
        var back = _items[_postTailIndex - 1];
        _postTailIndex = _postTailIndex <= 1 ? _items.Length : _postTailIndex - 1;
        return back;
    }

    public bool TryPopFront(out T item)
    {
        if (Count == 0)
        {
            item = default;
            return false;
        }

        item = PopFrontUnchecked();
        return true;
    }

    public bool TryPopBack(out T item)
    {
        if (Count == 0)
        {
            item = default;
            return false;
        }

        item = PopBackUnchecked();
        return true;
    }

    public T[] ToArrayFast()
    {
        if(Count==0) return Array.Empty<T>();
        var result=new T[Count];
        if (_headIndex < _postTailIndex)
        {
            Array.Copy(_items, _headIndex, result, 0, Count);
            return result;
        }
        
        var firstMoveSize = _items.Length - _headIndex;
        Array.Copy(_items, _headIndex, result, 0, firstMoveSize);
        Array.Copy(_items, 0, result, firstMoveSize, _postTailIndex);
        return result;
    }
    
    public IEnumerator<T> GetEnumerator()
    {
        if (Count == 0) yield break;
        var arrayLength=_items.Length;
        if (_headIndex < _postTailIndex)
        {
            for (var i = _headIndex; i < _postTailIndex; i++)
                yield return _items[i];
            yield break;
        }
        for (var i = _headIndex; i < arrayLength; i++)
            yield return _items[i];
        for (var i = 0; i < _postTailIndex; i++)
            yield return _items[i];
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    private static bool InsideInclusiveRange(int value, int min, int max)
    {
        var uVal = (uint)value;
        var uMin = (uint)min;
        var uMax = (uint)max;
        return uVal-uMin<=uMax-uMin;
    }
}

API Usage

Useful for sequencebuilding with structs. Offers large Performance Boon over LinkedList.

    public static PolyLine<TVec, TNum>[] UnifyNonReversing<TVec, TNum>(RollingList<Line<TVec, TNum>> segments, TNum? squareTolerance=null) 
        where TNum : unmanaged, IFloatingPointIeee754<TNum> 
        where TVec : unmanaged, IFloatingVector<TVec, TNum>
    {
        var epsilon=squareTolerance?? TNum.CreateTruncating(0.000001);
        if (segments is { Count: 0 }) return [];
        if (segments is { Count: 1 }) return [new([segments[0].Start,segments[0].End])];
        
        List<PolyLine<TVec, TNum>> polyLines = [];
        RollingList<Line<TVec, TNum>> connected = [segments.PopBack()];
        
        var checkedSinceLastAdd = 0;
        while (segments.TryPopBack(out var line))
        {
            if (checkedSinceLastAdd > segments.Count)
            {
                polyLines.Add(PolyLine<TVec, TNum>.FromSegments(connected));
                connected = [];
                connected.PushBack(line);
                checkedSinceLastAdd = 0;
                continue;
            }
            
            var connectedStart= connected[0].Start;
            var connectedEnd = connected[^1].End;
            var checkedPrev=checkedSinceLastAdd;
            checkedSinceLastAdd = 0;
            if (connectedStart.IsApprox(line.End,epsilon)) { connected.PushFront(line); }
            else if (connectedEnd.IsApprox(line.Start,epsilon)){ connected.PushBack(line); }
            else {segments.PushFront(line); checkedSinceLastAdd = checkedPrev+1; }
        }
        if (connected.Count>0) polyLines.Add(PolyLine<TVec,TNum>.FromSegments(connected));
        return polyLines.ToArray();
    }

Alternative Designs

Queue may be extended By Push and Pop Methods , but this would violate the Design.

Risks

On Reference types the above proposed Collection may be slower unless greatly altered. Which is why I have constrained it to unmanaged types.

Performance Benefits

On my local machine simple benchmarks showed clear superiority over LinkedList for the described use cases. Both in terms of execution time and heap-allocation.