UnrolledLinkedList.cs

using System.Collections.Generic;

namespace DataStructures.UnrolledList;

/// <summary>
/// Unrolled linked list is a linked list of small arrays,
/// all of the same size where each is so small that the insertion
/// or deletion is fast and quick, but large enough to fill the cache line.
/// </summary>
public class UnrolledLinkedList
{
    private readonly int sizeNode;

    private UnrolledLinkedListNode start = null!;
    private UnrolledLinkedListNode end = null!;

    /// <summary>
    /// Initializes a new instance of the <see cref="UnrolledLinkedList"/> class.
    /// Create a unrolled list with start chunk size.
    /// </summary>
    /// <param name="chunkSize">The size of signe chunk.</param>
    public UnrolledLinkedList(int chunkSize)
    {
        sizeNode = chunkSize + 1;
    }

    /// <summary>
    /// Add value to list [O(n)].
    /// </summary>
    /// <param name="value">The entered value.</param>
    public void Insert(int value)
    {
        if (start == null)
        {
            start = new UnrolledLinkedListNode(sizeNode);
            start.Set(0, value);

            end = start;
            return;
        }

        if (end.Count + 1 < sizeNode)
        {
            end.Set(end.Count, value);
        }
        else
        {
            var pointer = new UnrolledLinkedListNode(sizeNode);
            var j = 0;
            for (var pos = end.Count / 2 + 1; pos < end.Count; pos++)
            {
                pointer.Set(j++, end.Get(pos));
            }

            pointer.Set(j++, value);
            pointer.Count = j;

            end.Count = end.Count / 2 + 1;
            end.Next = pointer;
            end = pointer;
        }
    }

    /// <summary>
    /// Help method. Get all list inside to check the state.
    /// </summary>
    /// <returns>Items from all nodes.</returns>
    public IEnumerable<int> GetRolledItems()
    {
        UnrolledLinkedListNode pointer = start;
        List<int> result = new();

        while (pointer != null)
        {
            for (var i = 0; i < pointer.Count; i++)
            {
                result.Add(pointer.Get(i));
            }

            pointer = pointer.Next;
        }

        return result;
    }
}