Skip to main content

6.9 - Advanced Data Structures

Advanced data structures combine the concepts of basic data structures to solve specific problems efficiently. These data structures are designed to optimize certain operations and are used in various applications, from algorithm design to system implementation. This section explores several advanced data structures and their implementations in C#.

6.9.1 - Advanced Collection Types​

C# provides several advanced collection types that extend the functionality of basic collections:

6.9.1.1 - Concurrent Collections​

The System.Collections.Concurrent namespace provides thread-safe collection classes that should be used in multi-threaded scenarios:

// ConcurrentQueue example
ConcurrentQueue<int> concurrentQueue = new ConcurrentQueue<int>();
concurrentQueue.Enqueue(1);
concurrentQueue.Enqueue(2);

// Thread-safe dequeue operation
if (concurrentQueue.TryDequeue(out int result))
{
    Console.WriteLine($"Dequeued: {result}");
}

// ConcurrentDictionary example
ConcurrentDictionary<string, int> concurrentDict = new ConcurrentDictionary<string, int>();
concurrentDict.TryAdd("one", 1);
concurrentDict.TryAdd("two", 2);

// Thread-safe update operation
concurrentDict.AddOrUpdate("one", 10, (key, oldValue) => oldValue + 10);

// ConcurrentBag example (unordered collection)
ConcurrentBag<int> concurrentBag = new ConcurrentBag<int>();
concurrentBag.Add(1);
concurrentBag.Add(2);

// BlockingCollection example (bounded collection)
BlockingCollection<int> blockingCollection = new BlockingCollection<int>(boundedCapacity: 5);
blockingCollection.Add(1); // Will block if collection is full

// In another thread
int item = blockingCollection.Take(); // Will block if collection is empty

6.9.1.2 - Immutable Collections​

The System.Collections.Immutable namespace provides immutable collection classes that cannot be modified after creation:

// Creating immutable collections
ImmutableList<int> immutableList = ImmutableList.Create<int>(1, 2, 3);
ImmutableDictionary<string, int> immutableDict = ImmutableDictionary.Create<string, int>()
    .Add("one", 1)
    .Add("two", 2);

// Creating new collections from existing ones
ImmutableList<int> newList = immutableList.Add(4); // Original list is unchanged
ImmutableDictionary<string, int> newDict = immutableDict.SetItem("one", 10); // Original dict is unchanged
// Benefits of immutable collections:
// 1. Thread safety without locks
// 2. Safe for use as keys in dictionaries
// 3. Snapshot semantics for iterations
// 4. Simplified reasoning about code

6.9.1.3 - Specialized Collections​

C# provides several specialized collections for specific use cases:

// BitArray - compact array of bit values
BitArray bits = new BitArray(8);
bits[0] = true;
bits[1] = false;

// BitVector32 - 32 Boolean values in a single integer
BitVector32 bitVector = new BitVector32(0);
BitVector32.Section section1 = BitVector32.CreateSection(5); // 5 bits
BitVector32.Section section2 = BitVector32.CreateSection(3, section1); // 3 bits
int value = bitVector[section1]; // Get value from section

// StringCollection - specialized for strings
StringCollection strings = new StringCollection();
strings.Add("hello");
strings.Add("world");

// NameValueCollection - multiple string values per key
NameValueCollection nameValues = new NameValueCollection();
nameValues.Add("color", "red");
nameValues.Add("color", "blue");
string[] colors = nameValues.GetValues("color"); // Returns ["red", "blue"]

6.9.2 - Specialized Data Structures​

Let's explore some specialized data structures that solve specific problems:

6.9.2.1 - Bloom Filter​

A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set:

public class BloomFilter
{
    private BitArray bits;
    private int[] hashFunctions;
    private int size;
    
    public BloomFilter(int size, int numHashes)
    {
        this.size = size;
        bits = new BitArray(size);
        hashFunctions = new int[numHashes];
        
        // Initialize hash functions with different seeds
        Random random = new Random(42);
        for (int i = 0; i < numHashes; i++)
        {
            hashFunctions[i] = random.Next();
        }
    }

