Linked lists, stacks and queues — Data Structures & Algorithms

3. Linked lists, stacks and queues

Basic★ Must knowLesson 3 of 10

Linked list: nodes scattered in memory, each pointing to the next (and previous, in a doubly linked list).

csharp

public class Node<T>(T value) { public T Value = value; public Node<T>? Next; }

Node<int>? Reverse(Node<int>? head)            // classic interview question — O(n) time, O(1) space
{
    Node<int>? prev = null;
    while (head != null)
    {
        var next = head.Next;
        head.Next = prev;      // flip the pointer
        prev = head;
        head = next;
    }
    return prev;
}

	Array/List	Linked list
Index access	O(1)	O(n)
Insert/delete at a known node	O(n) shift	O(1) relink
Memory	Compact, cache-friendly	Extra pointer per node, cache misses

Stack (LIFO) and queue (FIFO) are usually built on arrays (circular buffer for queues):

csharp

bool IsBalanced(string s)                    // stack: matching brackets
{
    var stack = new Stack<char>();
    var pairs = new Dictionary<char, char> { [')'] = '(', [']'] = '[', ['}'] = '{' };
    foreach (char c in s)
    {
        if (c is '(' or '[' or '{') stack.Push(c);
        else if (pairs.TryGetValue(c, out var open) && (stack.Count == 0 || stack.Pop() != open)) return false;
    }
    return stack.Count == 0;
}

The call stack is literally a stack of frames; recursion uses it, which is why deep recursion overflows it.