Stack Using Linked List vs Array Stack Trade-offs in DSA C# - Trade-offs & Analysis

Mental Model

A stack stores items in order, last in first out. It can be built using a linked list or an array, each with different strengths and limits.

Analogy: Think of a stack like a stack of plates. Using an array is like having a fixed-size tray where plates fit exactly. Using a linked list is like stacking plates freely without a tray size limit but with more overhead to keep track of each plate.

Array Stack:
[0] 1
[1] 2
[2] 3 ↑top
[3] null

Linked List Stack:
3 -> 2 -> 1 -> null ↑top

Dry Run Walkthrough

Input: Push 1, Push 2, Push 3, Pop, Push 4 on both Array Stack and Linked List Stack

Goal: Show how each stack changes step-by-step and highlight trade-offs in size and operations

Step 1: Push 1 on array stack and linked list stack

Array: [1] null null null ↑top
Linked List: 1 -> null ↑top

Why: Add first element to both stacks

Step 2: Push 2 on array stack and linked list stack

Array: [1] [2] null null ↑top
Linked List: 2 -> 1 -> null ↑top

Why: Add second element on top of first

Step 3: Push 3 on array stack and linked list stack

Array: [1] [2] [3] null ↑top
Linked List: 3 -> 2 -> 1 -> null ↑top

Why: Add third element on top

Step 4: Pop from array stack and linked list stack

Array: [1] [2] null null ↑top
Linked List: 2 -> 1 -> null ↑top

Why: Remove top element from both stacks

Step 5: Push 4 on array stack and linked list stack

Array: [1] [2] [4] null ↑top
Linked List: 4 -> 2 -> 1 -> null ↑top

Why: Add new element on top after pop

Result:

Array Stack final: 1 -> 2 -> 4 -> null
Linked List Stack final: 4 -> 2 -> 1 -> null

Annotated Code

DSA C#

using System;

public class ArrayStack
{
    private int[] arr;
    private int top;
    private int capacity;

    public ArrayStack(int size)
    {
        arr = new int[size];
        capacity = size;
        top = -1;
    }

    public bool IsEmpty() => top == -1;

    public bool IsFull() => top == capacity - 1;

    public void Push(int val)
    {
        if (IsFull())
        {
            Console.WriteLine("Stack Overflow");
            return;
        }
        top++;
        arr[top] = val; // place val on top
    }

    public int Pop()
    {
        if (IsEmpty())
        {
            Console.WriteLine("Stack Underflow");
            return -1;
        }
        int val = arr[top];
        top--; // remove top element
        return val;
    }

    public void PrintStack()
    {
        for (int i = 0; i <= top; i++)
            Console.Write(arr[i] + " -> ");
        Console.WriteLine("null");
    }
}

public class LinkedListStack
{
    private class Node
    {
        public int val;
        public Node next;
        public Node(int v) { val = v; next = null; }
    }

    private Node top;

    public LinkedListStack() { top = null; }

    public bool IsEmpty() => top == null;

    public void Push(int val)
    {
        Node newNode = new Node(val);
        newNode.next = top; // new node points to old top
        top = newNode; // top moves to new node
    }

    public int Pop()
    {
        if (IsEmpty())
        {
            Console.WriteLine("Stack Underflow");
            return -1;
        }
        int val = top.val;
        top = top.next; // remove top node
        return val;
    }

    public void PrintStack()
    {
        Node curr = top;
        while (curr != null)
        {
            Console.Write(curr.val + " -> ");
            curr = curr.next;
        }
        Console.WriteLine("null");
    }
}

public class Program
{
    public static void Main()
    {
        ArrayStack arrayStack = new ArrayStack(4);
        LinkedListStack linkedListStack = new LinkedListStack();

        // Push 1
        arrayStack.Push(1);
        linkedListStack.Push(1);
        // Push 2
        arrayStack.Push(2);
        linkedListStack.Push(2);
        // Push 3
        arrayStack.Push(3);
        linkedListStack.Push(3);

        // Pop
        arrayStack.Pop();
        linkedListStack.Pop();

        // Push 4
        arrayStack.Push(4);
        linkedListStack.Push(4);

        Console.WriteLine("Array Stack final:");
        arrayStack.PrintStack();

        Console.WriteLine("Linked List Stack final:");
        linkedListStack.PrintStack();
    }
}

top++; arr[top] = val; // place val on top

advance top index and store new value on array stack

top--; // remove top element

decrement top index to pop from array stack

newNode.next = top; top = newNode; // new node becomes top

link new node to current top and update top pointer in linked list stack

top = top.next; // remove top node

move top pointer to next node to pop from linked list stack

Output

Array Stack final:

1 -> 2 -> 4 -> null

Linked List Stack final:

4 -> 2 -> 1 -> null

Complexity Analysis

Time: O(1) for push and pop in both stacks because operations only affect the top element

Space: Array stack uses O(n) fixed space; linked list stack uses O(n) dynamic space growing with elements

vs Alternative: Array stack is faster with less overhead but fixed size; linked list stack is flexible size but uses extra memory for pointers

Edge Cases

Push on full array stack

Prints 'Stack Overflow' and does not add element

DSA C#

if (IsFull()) { Console.WriteLine("Stack Overflow"); return; }

Pop from empty stack

Prints 'Stack Underflow' and returns -1

DSA C#

if (IsEmpty()) { Console.WriteLine("Stack Underflow"); return -1; }

Push and pop single element

Works normally, stack becomes empty after pop

