Important Data Structures

A comprehensive guide to fundamental data structures with their characteristics, use cases, and C# implementations.

Linear Data Structures

Linked List

Description: Dynamic nodes for efficient insertion and deletion in sequences.

Characteristics:

• O(1) insertion/deletion at known position
• O(n) search
• Dynamic size
• No contiguous memory required

// Built-in LinkedList<T>
var list = new LinkedList<int>();
list.AddLast(1);
list.AddFirst(0);
list.AddAfter(list.First!, 2);

// Custom implementation
public class Node<T>
{
    public T Data { get; set; }
    public Node<T>? Next { get; set; }

    public Node(T data) => Data = data;
}

public class CustomLinkedList<T>
{
    public Node<T>? Head { get; private set; }
    public Node<T>? Tail { get; private set; }

    public void AddLast(T data)
    {
        var node = new Node<T>(data);
        if (Head == null)
        {
            Head = Tail = node;
        }
        else
        {
            Tail!.Next = node;
            Tail = node;
        }
    }
}

Stack

Description: LIFO (Last In, First Out) data structure, supports push and pop operations efficiently.

Characteristics:

• O(1) push/pop/peek
• Great for recursion, undo operations, expression parsing

// Built-in Stack<T>
var stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
int top = stack.Pop();      // 2
int peek = stack.Peek();    // 1

// Use cases
public class ExpressionEvaluator
{
    public int EvaluatePostfix(string expression)
    {
        var stack = new Stack<int>();
        foreach (var token in expression.Split(' '))
        {
            if (int.TryParse(token, out int num))
            {
                stack.Push(num);
            }
            else
            {
                int b = stack.Pop();
                int a = stack.Pop();
                int result = token switch
                {
                    "+" => a + b,
                    "-" => a - b,
                    "*" => a * b,
                    "/" => a / b,
                    _ => throw new InvalidOperationException()
                };
                stack.Push(result);
            }
        }
        return stack.Pop();
    }
}

Queue

Description: FIFO (First In, First Out) linear data structure, supports enqueue and dequeue operations.

Characteristics:

• O(1) enqueue/dequeue
• Great for task scheduling, BFS, buffering

// Built-in Queue<T>
var queue = new Queue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
int first = queue.Dequeue();  // 1

// Producer-Consumer pattern
public class TaskQueue<T>
{
    private readonly Queue<T> _queue = new();
    private readonly object _lock = new();

    public void Enqueue(T item)
    {
        lock (_lock)
        {
            _queue.Enqueue(item);
            Monitor.Pulse(_lock);
        }
    }

    public T Dequeue()
    {
        lock (_lock)
        {
            while (_queue.Count == 0)
                Monitor.Wait(_lock);
            return _queue.Dequeue();
        }
    }
}

Priority Queue

Description: Efficient data structure combining queue and heap properties.

Characteristics:

• O(log n) insert/remove
• O(1) peek min/max
• Great for task scheduling with priorities

// .NET 6+ PriorityQueue<TElement, TPriority>
var pq = new PriorityQueue<string, int>();
pq.Enqueue("Low priority", 3);
pq.Enqueue("High priority", 1);
pq.Enqueue("Medium priority", 2);

while (pq.TryDequeue(out var task, out var priority))
{
    Console.WriteLine($"{task} (priority: {priority})");
}
// Output:
// High priority (priority: 1)
// Medium priority (priority: 2)
// Low priority (priority: 3)

Tree Data Structures

Heap

Description: Priority-based binary tree data structure for efficient operations.

Types:

• Min Heap: Parent <= children (root is minimum)
• Max Heap: Parent >= children (root is maximum)

// Using PriorityQueue as Min Heap
var minHeap = new PriorityQueue<int, int>();
minHeap.Enqueue(5, 5);
minHeap.Enqueue(3, 3);
minHeap.Enqueue(8, 8);
// Dequeue returns: 3, 5, 8

// Max Heap by negating priority
var maxHeap = new PriorityQueue<int, int>();
maxHeap.Enqueue(5, -5);
maxHeap.Enqueue(3, -3);
maxHeap.Enqueue(8, -8);
// Dequeue returns: 8, 5, 3

Binary Tree

Description: Hierarchical structure, efficient for searching and organizing hierarchical relationships.

public class BinaryTreeNode<T>
{
    public T Value { get; set; }
    public BinaryTreeNode<T>? Left { get; set; }
    public BinaryTreeNode<T>? Right { get; set; }

    public BinaryTreeNode(T value) => Value = value;
}

public class BinarySearchTree<T> where T : IComparable<T>
{
    public BinaryTreeNode<T>? Root { get; private set; }

    public void Insert(T value)
    {
        Root = InsertRecursive(Root, value);
    }

    private BinaryTreeNode<T> InsertRecursive(BinaryTreeNode<T>? node, T value)
    {
        if (node == null)
            return new BinaryTreeNode<T>(value);

        if (value.CompareTo(node.Value) < 0)
            node.Left = InsertRecursive(node.Left, value);
        else
            node.Right = InsertRecursive(node.Right, value);

        return node;
    }

    public bool Contains(T value)
    {
        var current = Root;
        while (current != null)
        {
            int comparison = value.CompareTo(current.Value);
            if (comparison == 0) return true;
            current = comparison < 0 ? current.Left : current.Right;
        }
        return false;
    }
}

