Stack, Queue and LinkedList

1. What is the difference between Stack<T> and Queue<T>?

What is Stack?

Stack<T> is a generic collection in C# that follows the LIFO (Last In, First Out) principle.

The last element added to the stack is the first element removed.

Real-world example: A stack of plates. The last plate placed on top is removed first.

What is Queue?

Queue<T> is a generic collection that follows the FIFO (First In, First Out) principle.

The first element added to the queue is the first element removed.

Real-world example: Customers waiting in a bank. The first customer in the queue is served first.

Comparison

Example Program

// Stack Example
Stack<string> stack = new();

stack.Push("John");
stack.Push("David");
stack.Push("Peter");

Console.WriteLine("Stack:");
Console.WriteLine(stack.Pop());
Console.WriteLine(stack.Pop());

// Queue Example
Queue<string> queue = new();

queue.Enqueue("John");
queue.Enqueue("David");
queue.Enqueue("Peter");

Console.WriteLine("Queue:");
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Dequeue());

Output:

Stack:
Peter
David

Queue:
John
David

Program Explanation

Stack:

1. Push("John") adds John.

2. Push("David") adds David.

3. Push("Peter") adds Peter.

4. Pop() removes Peter because he was added last.

5. The next Pop() removes David.

Queue:

1. Enqueue("John") adds John.

2. Enqueue("David") adds David.

3. Enqueue("Peter") adds Peter.

4. Dequeue() removes John because he was added first.

5. The next Dequeue() removes David.

Internal Working

Stack – LIFO

Push(John)
Push(David)
Push(Peter)

     TOP
      |
      v
  +---------+
  | Peter   |  <-- Removed first
  +---------+
  | David   |
  +---------+
  | John    |
  +---------+

Pop() -> Peter
Pop() -> David
Pop() -> John

Queue – FIFO

Enqueue(John)
Enqueue(David)
Enqueue(Peter)

FRONT                         REAR
  |                             |
  v                             v
+--------+--------+---------+
| John   | David  | Peter   |
+--------+--------+---------+
  |
  v
Removed first

Dequeue() -> John
Dequeue() -> David
Dequeue() -> Peter

Key Points

• Stack follows LIFO.

• Queue follows FIFO.

• Both are generic collections in System.Collections.Generic.

• Stack uses Push(), Pop() and Peek().

• Queue uses Enqueue(), Dequeue() and Peek().

• Both provide O(1) removal of the next element.

• Neither is thread-safe for concurrent modifications.

Interview Tip: Use Stack<T> for undo operations or backtracking. Use Queue<T> for processing requests in arrival order.

2. What is the difference between Push(), Pop(), and Peek()?

Explanation

These three methods are commonly used with Stack<T>.

• Push() – Adds an element to the top of the stack.

• Pop() – Removes and returns the top element.

• Peek() – Returns the top element without removing it.

Comparison

Example Program

Stack<int> numbers = new();

// Add elements
numbers.Push(10);
numbers.Push(20);
numbers.Push(30);

// Read top element
Console.WriteLine(numbers.Peek());

// Remove top element
Console.WriteLine(numbers.Pop());

// Read current top
Console.WriteLine(numbers.Peek());

// Count remaining elements
Console.WriteLine(numbers.Count);

Output:

30
30
20
2

Program Explanation

1. Push(10) adds 10 to the stack.

2. Push(20) adds 20.

3. Push(30) adds 30 at the top.

4. Peek() returns 30 without removing it.

5. Pop() returns and removes 30.

6. Peek() now returns 20.

7. Count returns 2 because two elements remain.

Internal Working

Initial Stack

   TOP
    |
    v
+------+
|  30  |
+------+
|  20  |
+------+
|  10  |
+------+


Peek()
-------
Returns 30
Stack unchanged


Pop()
------
Returns 30
Removes 30

   TOP
    |
    v
+------+
|  20  |
+------+
|  10  |
+------+


Push(40)
--------
Adds 40

   TOP
    |
    v
+------+
|  40  |
+------+
|  20  |
+------+
|  10  |
+------+

What happens when the Stack is empty?

Calling Pop() or Peek() on an empty stack throws an InvalidOperationException.

Stack<int> numbers = new();

if (numbers.Count > 0)
{
    Console.WriteLine(numbers.Pop());
}
else
{
    Console.WriteLine("Stack is empty");
}

Modern .NET also supports TryPop() and TryPeek().

