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

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

Kagera

might be related #170473 – Hymettus

Your DetachWagonFromRight method does not in fact remove the last element - if you have another element in the LinkedList with the same value that one will be removed instead – Naughton

What kind of performance improvement are you looking for? How do you measure? – Crumby

You might want to consider List<T> instead of LinkedList – Huckaback

I have no idea what your performance issues are (you haven't defined them), I have no idea what your performance goals are (you haven't defined them). Even still I made a quick version of your code using List, fiddle here – Huckaback

I'm confused what First and Last has to do with Right and Left. If you add a wagon to the left, and it's the only wagon, then removing one from the Right will remove it? What kind of crazy wagon train is this?? :) (to be serious, though, I assumed you would have a "Left" linked list and a "Right" linked list that shared the same Head node when I first started reading the code. That would make more sense to me, assuming your wagon train is configured in a "V", like a flight of geese...) – Donell

@RufusL Ah thats a good point, I did not read it like that at first. If OP can confirm I will adjust my fiddle – Huckaback

@RufusL To my understanding, OP is interpreting a LinkedList to be a list of things from left to right (not like a "V"), where Left = Front and Right = Last. So a wagon on the right could very well be the left most wagon as well if there is only 1 wagon. – Silviasilviculture

@BlakeThingstad I'm sure you're right, and that's what his code seems to represent. I've just never heard of a wagon train configured like that, so it was likely just my own interpretation bias – Donell

OP, have you looked into binary tree data structures? As others have mentioned, it's not clear what you are trying to improve with what you have, but it may help... snipd.net/binary-search-trees-bsts-in-c – Donell

@RufusL Oh true, I was imagining just a train so they would be front to back. I suppose a bunch of wagons could more commonly be arranged in a "V". – Silviasilviculture

@BlakeThingstad Agree, front to back also makes sense. But again, that would be "first and last" not "left and right" (to me, anyway). – Donell

performance is weak What performance are you seeing? What do you need / seek? Have you tried using List instead? – Cassareep

I updated my question to provide link to original answer in hopes this clears up the nature of this question. BTW... thanks Slai, this is related to the question you referenced, and I submitted an answer to it as such. – Kagera

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

Kagera

What about that solution is not simple enough for you? Each method is one line long - I am not sure how it is even possible to make that any simpler. – Cassareep

mjwills: I was making reference to Deque. Take a look at Cleary's implement of Deque (link in my answer). I haven't made the time to look it through. I will because I am interested to learn how it achieves performance over the LinkedList collection. If I need a LinkedList functionality with improved performance, then Cleary's Deque is my C# choice right now. Thanks! – Kagera

The LinkedList is indeed the best for this task. The only inefficient parts are the Remove calls inside the Detach methods, since they involve unnecessary linear search. Replace them with RemofeFirst() and RemoveLast() respectively and you are done. – Edra

@Ivan Stoev - you are correct. I went back and reviewed my answer. I have EDITED my answer to include an code for LinkedList with your suggestion of calling RemoveFirst() and RemoveLast(). Thank you!! – Kagera

@AdamCox: FWIW, the fundamental mistake in your original code was that you called remove with a value from the list, instead of with a node. To use LinkedList well, always work with nodes. It doesn't matter at the ends, because RemoveFirst and RemoveLast exist. But in more general algorithms, pass around nodes, not values. Wagons.First and Wagons.Last are nodes. If RemoveFirst did not exist, the node-based implementation of DetachWagonFromLeft() is var node = Wagons.First; Wagons.Remove(node); return node.Value; This is as efficient as RemoveFirst. – Barman