B-Tree

Description: Balanced search tree for efficient retrieval, commonly used in databases.

Characteristics:

• Self-balancing
• Multiple keys per node
• Optimized for disk access
• Used in database indexes

// Conceptual B-Tree node
public class BTreeNode<T> where T : IComparable<T>
{
    public List<T> Keys { get; } = new();
    public List<BTreeNode<T>> Children { get; } = new();
    public bool IsLeaf { get; set; }
    public int Degree { get; }

    public BTreeNode(int degree, bool isLeaf)
    {
        Degree = degree;
        IsLeaf = isLeaf;
    }
}

Hash-Based Structures

Hash Index / Hash Table

Description: Hash function-based data retrieval structure in databases.

Characteristics:

• O(1) average lookup, insert, delete
• Key-value storage

// Built-in Dictionary<TKey, TValue>
var dict = new Dictionary<string, int>
{
    ["apple"] = 1,
    ["banana"] = 2
};

// HashSet<T> for unique values
var set = new HashSet<int> { 1, 2, 3 };
bool exists = set.Contains(2);  // O(1)

// Custom hash table implementation
public class SimpleHashTable<TKey, TValue> where TKey : notnull
{
    private readonly LinkedList<KeyValuePair<TKey, TValue>>[] _buckets;
    private readonly int _size;

    public SimpleHashTable(int size = 16)
    {
        _size = size;
        _buckets = new LinkedList<KeyValuePair<TKey, TValue>>[size];
    }

    private int GetBucketIndex(TKey key) =>
        Math.Abs(key.GetHashCode()) % _size;

    public void Add(TKey key, TValue value)
    {
        int index = GetBucketIndex(key);
        _buckets[index] ??= new LinkedList<KeyValuePair<TKey, TValue>>();
        _buckets[index].AddLast(new KeyValuePair<TKey, TValue>(key, value));
    }

    public TValue? Get(TKey key)
    {
        int index = GetBucketIndex(key);
        if (_buckets[index] == null) return default;

        foreach (var kvp in _buckets[index])
        {
            if (kvp.Key.Equals(key))
                return kvp.Value;
        }
        return default;
    }
}

Graph Structures

Graph

Description: Nodes and edges representing relationships, versatile data structure for modeling scenarios.

public class Graph<T> where T : notnull
{
    private readonly Dictionary<T, HashSet<T>> _adjacencyList = new();

    public void AddVertex(T vertex)
    {
        if (!_adjacencyList.ContainsKey(vertex))
            _adjacencyList[vertex] = new HashSet<T>();
    }

    public void AddEdge(T from, T to, bool bidirectional = true)
    {
        AddVertex(from);
        AddVertex(to);
        _adjacencyList[from].Add(to);
        if (bidirectional)
            _adjacencyList[to].Add(from);
    }

    // BFS traversal
    public IEnumerable<T> BFS(T start)
    {
        var visited = new HashSet<T>();
        var queue = new Queue<T>();
        queue.Enqueue(start);
        visited.Add(start);

        while (queue.Count > 0)
        {
            var vertex = queue.Dequeue();
            yield return vertex;

            foreach (var neighbor in _adjacencyList[vertex])
            {
                if (!visited.Contains(neighbor))
                {
                    visited.Add(neighbor);
                    queue.Enqueue(neighbor);
                }
            }
        }
    }

    // DFS traversal
    public IEnumerable<T> DFS(T start)
    {
        var visited = new HashSet<T>();
        var stack = new Stack<T>();
        stack.Push(start);

        while (stack.Count > 0)
        {
            var vertex = stack.Pop();
            if (visited.Contains(vertex))
                continue;

            visited.Add(vertex);
            yield return vertex;

            foreach (var neighbor in _adjacencyList[vertex])
            {
                if (!visited.Contains(neighbor))
                    stack.Push(neighbor);
            }
        }
    }
}

Advanced Structures

Skip List

Description: Probabilistic linked list alternative for efficient searching and insertion.

Characteristics:

• O(log n) average search, insert, delete
• Simpler than balanced trees
• Used in Redis sorted sets

LSM Tree (Log-Structured Merge Tree)

Description: Key-value store design, optimizing write-intensive workloads through sorted merging.

Use Cases:

• LevelDB, RocksDB
• Apache Cassandra
• Write-heavy databases

Inverted Index

Description: Document-to-term mapping for efficient full-text searches in documents.

Use Cases:

• Search engines
• Elasticsearch
• Full-text search

public class InvertedIndex
{
    private readonly Dictionary<string, HashSet<int>> _index = new();

    public void IndexDocument(int docId, string content)
    {
        var words = content.ToLower().Split(' ', StringSplitOptions.RemoveEmptyEntries);
        foreach (var word in words)
        {
            if (!_index.ContainsKey(word))
                _index[word] = new HashSet<int>();
            _index[word].Add(docId);
        }
    }

    public IEnumerable<int> Search(string term)
    {
        return _index.TryGetValue(term.ToLower(), out var docs)
            ? docs
            : Enumerable.Empty<int>();
    }
}

SSTable (Sorted String Table)

Description: Immutable table for key-value pairs, optimized for write-once, read-many.

Characteristics:

• Immutable, ordered key-value pairs
• Used in LSM Tree implementations
• Efficient for sequential reads

Data Structure Selection Guide

Sources

• Arhitectura/data types.jpeg