if (numbers.TryPop(out int value))
{
    Console.WriteLine(value);
}

These methods return false when the stack is empty instead of throwing an exception.

Key Points

• Push() adds an element.

• Pop() removes and returns the top element.

• Peek() reads without removing.

• Pop() and Peek() throw exceptions when the stack is empty.

• TryPop() and TryPeek() provide safer alternatives.

• All three operations have O(1) complexity, except that Push() is amortized O(1) because resizing may occur.

Interview Tip: The most important distinction is that Pop() removes an element, whereas Peek() does not.

3. What is the difference between List<T> and LinkedList<T>?

What is List?

List<T> is a generic collection that stores elements in a dynamically resized array.

It supports fast index-based access.

What is LinkedList?

LinkedList<T> is a generic collection that stores elements as doubly linked nodes.

Each node contains:

• Value

• Reference to the previous node

• Reference to the next node

Unlike List<T>, elements are not stored in a single contiguous array.

Comparison

For LinkedList, O(1) insertion/removal assumes the required node is already known. Searching for a node takes O(n).

Example Program

Using List:

List<string> employees = new()
{
    "John",
    "David",
    "Peter"
};

// Access by index
Console.WriteLine(employees[1]);

// Insert at beginning
employees.Insert(0, "Robert");

foreach (var employee in employees)
{
    Console.WriteLine(employee);
}

Output:

David
Robert
John
David
Peter

Using LinkedList:

LinkedList<string> employees = new();

employees.AddLast("John");
employees.AddLast("David");
employees.AddLast("Peter");

// Insert at beginning
employees.AddFirst("Robert");

// Insert after David
var node = employees.Find("David");

if (node != null)
{
    employees.AddAfter(node, "Michael");
}

foreach (var employee in employees)
{
    Console.WriteLine(employee);
}

Output:

Robert
John
David
Michael
Peter

Program Explanation

List:

1. Creates a dynamic array containing three employee names.

2. employees[1] directly accesses David.

3. Insert(0, "Robert") inserts Robert at the beginning.

4. Existing elements are shifted to the right.

LinkedList:

1. AddLast() inserts elements at the end.

2. AddFirst() inserts Robert at the beginning.

3. Find("David") searches for the node containing David.

4. AddAfter() inserts Michael after David.

5. Existing nodes do not need to be shifted.

Internal Working

List – Dynamic Array

Before Insert(0, "Robert")

Index     0       1        2
       +-------+-------+-------+
       | John  | David | Peter |
       +-------+-------+-------+


After Insert(0, "Robert")

Index     0        1       2        3
       +--------+-------+-------+-------+
       | Robert | John  | David | Peter |
       +--------+-------+-------+-------+

Existing elements shifted right.

LinkedList – Doubly Linked Nodes

Before AddAfter(David, "Michael")

NULL
  |
  v
[John] <--> [David] <--> [Peter]
                            |
                            v
                           NULL


After AddAfter(David, "Michael")

NULL
  |
  v
[John] <--> [David] <--> [Michael] <--> [Peter]
                                          |
                                          v
                                         NULL

Only node references are updated.
No shifting required.

How does LinkedList insertion work internally?

Suppose we insert Michael after David.

Before:

David.Next = Peter
Peter.Previous = David


After:

David.Next = Michael
Michael.Previous = David

Michael.Next = Peter
Peter.Previous = Michael

The collection updates the links between nodes instead of moving existing elements.

Real-World Scenarios

Use List<T> when:

• Displaying employee records.

• Accessing items by index.

• Iterating through large collections.

• Frequently appending elements.

Use LinkedList<T> when:

• Implementing an LRU cache.

• Maintaining a sequence with frequent insertions and removals at known positions.

• Implementing custom navigation or scheduling structures.

Key Points

• List<T> uses a dynamic array.

• LinkedList<T> uses doubly linked nodes.

• List supports index-based access; LinkedList does not.

• List provides O(1) index access.

• LinkedList provides O(1) insertion/removal when the node is known.

• LinkedList requires additional memory for node references.

• List<T> is generally the preferred default due to cache locality and lower memory overhead.

Interview Tip: Do not assume LinkedList is always faster for insertion. If you first need to search for the node, the total operation can still take O(n).

Quick Interview Revision

Most important for interviews: Understand LIFO vs FIFO, Push() vs Pop() vs Peek(), and why List<T> is usually preferred over LinkedList<T> despite LinkedList's O(1) node insertion and removal.