    public void Add(string item)
    {
        // Apply each hash function to get bit positions
        foreach (int seed in hashFunctions)
        {
            int position = Math.Abs((item.GetHashCode() ^ seed) % size);
            bits[position] = true;
        }
    }
    
    public bool MightContain(string item)
    {
        foreach (int seed in hashFunctions)
        {
            int position = Math.Abs((item.GetHashCode() ^ seed) % size);
            if (!bits[position])
                return false; // Definitely not in the set
        }
        
        return true; // Might be in the set (could be a false positive)
    }
}

6.9.2.2 - Trie (Prefix Tree)​

A trie is a tree-like data structure used to store a dynamic set of strings, where the keys are usually strings:

public class Trie
{
    private class TrieNode
    {
        public Dictionary<char, TrieNode> Children { get; } = new Dictionary<char, TrieNode>();
        public bool IsEndOfWord { get; set; }
    }
    
    private readonly TrieNode root = new TrieNode();
    
    public void Insert(string word)
    {
        TrieNode current = root;
        
        foreach (char c in word)
        {
            if (!current.Children.ContainsKey(c))
                current.Children[c] = new TrieNode();
                
            current = current.Children[c];
        }
        
        current.IsEndOfWord = true;
    }
    
    public bool Search(string word)
    {
        TrieNode node = FindNode(word);
        return node != null && node.IsEndOfWord;
    }
    
    public bool StartsWith(string prefix)
    {
        return FindNode(prefix) != null;
    }
    
    private TrieNode FindNode(string prefix)
    {
        TrieNode current = root;
        
        foreach (char c in prefix)
        {
            if (!current.Children.ContainsKey(c))
                return null;
                
            current = current.Children[c];
        }
        
        return current;
    }
}

6.9.2.3 - Disjoint Set (Union-Find)​

A disjoint-set data structure keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets:

public class DisjointSet
{
    private int[] parent;
    private int[] rank;
    
