CODEWITHSUNDEEP
c#.netcollections
Billy ONeal
Billy ONeal

Reputation: 106589

Why would one use Stack<T> instead of List<T>?

List<T> from System.Collections.Generic does everything Stack<T> does, and more -- they're based on the same underlying data structure. Under what conditions is it correct to choose Stack<T> instead?

Upvotes: 18

Views: 26521

Answers (7)

Akash Kava
Akash Kava

Reputation: 39946

Stack will be used for recursive algorithms where chances of hitting stack overflow is high.

For example, if you want to travel all children of a tree without using recursive method, you would then use Stack.

Recursive Method

void Visit(Node node) {
    // do something with node...
    for each(var child in node.Children) {
        Visit(child); // <<- recursive method.
    }
}

This method uses thread stack, so there is chance that this will cause stack overflow if tree is large enough.

Non Recursive Method

void Visit(Node node) {
    // push node onto stack...
    Stack<Node> stack = new ();
    stack.Push(node);
    while(stack.Count > 0) {
        var visitedNode = stack.Pop();

        // this is the loop of actual logic
        // do something with visited node..
        for each(var child in visitedNode.Children) {
            stack.Push(child);
        }
    }
}

This method doesn't use thread stack. So this method will never cause Stack overflow exception.

The real benefit is, you can actually check Stack's length and abort, where else StackOverflow will kill the app.

Stack is usually used by compilers to analyze huge chunks of code.

Upvotes: 0

Abe Miessler
Abe Miessler

Reputation: 85096

You would use stack if you had a need for a Last In First Out collection of items. A list will allow you to access its items at any index. There are a lot of other differences, but I would say this is the most fundamental.

Update after your comment:

I would say that using Stack<T> makes a statement about how you want this code to be used. It's always good to plan for the future, but if you have a need for Stack<T> right now, and no compelling reason to use List<T>, then I would go with Stack<T>.

Upvotes: 20

Jorge Galv&#227;o
Jorge Galv&#227;o

Reputation: 1893

Besides being conceptually different, as the other the answers already point out, there are also different methods in the Stack that make your code cleaner (and your life easier) than the correspondent code when using a List.

For example, a simple object pool snippet when using a Stack:

if (!pool.TryPop(out var obj))
{
    obj = new Foo();
}

And the same written as a List while keeping the operation O(1):

Foo obj;
int count = pool.Count;
if (count > 0)
{
    obj = pool[--count];
    pool.RemoveAt(count);
}
else
{
    obj = new Foo();
}

Upvotes: 0

dimo414
dimo414

Reputation: 48864

why I would artificially limit myself to using Stack in new code

There's your answer - you should use Stack when you have a need to enforce a contractual expectation that the data structure being used can only be operated on as a stack. Of course, the times you really want to do that are limited, but it's an important tool when appropriate.

For example, supposed the data being worked with doesn't make any sense unless the stack order is enforced. In those cases, you'd be opening yourself up to trouble if you made the data available as a list. By using a Stack (or a Queue, or any other order-sensitive structure) you can specify in your code exactly how the data is supposed to be used.

Upvotes: 8

KeithS
KeithS

Reputation: 71573

It's all about concept. A List is a List, and a Stack is a Stack, and they do two very different things. Their only commonality is their generic nature and their variable length.

A List is a variable-length collection of items in which any element can be accessed and overwritten by index, and to which items can be added and from which items can be removed at any such index.

A Stack is a variable-length collection of items supporting a LIFO access model; only the top element of the Stack can be accessed, and elements can be added to and removed from only that "endpoint" of the collection. The item 3 elements from the "top" can only be accessed by "popping" the two elements above it to expose it.

Use the correct tool for the job; use a List when you need "random" access to any element in the collection. Use a Stack when you want to enforce the more limited "top-only" access to elements in the array. Use a Queue when you want to enforce a FIFO "pipeline"; items go in one end, out the other.

Upvotes: 4

Servy
Servy

Reputation: 203828

Well, you would want to use Stack if you were logically trying to represent a stack. It will convey the intention of the programmer throughout the code if you use a stack, and it will prevent in-advertant mis-use of the data structure (unintentionally adding/removing/reading somewhere other than one end).

It's certainly possible that, rather than a concrete implementation, Stack could just be an interface. You could then have something like List implement that interface. The problem there is mostly a matter of convenience. If someone needs a stack they need to pick some specific implementation and remember ("Oh yeah, List is the preferred stack implementation") rather than just newing up the concrete type.

Upvotes: 5

Nicholas Carey
Nicholas Carey

Reputation: 74307

System.Collections.Generic.Stack<T> is a LIFO (Last-In, First-Out) data structure aka a stack.

Despite its name, SCG.List<T> is not the abstract data type known as a [linked] list: it is, in fact, a variable-length array.

Two very different creatures.

Upvotes: -1

Related Questions