How to make improve performance on my implement of this LinkedList?

Question

The problem is as follows

A TrainComposition is built by attaching and detaching wagons from the left and the right sides, efficiently with respect to time used.

For example, if we start by attaching wagon 7 from the left followed by attaching wagon 13, again from the left, we get a composition of two wagons (13 and 7 from left to right). Now the first wagon that can be detached from the right is 7 and the first that can be detached from the left is 13.

Implement a TrainComposition that models this problem.

This question may still be relevant in regards to how to solve ordering of a list of items. Originally, I submitted an answer to such a problem posed during a Testdome exercise. While the answer was logically correct, it lacked the performance requirements. Therefore, I asked this question herein.

My updated question, as follows:

I have reviewed different collection types, but am stuck on how to improve performance over my implement of this LinkedList.

The behaviour I need is that of LinkedList collection, but performance is weak. Do you see any tweaks I could make to improve performance? Perhaps there is another type of collection that gives function of linked list and improves performance. I am still working this out. Thanks for the help.

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
    }
}

A similar question was asked here, but using java and not C#. Therefore, the libraries differ and I think it is an unasked question.

EDIT

For clarity, please refer to the above stated Testdome problem description.

If it possible, take my code above, and plunk it into the Testdome client code edit box to run the tests and see results, as follows:

• Example case: Correct answer

• Several wagons: Correct answer
• Performance test with a large number of wagons: Time limit exceeded

EDIT

Using a List, as follows, I also am unable to pass performance requirement:

    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;
    }

LATEST UPDATE

Stay tuned, I am working on updating this question to provide codepen...

Answer 1

In the end, what worked was Steven Cleary's C# implement of Deque, and the following:

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();
}

Is there a simpler solution, than implementing the entirety of Cleary's C# Deque?

As Ivan had commented below, it is possible to achieve the same goals with LinkedList, and calling to RemoveFirst(), and RemoveLast(), as follows:

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;
}