    public DisjointSet(int size)
    {
        parent = new int[size];
        rank = new int[size];
        
        // Initialize each element as a separate set
        for (int i = 0; i < size; i++)
        {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    // Find the representative (root) of the set containing element x
    public int Find(int x)
    {
        // Path compression: make every examined node point directly to the root
        if (parent[x] != x)
            parent[x] = Find(parent[x]);
            
        return parent[x];
    }
    
    // Union two sets
    public void Union(int x, int y)
    {
        int rootX = Find(x);
        int rootY = Find(y);
        
        if (rootX == rootY)
            return;
            
        // Union by rank: attach smaller rank tree under root of higher rank tree
        if (rank[rootX] < rank[rootY])
        {
            parent[rootX] = rootY;
        }
        else if (rank[rootX] > rank[rootY])
        {
            parent[rootY] = rootX;
        }
        else
        {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

6.9.2.4 - Segment Tree​

A segment tree is a tree data structure used for storing information about intervals or segments:

public class SegmentTree
{
    private int[] tree;
    private int[] lazy;
    private int[] array;
    private int n;
    
    public SegmentTree(int[] arr)
    {
        array = arr;
        n = arr.Length;
        
        // Height of segment tree
        int height = (int)Math.Ceiling(Math.Log(n, 2));
        
        // Maximum size of segment tree
        int maxSize = 2 * (int)Math.Pow(2, height) - 1;
        
        tree = new int[maxSize];
        lazy = new int[maxSize];
        
        BuildTree(0, 0, n - 1);
    }
    
    private void BuildTree(int node, int start, int end)
    {
        if (start == end)
        {
            // Leaf node
            tree[node] = array[start];
            return;
        }
        
        int mid = (start + end) / 2;
        
        // Recursively build left and right subtrees
        BuildTree(2 * node + 1, start, mid);
        BuildTree(2 * node + 2, mid + 1, end);
        
        // Internal node will have the sum of both of its children
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }

    // Query the sum of elements in range [queryStart, queryEnd]
    public int Query(int queryStart, int queryEnd)
    {
        return Query(0, 0, n - 1, queryStart, queryEnd);
    }
    
    private int Query(int node, int start, int end, int queryStart, int queryEnd)
    {
        // If the range is completely outside the query range
        if (start > queryEnd || end < queryStart)
            return 0;
            
        // If the range is completely inside the query range
        if (queryStart <= start && end <= queryEnd)
            return tree[node];
            
        // If the range is partially inside the query range
        int mid = (start + end) / 2;
        int leftSum = Query(2 * node + 1, start, mid, queryStart, queryEnd);
        int rightSum = Query(2 * node + 2, mid + 1, end, queryStart, queryEnd);
        
        return leftSum + rightSum;
    }

6.9.3 - Memory-Efficient Data Structures​

Some data structures are designed to be memory-efficient for specific use cases:

6.9.3.1 - Sparse Arrays​

Sparse arrays are arrays where most elements have the default value (e.g., 0 for numbers). Instead of storing all elements, we only store non-default values:

public class SparseArray<T>
{
    private Dictionary<int, T> elements = new Dictionary<int, T>();
    private T defaultValue;
    private int length;
    
    public SparseArray(int length, T defaultValue = default)
    {
        this.length = length;
        this.defaultValue = defaultValue;
    }
    
    public T this[int index]
    {
        get
        {
            if (index < 0 || index >= length)
                throw new IndexOutOfRangeException();
                
            return elements.TryGetValue(index, out T value) ? value : defaultValue;
        }
        set
        {
            if (index < 0 || index >= length)
                throw new IndexOutOfRangeException();
                
            if (EqualityComparer<T>.Default.Equals(value, defaultValue))
                elements.Remove(index);
            else
                elements[index] = value;
        }
    }
}

6.9.3.2 - Bit Fields​

Bit fields use individual bits to store boolean values, saving memory when you need to store many boolean flags:

[Flags]
public enum Permissions
{
    None = 0,
    Read = 1 << 0,      // 0001
    Write = 1 << 1,     // 0010
    Execute = 1 << 2,   // 0100
    Delete = 1 << 3     // 1000
}

// Usage
Permissions userPermissions = Permissions.Read | Permissions.Write;

// Check if user has read permission
bool canRead = (userPermissions & Permissions.Read) == Permissions.Read;

// Add execute permission
userPermissions |= Permissions.Execute;

// Remove write permission
userPermissions &= ~Permissions.Write;

6.9.4 - Applications of Advanced Data Structures​

Advanced data structures have many practical applications:

  1. Bloom Filters: Used in databases, caches, and spell checkers to quickly determine if an element might be in a set.
  2. Tries: Used in autocomplete, spell checking, and IP routing.
  3. Disjoint Sets: Used in Kruskal's algorithm, finding connected components, and cycle detection.
  4. Segment Trees: Used in range queries, computational geometry, and competitive programming.
  5. Priority Queues: Used in Dijkstra's algorithm, task scheduling, and event simulation.

6.9.5 - Performance Considerations​

When choosing an advanced data structure, consider these performance aspects:

  1. Time Complexity: Different operations may have different time complexities.
  2. Space Complexity: Some structures trade memory for speed.
  3. Implementation Complexity: More complex structures may be harder to implement correctly.
  4. Cache Efficiency: Some structures are more cache-friendly than others.
  5. Concurrency: Some structures are better suited for concurrent access.

Summary​

Advanced data structures extend the capabilities of basic data structures to solve specific problems efficiently. By understanding these structures and their applications, you can choose the right tool for each task and optimize your C# applications for performance, memory usage, and maintainability.

        // Maximum size of segment tree
        int maxSize = 2 * (int)Math.Pow(2, height) - 1;
        
        tree = new int[maxSize];
        lazy = new int[maxSize];
        
        BuildTree(0, 0, n - 1);
    }
    
    private void BuildTree(int node, int start, int end)
    {
        if (start == end)
        {
            tree[node] = array[start];
            return;
        }
        
        int mid = (start + end) / 2;
        
        // Recursively build left and right subtrees
        BuildTree(2 * node + 1, start, mid);
        BuildTree(2 * node + 2, mid + 1, end);
        
        // Internal node will have the sum of both of its children
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }

    // Query the sum of elements in range [queryStart, queryEnd]
    public int Query(int queryStart, int queryEnd)
    {
        return QueryRecursive(0, 0, n - 1, queryStart, queryEnd);
    }
    
    private int QueryRecursive(int node, int start, int end, int queryStart, int queryEnd)
    {
        // If there is a pending lazy update, update the node
        if (lazy[node] != 0)
        {
            tree[node] += (end - start + 1) * lazy[node];
            
            if (start != end)
            {
                lazy[2 * node + 1] += lazy[node];
                lazy[2 * node + 2] += lazy[node];
            }
            
            lazy[node] = 0;
        }
        
        // No overlap
        if (queryStart > end || queryEnd < start)
            return 0;
        
        // Complete overlap
        if (queryStart <= start && queryEnd >= end)
            return tree[node];
        
        // Partial overlap
        int mid = (start + end) / 2;
        int leftSum = QueryRecursive(2 * node + 1, start, mid, queryStart, queryEnd);
        int rightSum = QueryRecursive(2 * node + 2, mid + 1, end, queryStart, queryEnd);
        
        return leftSum + rightSum;
    }
    
    public void Update(int index, int value)
    {
        UpdateRecursive(0, 0, n - 1, index, value);
    }
    
    private void UpdateRecursive(int node, int start, int end, int index, int value)
    {
        // If there is a pending lazy update, update the node
        if (lazy[node] != 0)
        {
            tree[node] += (end - start + 1) * lazy[node];
            
            if (start != end)
            {
                lazy[2 * node + 1] += lazy[node];
                lazy[2 * node + 2] += lazy[node];
            }
            
            lazy[node] = 0;
        }
        
        // No overlap
        if (index < start || index > end)
            return;
        
        // Leaf node
        if (start == end)
        {
            tree[node] = value;
            return;
        }
        
        // Partial overlap
        int mid = (start + end) / 2;
        UpdateRecursive(2 * node + 1, start, mid, index, value);
        UpdateRecursive(2 * node + 2, mid + 1, end, index, value);
        
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
    
    public void UpdateRange(int updateStart, int updateEnd, int value)
    {
        UpdateRangeRecursive(0, 0, n - 1, updateStart, updateEnd, value);
    }
    
    private void UpdateRangeRecursive(int node, int start, int end, int updateStart, int updateEnd, int value)
    {
        // If there is a pending lazy update, update the node
        if (lazy[node] != 0)
        {
            tree[node] += (end - start + 1) * lazy[node];
            
            if (start != end)
            {
                lazy[2 * node + 1] += lazy[node];
                lazy[2 * node + 2] += lazy[node];
            }
            
            lazy[node] = 0;
        }
        
        // No overlap
        if (updateStart > end || updateEnd < start)
            return;
        
        // Complete overlap
        if (updateStart <= start && updateEnd >= end)
        {
            tree[node] += (end - start + 1) * value;
            
            if (start != end)
            {
                lazy[2 * node + 1] += value;
                lazy[2 * node + 2] += value;
            }
            
            return;
        }
        
        // Partial overlap
        int mid = (start + end) / 2;
        UpdateRangeRecursive(2 * node + 1, start, mid, updateStart, updateEnd, value);
        UpdateRangeRecursive(2 * node + 2, mid + 1, end, updateStart, updateEnd, value);
        
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
}

6.9.3.2 - Applications of Segment Tree​

Segment trees are used in various applications:

  1. Range Queries: Finding the sum, minimum, maximum, etc., of a range of elements.
  2. Range Updates: Updating a range of elements.
  3. Computational Geometry: Finding intersections of line segments.
  4. Database Queries: Optimizing range queries in databases.
  5. Competitive Programming: Solving problems involving range queries and updates.

6.9.4 - Fenwick Tree (Binary Indexed Tree)​

A Fenwick tree (also known as a binary indexed tree) is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

6.9.4.1 - Implementation​

public class FenwickTree
{
    private int[] tree;
    private int n;
    
    public FenwickTree(int size)
    {
        n = size + 1;
        tree = new int[n];
    }
    
    public void Update(int index, int value)
    {
        index++; // 1-based indexing
        
        while (index < n)
        {
            tree[index] += value;
            index += index & -index; // Add the least significant bit
        }
    }
    
    public int Query(int index)
    {
        index++; // 1-based indexing
        int sum = 0;
        
        while (index > 0)
        {
            sum += tree[index];
            index -= index & -index; // Remove the least significant bit
        }
        
        return sum;
    }
    
    public int RangeQuery(int left, int right)
    {
        return Query(right) - Query(left - 1);
    }
}

6.9.4.2 - Applications of Fenwick Tree​

Fenwick trees are used in various applications:

  1. Range Sum Queries: Finding the sum of a range of elements.
  2. Range Updates: Updating a range of elements.
  3. Count Inversions: Counting the number of inversions in an array.
  4. Range Frequency Queries: Finding the frequency of an element in a range.
  5. Computational Geometry: Solving problems involving range queries.

6.9.5 - Trie (Prefix Tree)​

A trie (also known as a prefix tree) is a tree-like data structure used to store a dynamic set of strings, where the keys are usually strings. It is particularly useful for searching for keys with a common prefix.

6.9.5.1 - Implementation​

public class Trie
{
    private class TrieNode
    {
        public Dictionary<char, TrieNode> Children { get; } = new Dictionary<char, TrieNode>();
        public bool IsEndOfWord { get; set; }
    }
    
    private TrieNode root = new TrieNode();
    
    public void Insert(string word)
    {
        TrieNode current = root;
        
        foreach (char c in word)
        {
            if (!current.Children.ContainsKey(c))
                current.Children[c] = new TrieNode();
            
            current = current.Children[c];
        }
        
        current.IsEndOfWord = true;
    }
    
    public bool Search(string word)
    {
        TrieNode node = FindNode(word);
        return node != null && node.IsEndOfWord;
    }
    
    public bool StartsWith(string prefix)
    {
        return FindNode(prefix) != null;
    }
    
    private TrieNode FindNode(string word)
    {
        TrieNode current = root;
        
        foreach (char c in word)
        {
            if (!current.Children.ContainsKey(c))
                return null;
            
            current = current.Children[c];
        }
        
        return current;
    }
    
    public List<string> GetWordsWithPrefix(string prefix)
    {
        List<string> words = new List<string>();
        TrieNode node = FindNode(prefix);
        
        if (node != null)
            CollectWords(node, prefix, words);
        
        return words;
    }
    
    private void CollectWords(TrieNode node, string prefix, List<string> words)
    {
        if (node.IsEndOfWord)
            words.Add(prefix);
        
        foreach (var child in node.Children)
            CollectWords(child.Value, prefix + child.Key, words);
    }
}

6.9.5.2 - Applications of Trie​

Tries are used in various applications:

  1. Autocomplete: Suggesting words as a user types.
  2. Spell Checking: Checking if a word is spelled correctly.
  3. IP Routing: Finding the next hop in a routing table.
  4. Longest Prefix Matching: Finding the longest matching prefix in a set of strings.
  5. Word Games: Solving word games like Boggle.

6.9.6 - Suffix Tree and Suffix Array​

Suffix trees and suffix arrays are data structures used for efficient string operations, particularly for substring searches.

6.9.6.1 - Suffix Array Implementation​

public class SuffixArray
{
    private string text;
    private int[] suffixArray;
    
    public SuffixArray(string text)
    {
        this.text = text;
        BuildSuffixArray();
    }
    
    private void BuildSuffixArray()
    {
        int n = text.Length;
        suffixArray = new int[n];
        
        // Initialize suffix array
        for (int i = 0; i < n; i++)
            suffixArray[i] = i;
        
        // Sort suffixes
        Array.Sort(suffixArray, (a, b) => string.Compare(text.Substring(a), text.Substring(b)));
    }
    
    public int[] GetSuffixArray()
    {
        return suffixArray;
    }
    
    public List<int> Search(string pattern)
    {
        List<int> positions = new List<int>();
        int n = text.Length;
        int m = pattern.Length;
        
        // Binary search for the pattern
        int left = 0;
        int right = n - 1;
        
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            int result = string.Compare(pattern, 0, m, text, suffixArray[mid], Math.Min(m, n - suffixArray[mid]));
            
            if (result == 0)
            {
                // Pattern found, collect all occurrences
                positions.Add(suffixArray[mid]);
                
                // Check for more occurrences to the left
                int i = mid - 1;
                while (i >= 0 && string.Compare(pattern, 0, m, text, suffixArray[i], Math.Min(m, n - suffixArray[i])) == 0)
                {
                    positions.Add(suffixArray[i]);
                    i--;
                }
                
                // Check for more occurrences to the right
                i = mid + 1;
                while (i < n && string.Compare(pattern, 0, m, text, suffixArray[i], Math.Min(m, n - suffixArray[i])) == 0)
                {
                    positions.Add(suffixArray[i]);
                    i++;
                }
                
                break;
            }
            else if (result < 0)
                right = mid - 1;
            else
                left = mid + 1;
        }
        
        return positions;
    }
}

6.9.6.2 - Applications of Suffix Tree and Suffix Array​

Suffix trees and suffix arrays are used in various applications:

  1. String Matching: Finding occurrences of a pattern in a text.
  2. Longest Common Substring: Finding the longest substring common to two strings.
  3. Longest Repeated Substring: Finding the longest substring that appears multiple times in a text.
  4. Bioinformatics: Analyzing DNA sequences.
  5. Data Compression: Implementing data compression algorithms.

6.9.7 - Bloom Filter​

A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. It may produce false positives (indicating an element is in the set when it is not), but never false negatives (indicating an element is not in the set when it is).

6.9.7.1 - Implementation​

public class BloomFilter
{
    private BitArray bits;
    private int[] hashSeeds;
    private int size;
    private int hashCount;
    
    public BloomFilter(int size, int hashCount)
    {
        this.size = size;
        this.hashCount = hashCount;
        bits = new BitArray(size);
        hashSeeds = new int[hashCount];
        
        Random random = new Random();
        for (int i = 0; i < hashCount; i++)
            hashSeeds[i] = random.Next();
    }
    
    public void Add(string item)
    {
        for (int i = 0; i < hashCount; i++)
        {
            int hash = GetHash(item, hashSeeds[i]);
            bits[hash] = true;
        }
    }
    
    public bool Contains(string item)
    {
        for (int i = 0; i < hashCount; i++)
        {
            int hash = GetHash(item, hashSeeds[i]);
            if (!bits[hash])
                return false;
        }
        
        return true;
    }
    
    private int GetHash(string item, int seed)
    {
        int hash = item.GetHashCode() ^ seed;
        return Math.Abs(hash) % size;
    }
}

6.9.7.2 - Applications of Bloom Filter​

Bloom filters are used in various applications:

  1. Database Queries: Optimizing database queries by filtering out non-matching records.
  2. Cache Filtering: Determining if an item is in a cache.
  3. Network Routing: Filtering out routing information.
  4. Spell Checking: Checking if a word is spelled correctly.
  5. Web Crawling: Avoiding revisiting the same URLs.

6.9.8 - Skip List​

A skip list is a probabilistic data structure that allows for efficient searching, insertion, and deletion operations. It is an alternative to balanced trees and provides expected O(log n) time complexity for these operations.

6.9.8.1 - Implementation​

public class SkipList<T> where T : IComparable<T>
{
    private class Node
    {
        public T Value { get; set; }
        public Node[] Forward { get; set; }
        
        public Node(T value, int level)
        {
            Value = value;
            Forward = new Node[level + 1];
        }
    }
    
    private const int MaxLevel = 16;
    private const double Probability = 0.5;
    private Node head;
    private int level;
    private Random random;
    
    public SkipList()
    {
        head = new Node(default, MaxLevel);
        level = 0;
        random = new Random();
    }
    
    public void Insert(T value)
    {
        Node[] update = new Node[MaxLevel + 1];
        Node current = head;
        
        for (int i = level; i >= 0; i--)
        {
            while (current.Forward[i] != null && current.Forward[i].Value.CompareTo(value) < 0)
                current = current.Forward[i];
            
            update[i] = current;
        }
        
        current = current.Forward[0];
        
        if (current == null || current.Value.CompareTo(value) != 0)
        {
            int newLevel = RandomLevel();
            
            if (newLevel > level)
            {
                for (int i = level + 1; i <= newLevel; i++)
                    update[i] = head;
                
                level = newLevel;
            }
            
            Node newNode = new Node(value, newLevel);
            
            for (int i = 0; i <= newLevel; i++)
            {
                newNode.Forward[i] = update[i].Forward[i];
                update[i].Forward[i] = newNode;
            }
        }
    }
    
    public bool Contains(T value)
    {
        Node current = head;
        
        for (int i = level; i >= 0; i--)
        {
            while (current.Forward[i] != null && current.Forward[i].Value.CompareTo(value) < 0)
                current = current.Forward[i];
        }
        
        current = current.Forward[0];
        
        return current != null && current.Value.CompareTo(value) == 0;
    }
    
    public bool Remove(T value)
    {
        Node[] update = new Node[MaxLevel + 1];
        Node current = head;
        
        for (int i = level; i >= 0; i--)
        {
            while (current.Forward[i] != null && current.Forward[i].Value.CompareTo(value) < 0)
                current = current.Forward[i];
            
            update[i] = current;
        }
        
        current = current.Forward[0];
        
        if (current != null && current.Value.CompareTo(value) == 0)
        {
            for (int i = 0; i <= level; i++)
            {
                if (update[i].Forward[i] != current)
                    break;
                
                update[i].Forward[i] = current.Forward[i];
            }
            
            while (level > 0 && head.Forward[level] == null)
                level--;
            
            return true;
        }
        
        return false;
    }
    
    private int RandomLevel()
    {
        int lvl = 0;
        while (random.NextDouble() < Probability && lvl < MaxLevel)
            lvl++;
        return lvl;
    }
}

6.9.8.2 - Applications of Skip List​

Skip lists are used in various applications:

  1. Sorted Sets: Implementing sorted sets in Redis.
  2. In-Memory Databases: Implementing in-memory databases.
  3. Priority Queues: Implementing priority queues.
  4. Range Queries: Efficiently handling range queries.
  5. Concurrent Data Structures: Implementing concurrent data structures.

6.9.9 - LRU Cache​

An LRU (Least Recently Used) cache is a cache eviction policy that discards the least recently used items first when the cache reaches its capacity.

6.9.9.1 - Implementation​

public class LRUCache<TKey, TValue>
{
    private class Node
    {
        public TKey Key { get; set; }
        public TValue Value { get; set; }
        public Node Previous { get; set; }
        public Node Next { get; set; }
        
        public Node(TKey key, TValue value)
        {
            Key = key;
            Value = value;
            Previous = null;
            Next = null;
        }
    }
    
    private Dictionary<TKey, Node> cache;
    private Node head;
    private Node tail;
    private int capacity;
    private int count;
    
    public LRUCache(int capacity)
    {
        this.capacity = capacity;
        cache = new Dictionary<TKey, Node>(capacity);
        head = new Node(default, default);
        tail = new Node(default, default);
        head.Next = tail;
        tail.Previous = head;
        count = 0;
    }
    
    public TValue Get(TKey key)
    {
        if (!cache.ContainsKey(key))
            return default;
        
        Node node = cache[key];
        MoveToHead(node);
        return node.Value;
    }
    
    public void Put(TKey key, TValue value)
    {
        if (cache.ContainsKey(key))
        {
            Node node = cache[key];
            node.Value = value;
            MoveToHead(node);
        }
        else
        {
            Node newNode = new Node(key, value);
            cache.Add(key, newNode);
            AddNode(newNode);
            count++;
            
            if (count > capacity)
            {
                Node tail = PopTail();
                cache.Remove(tail.Key);
                count--;
            }
        }
    }
    
    private void AddNode(Node node)
    {
        node.Previous = head;
        node.Next = head.Next;
        head.Next.Previous = node;
        head.Next = node;
    }
    
    private void RemoveNode(Node node)
    {
        Node previous = node.Previous;
        Node next = node.Next;
        previous.Next = next;
        next.Previous = previous;
    }
    
    private void MoveToHead(Node node)
    {
        RemoveNode(node);
        AddNode(node);
    }
    
    private Node PopTail()
    {
        Node res = tail.Previous;
        RemoveNode(res);
        return res;
    }
}

6.9.9.2 - Applications of LRU Cache​

LRU caches are used in various applications:

  1. Database Caching: Caching database query results.
  2. Web Caching: Caching web page content.
  3. Memory Management: Managing memory in operating systems.
  4. Image Caching: Caching images in image processing applications.
  5. Network Caching: Caching network resources.

6.9.10 - Sparse Table​

A sparse table is a data structure used for efficiently answering range queries on static arrays. It is particularly useful for range minimum/maximum queries.

6.9.10.1 - Implementation​

public class SparseTable
{
    private int[,] table;
    private int[] log2;
    private int n;
    
    public SparseTable(int[] array)
    {
        n = array.Length;
        int logN = (int)Math.Floor(Math.Log(n, 2)) + 1;
        
        table = new int[n, logN];
        log2 = new int[n + 1];
        
        // Precompute log2 values
        for (int i = 2; i <= n; i++)
            log2[i] = log2[i / 2] + 1;
        
        // Initialize the sparse table
        for (int i = 0; i < n; i++)
            table[i, 0] = array[i];
        
        // Fill the sparse table
        for (int j = 1; (1 << j) <= n; j++)
        {
            for (int i = 0; i + (1 << j) - 1 < n; i++)
            {
                table[i, j] = Math.Min(table[i, j - 1], table[i + (1 << (j - 1)), j - 1]);
            }
        }
    }
    
    public int Query(int left, int right)
    {
        int length = right - left + 1;
        int k = log2[length];
        
        return Math.Min(table[left, k], table[right - (1 << k) + 1, k]);
    }
}

6.9.10.2 - Applications of Sparse Table​

Sparse tables are used in various applications:

  1. Range Minimum/Maximum Queries: Finding the minimum or maximum value in a range.
  2. Longest Common Prefix: Finding the longest common prefix of two strings.
  3. Lowest Common Ancestor: Finding the lowest common ancestor of two nodes in a tree.
  4. Range GCD Queries: Finding the greatest common divisor of a range of numbers.
  5. Competitive Programming: Solving problems involving range queries.

6.9.11 - Performance Considerations​

When working with advanced data structures, consider the following performance aspects:

  1. Time Complexity: Different data structures have different time complexities for various operations. Choose the appropriate data structure for your specific requirements.
  2. Space Complexity: Advanced data structures often use more memory than basic data structures. Be mindful of memory usage, especially with large datasets.
  3. Implementation Complexity: Some advanced data structures are complex to implement and maintain. Consider using libraries or simpler alternatives when appropriate.
  4. Cache Locality: The memory access pattern of a data structure affects its performance on modern processors. Data structures with good cache locality perform better.

6.9.12 - Best Practices​

Here are some best practices for working with advanced data structures in C#:

  1. Choose the Right Data Structure: Use the appropriate data structure for your specific requirements.
  2. Use Built-in Collections When Possible: Use built-in collections like PriorityQueue<TElement, TPriority> when available.
  3. Implement Custom Data Structures When Needed: Implement custom data structures when you need specific behavior not provided by built-in collections.
  4. Test with Different Dataset Sizes: Test your code with different dataset sizes to ensure it scales well.
  5. Document Data Structure Behavior: Document the behavior of your data structures to make them easier to understand and maintain.
  6. Consider Thread Safety: Ensure thread safety when working with data structures in multi-threaded applications.

This concludes our exploration of data structures in C#. We've covered basic data structures like arrays, lists, stacks, queues, linked lists, hash tables, trees, and graphs, as well as advanced data structures like priority queues, disjoint sets, segment trees, and more. Understanding these data structures and their applications will help you write more efficient and optimized code in C#.