# Singly linked list backed stack

I commented on a question and blindly asserted that a Stack based on a linked list was rather elegant (see here)

I haven't ever written a Stack in C# so I thought I should back up my claim:

public class Stack<T> : IEnumerable<T>
{
protected class StorageNode
{
public T Value { get; set; }

public StorageNode Next { get; set; }

public StorageNode(T value)
{
Value = value;
}
}

public int Count { get; private set; }

public void Push(T value)
{
var newNode = new StorageNode(value);
{
}
++Count;
}

public T Pop()
{
{
throw new InvalidOperationException("Cannot pop an empty stack");
}
--Count;
return result;
}

public IEnumerator<T> GetEnumerator()
{
while (current != null)
{
yield return current.Value;
current = current.Next;
}
}

IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}


I didn't use the .Net LinkedList because I thought it was a bit overkill for a singly linked list...

Is there anything I can improve in my code?

• Not sure about elegance here, to me it looks like you're using the list backwards which does avoid linear popping but I'd just use a 2-linked list since its usage would be more obvious. – user29120 Sep 30 '15 at 13:19
• Your code looks fine to me, but I find an ImmutableStack even more elegant. Here's an example: ericlippert.com/2014/10/16/producing-combinations-part-two – Dennis_E Sep 30 '15 at 13:22
• @AlexM. You don't need double linking because you only need to add and remove at the head of the list. Is that the part you think is backwards? – RobH Sep 30 '15 at 13:23
• Yes, that's the part. head.Next = newNode vs newNode.Next = head; Try to visualize it. It's as if you're making the list accommodate itself to the new entry, instead of accommodating the new entry inside the list. The code is not spread on tons of lines so it's not a particularly hard thing to find out what's going on but it surprised me at first since I expected new elements to be appended to the current head, as I've seen in... all of the linked list so far. – user29120 Sep 30 '15 at 13:24
• @AlexM. I have no problem visualizing it. I'm making a new link and attaching the rest of the list to it. – RobH Sep 30 '15 at 13:26

Personally I would change

public void Push(T value)
{
var newNode = new StorageNode(value);
{
}
++Count;
}


into

public void Push(T value)
{
var newNode = new StorageNode(value);
++Count;
}


because I find the control not really useful. I mean, if the head is null then nothing happens, newNode.Next remains null.

Better yet (in my opinion), if you add a constructor:

public StorageNode(T value, StorageNode next)
{
Value = value;
Next = next;
}


the Push method can be written as:

public void Push(T value)
{
++Count;
}


I've looked at your code and question (and on the answer by Gentian Kasa), and there has been something troubling which I haven't got my head around, but I do believe the main issues I have with your code is the following:

• Unintuitive to use head and Next – To me it is much more intuitive to use either current or topOfStack instead of head, and similarily to use Prev and not Next. It might be a matter of preference, but your code just looks wrong, and that it is not a good sign
• Replace ++Count with Count += 1 – To me, this reads a lot better with Count += 1 instead of the ++Count which I read as a side effect, and when it is on its own line it looks even worse. This also applies for --Count
• Add underscore to private variables – In most companies I've worked in private variables are named _head, reserving head for locally scoped variables, and Head for public variables/properties

So I would have changed the following (along with correcting names in rest of code):

// In StorageNode class
public StorageNode(T value, StorageNode prev = null)
{
Value = value;
Prev = prev;
}

// In Stack class
public Stack() {
_topOfStack = null;
}

public void Push(T value)
{
_topOfStack = new StorageNode(value, _topOfStack);
Count += 1;
}


Added: My little rant on ++Count

Usually one sees this construct in stuff like myArray[++index] or myArray[index++], and I know the syntactic meaning. These reads as Increment index before getting array element at the new index position and Read array element at index, and then increment the index. It has it usages, but can also be rewritten in most cases to something even more readable.

The two usages which I don't get used to seeing are:

++Count;

for (int horizontal = 0, vertical = 0; horizontal < board.length; horizontal += 3) {
if (isWinSet(vertical, vertical + 3, vertical++ + 6)) {


The first I read as: Increment Count before... Ehhh... Nothing.... Awkward, in my opinion. But please note that you are free to your own opinion, and this is not discrediting anyone.

The second is more subtle, but in the loop initialisation both horizontal and vertical is reset. Good. In the loop end statement, horizontal is incremented by 3. Still good. But what about the increment on vertical? It is hidden in the next line, as the third index into the isWinSet( ..., ..., vertical++ + 6)! Not good! This is hard to read: First use vertical + 6 as parameter, and then increment vertical.

The vertical++ + 6 is the side effect at it worst, but after coding for a few years, I tend to avoid using both ++i and i++ to help keep the code easy and understandable. Usually it is much better to use i += 1 on a line of it own.

• I can see the reasoning behind your first point (+1) but I disagree with the other two. – RobH Oct 2 '15 at 7:44
• I should clarify that I have used underscores on private fields in the past but it's against the conventions at my current company and I have grown to prefer not having underscores. – RobH Oct 2 '15 at 7:51
• As said, this is a lot about personal preference, and the c# world is more divided than the Python community with regards to following common guidelines. But I gotten so used to it, that I react a little negative when it is not followed. Then again: Your mileage may vary... – holroy Oct 2 '15 at 8:09
• <rant> I loath underscore in variable names, leading underscores more so. Damn the convention! Leading _ is also akin to type-prefixing the name which I find a significant hindrance in large code files. This stuff is obsolete in the modern IDE. The dash is far superior but alas, not allowed. No need to Shift and the underscore can get hidden under certain display/highlighting on the screen. And depending on editor settings leading leading-underscored variables can sometimes get missed in text searches.<rant> – radarbob Oct 2 '15 at 16:02
• ++Count ... "I read it as a side effect." In a statement on its own there is no side effect. ++Count; and Count++; give the same result. Further using the ++ operator in this way is idiomatic in C# (and other languages), think of the for statement. Now if I wanted to increment without changing the value of Count then yeah, ++Count would be an error - been there done that! – radarbob Oct 2 '15 at 16:08