Как повысить производительность в моем проекте LinkedList?

Я просмотрел различные типы коллекций, но я зациклился на том, как повысить производительность над моим реализацией этого LinkedList.

Поведение, в котором я нуждаюсь, - это сборка LinkedList, но производительность слабая. Вы видите какие-либо хитрости, которые я мог бы сделать для повышения производительности? Возможно, есть еще один тип коллекции, который дает функцию связанного списка и повышает производительность. Я все еще работаю над этим. Спасибо за помощь.

using System;
using System.Collections.Generic;
using System.Linq;

public class TrainComposition
{

    public TrainComposition()
    {
        Wagons = new LinkedList<int>();
    }

    private LinkedList<int> Wagons;

    public void AttachWagonFromLeft(int wagonId)
    {
        Wagons.AddFirst(wagonId);
    }

    public void AttachWagonFromRight(int wagonId)
    {
        Wagons.AddLast(wagonId);
    }

    public int DetachWagonFromLeft()
    {
        var wagon = Wagons.First.Value;
        Wagons.Remove(wagon);
        return wagon;
    }

    public int DetachWagonFromRight()
    {
        var wagon = Wagons.Last.Value;
        Wagons.Remove(wagon);
        return wagon;
    }

    public static void Main(string[] args)
    {
        TrainComposition tree = new TrainComposition();
        tree.AttachWagonFromLeft(7);
        tree.AttachWagonFromLeft(13);
        Console.WriteLine(tree.DetachWagonFromRight()); // 7 
        Console.WriteLine(tree.DetachWagonFromLeft()); // 13
    }
}

Аналогичный вопрос был задан здесь, но с использованием java, а не С#. Поэтому библиотеки различаются, и я думаю, что это вопрос, который не задан.

ИЗМЕНИТЬ

Для большей наглядности обратитесь к оригиналу Описание проблемы Testdome.

Возьмите мой код выше и залейте его в поле редактирования кода клиента, чтобы запустить тесты и просмотреть результаты, как показано ниже:

  • Пример: правильный ответ
  • Несколько вагонов: правильный ответ
  • Тест производительности с большим количеством вагонов: превышен лимит времени

ИЗМЕНИТЬ

Используя список, следующим образом, я также не могу выполнить требования к производительности:

    public TrainComposition()
    {
        Wagons = new List<int>();
    }

    private List<int> Wagons;

    public void AttachWagonFromLeft(int wagonId) // insert at index 0
    {
        Wagons.Insert(0, wagonId);
    }

    public void AttachWagonFromRight(int wagonId) // add item to last/end 
    {
        Wagons.Add(wagonId);
    }

    public int DetachWagonFromLeft() // remove first item (index = 0)
    {
        var wagon = Wagons[0];
        Wagons.RemoveAt(0);
        return wagon;
    }

    public int DetachWagonFromRight() // remove last item (index = count - 1)
    {
        var lastWagonIndex = Wagons.Count() - 1;
        var wagon = Wagons[lastWagonIndex];
        Wagons.RemoveAt(lastWagonIndex);
        return wagon;
    }

Ответы

Ответ 1

В конце концов, что работало Steven Cleary С# реализация Deque и следующее:

public TrainComposition()
{
    Wagons = new Deque<int>();
}

private Deque<int> Wagons;

public void AttachWagonFromLeft(int wagonId)
{
    Wagons.AddToBack(wagonId);
}

public void AttachWagonFromRight(int wagonId)
{
    Wagons.AddToFront(wagonId);
}

public int DetachWagonFromLeft()
{
    return Wagons.RemoveFromBack();
}

public int DetachWagonFromRight()
{
    return Wagons.RemoveFromFront();
}

Есть ли более простое решение, чем реализация целого Cleary С# Deque?

Как сказал Иван, ниже, можно достичь тех же целей с помощью LinkedList и вызвать RemoveFirst() и RemoveLast() следующим образом:

public TrainComposition()
{
    Wagons = new LinkedList<int>();
}

private LinkedList<int> Wagons;

public void AttachWagonFromLeft(int wagonId)
{
    Wagons.AddFirst(wagonId);
}

public void AttachWagonFromRight(int wagonId)
{
    Wagons.AddLast(wagonId);
}

public int DetachWagonFromLeft()
{
    var wagon = Wagons.First.Value;
    Wagons.RemoveFirst();
    return wagon;
}

public int DetachWagonFromRight()
{
    var wagon = Wagons.Last.Value;
    Wagons.RemoveLast();
    return wagon;
}