DSA C#

top = top.next; // remove top node

When to Use This Pattern

When you need a last-in-first-out structure and must choose between fixed size or dynamic size, consider array stack for speed and linked list stack for flexibility.

Common Mistakes

Mistake: Forgetting to check if array stack is full before pushing
Fix: Always check IsFull() before push to avoid overflow errors

Mistake: Not updating top pointer correctly in linked list stack push or pop
Fix: Set newNode.next = top and then top = newNode for push; set top = top.next for pop

Summary

Stack can be implemented using array or linked list with different trade-offs.

Use array stack for fixed size and faster access; use linked list stack for dynamic size and flexibility.

Array stack has fixed capacity but less overhead; linked list stack grows dynamically but uses extra memory for pointers.

Practice

1. Which of the following is a key advantage of using a linked list to implement a stack compared to using an array?

easy

A. Accessing elements by index is faster

B. The stack can grow dynamically without a fixed size limit

C. Memory usage is always less

D. It uses less pointer overhead

Solution

1. Step 1: Understand stack growth in arrays

   Arrays have a fixed size, so stacks implemented with arrays have a maximum capacity.

2. Step 2: Understand linked list flexibility

   Linked lists can grow dynamically by adding nodes, so the stack size is limited only by memory.

3. Final Answer:

   The stack can grow dynamically without a fixed size limit -> Option B

4. Quick Check:

   Linked list stacks grow dynamically = B [OK]

Hint: Linked list stacks grow dynamically, arrays have fixed size [OK]

Common Mistakes:

• Thinking arrays can grow dynamically without resizing
• Assuming linked lists use less memory always
• Confusing access speed advantages

2. Which of the following is the correct way to declare an array-based stack of integers with size 10 in C#?

easy

A. int[] stack = new int[10];

B. int stack = new int[10];

C. int[] stack = int[10];

D. int stack[] = new int(10);

Solution

1. Step 1: Recall C# array declaration syntax

   In C#, arrays are declared with type[], then new type[size].

2. Step 2: Check each option

   int[] stack = new int[10]; matches correct syntax: int[] stack = new int[10]; others have syntax errors.

3. Final Answer:

   int[] stack = new int[10]; -> Option A

4. Quick Check:

   C# array syntax = D [OK]

Hint: Use type[] name = new type[size]; for arrays in C# [OK]

Common Mistakes:

• Missing [] after type
• Using parentheses instead of brackets for size
• Declaring array without new keyword

3. Consider this C# code using a linked list stack implementation:

StackNode top = null;
// Push 10
StackNode node1 = new StackNode(10);
node1.Next = top;
top = node1;
// Push 20
StackNode node2 = new StackNode(20);
node2.Next = top;
top = node2;
// Pop
int popped = top.Data;
top = top.Next;
Console.WriteLine(popped);

What is the output?

medium

A. NullReferenceException

B. 10

C. 20

D. 0

Solution

1. Step 1: Trace push operations

   First push 10: top points to node with 10. Then push 20: top points to node with 20, next points to 10.

2. Step 2: Trace pop operation

   Pop reads top.Data = 20, then top moves to next node (10).

3. Final Answer:

   20 -> Option C

4. Quick Check:

   Last pushed is first popped = A [OK]

Hint: Last pushed node is popped first in linked list stack [OK]

Common Mistakes:

• Confusing push order and pop order
• Assuming pop returns bottom element
• Forgetting to update top pointer

4. The following C# code attempts to push an element onto an array-based stack but causes a runtime error:

int[] stack = new int[2];
int top = 2;
stack[top] = 5;

What is the main issue causing the error?

medium

A. NullReferenceException due to uninitialized array

B. Stack overflow exception because stack is full

C. Syntax error in array declaration

D. Array index out of bounds because 'top' equals array size

Solution

1. Step 1: Understand array indexing in C#

   Array indices go from 0 to length-1, so valid indices are 0 and 1 for size 2.

2. Step 2: Check 'top' value usage

   Variable 'top' is 2, which is outside valid index range, causing index out of bounds error.

3. Final Answer:

   Array index out of bounds because 'top' equals array size -> Option D

4. Quick Check:

   Index must be less than array size = A [OK]

Hint: Array indices start at 0, max index is size-1 [OK]

Common Mistakes:

• Confusing stack overflow with index error
• Assuming array indices start at 1
• Ignoring that array is initialized properly

5. You need to implement a stack that will store a very large number of elements, but memory is limited and resizing arrays is costly. Which implementation is better and why?

1. Array-based stack with resizing
2. Linked list-based stack

hard

A. Linked list stack, because it uses memory only as needed and avoids resizing overhead

B. Array stack, because arrays always use less memory than linked lists

C. Array stack, because resizing is fast and memory is unlimited

D. Linked list stack, because it allows random access to elements

Solution

1. Step 1: Consider memory usage and resizing cost

   Array stacks need resizing which copies all elements, costly in time and memory.

2. Step 2: Consider linked list memory behavior

   Linked lists allocate memory per element, no resizing needed, so better for large unknown sizes with limited memory.

3. Final Answer:

   Linked list stack, because it uses memory only as needed and avoids resizing overhead -> Option A

4. Quick Check:

   Linked list avoids resizing overhead = C [OK]

Hint: Linked list stacks avoid costly resizing for large data [OK]

Common Mistakes:

• Assuming arrays always use less memory
• Ignoring resizing cost in arrays
• Thinking linked lists allow random access