Skip to main content

6.1 - Data Structures Basics

Data structures are specialized formats for organizing, processing, retrieving, and storing data. They provide a way to manage large amounts of data efficiently for uses such as large databases and internet indexing services. In C#, data structures are fundamental to writing efficient and optimized code.

6.1.1 - Importance of Data Structures​

Data structures are essential for several reasons:

  1. Efficiency: Proper data structures can significantly improve the performance of algorithms.
  2. Abstraction: They provide a level of abstraction that allows developers to focus on the problem rather than implementation details.
  3. Reusability: Well-designed data structures can be reused across different applications.
  4. Organization: They help in organizing data in a way that makes it easier to manipulate and retrieve.

6.1.2 - Classification of Data Structures​

Data structures can be classified in several ways:

6.1.2.1 - Linear vs. Non-Linear​

  • Linear Data Structures: Elements are arranged in a sequential manner, where each element is connected to its previous and next elements. Examples include arrays, linked lists, stacks, and queues.
  • Non-Linear Data Structures: Elements are not arranged sequentially. Examples include trees and graphs.

6.1.2.2 - Static vs. Dynamic​

  • Static Data Structures: Fixed size, memory allocated at compile time. Example: Arrays.
  • Dynamic Data Structures: Size can change during execution, memory allocated at runtime. Examples: Linked Lists, Stacks, Queues.

6.1.2.3 - Primitive vs. Non-Primitive​

  • Primitive Data Structures: Basic data types like int, float, char, etc.
  • Non-Primitive Data Structures: Derived from primitive data structures. Examples: Arrays, Lists, Stacks, Queues, etc.

6.1.3 - Common Operations on Data Structures​

Most data structures support the following operations:

  1. Insertion: Adding a new element to the data structure.
  2. Deletion: Removing an element from the data structure.
  3. Traversal: Accessing each element exactly once for processing.
  4. Searching: Finding the location of an element within the data structure.
  5. Sorting: Arranging elements in a specific order (ascending or descending).
  6. Merging: Combining two data structures into one.

6.1.4 - Performance Analysis​

The performance of data structures is typically measured using Big O notation, which describes the upper bound of the time complexity in the worst case.

6.1.4.1 - Time Complexity​

Time complexity measures the amount of time an algorithm takes to complete as a function of the input size.

Common time complexities (from fastest to slowest):

  • O(1): Constant time
  • O(log n): Logarithmic time
  • O(n): Linear time
  • O(n log n): Log-linear time
  • O(n²): Quadratic time
  • O(2^n): Exponential time
  • O(n!): Factorial time

6.1.4.2 - Space Complexity​

Space complexity measures the amount of memory an algorithm uses as a function of the input size.

6.1.5 - Choosing the Right Data Structure​

Selecting the appropriate data structure depends on various factors:

  1. Nature of the Problem: Different problems require different data structures.
  2. Operations Required: Some data structures are optimized for specific operations.
  3. Memory Constraints: Some data structures use more memory than others.
  4. Performance Requirements: Time complexity considerations for critical operations.

Here's a quick reference for common operations and their time complexities for various data structures:

Data StructureAccessSearchInsertionDeletion
ArrayO(1)O(n)O(n)O(n)
Linked ListO(n)O(n)O(1)O(1)
StackO(n)O(n)O(1)O(1)
QueueO(n)O(n)O(1)O(1)
Hash TableN/AO(1)O(1)O(1)
Binary Search TreeO(log n)O(log n)O(log n)O(log n)
AVL TreeO(log n)O(log n)O(log n)O(log n)
B-TreeO(log n)O(log n)O(log n)O(log n)
Red-Black TreeO(log n)O(log n)O(log n)O(log n)
HeapN/AO(n)O(log n)O(log n)

6.1.6 - Data Structures in C#​

C# provides a rich set of built-in data structures through the .NET Framework's System.Collections and System.Collections.Generic namespaces.

6.1.6.1 - System.Collections​

The System.Collections namespace contains non-generic collection classes that store items as objects.

Examples:

  • ArrayList
  • Hashtable
  • Queue
  • Stack

6.1.6.2 - System.Collections.Generic​

The System.Collections.Generic namespace contains generic collection classes that provide type safety.

Examples:

  • List<T>
  • Dictionary<TKey, TValue>
  • Queue<T>
  • Stack<T>
  • LinkedList<T>
  • HashSet<T>

6.1.6.3 - System.Collections.Concurrent​

The System.Collections.Concurrent namespace provides thread-safe collection classes for use in multi-threaded applications.

Examples:

  • ConcurrentDictionary<TKey, TValue>
  • ConcurrentQueue<T>
  • ConcurrentStack<T>
  • ConcurrentBag<T>

6.1.7 - Custom Data Structures​

While C# provides many built-in data structures, sometimes you may need to create custom data structures for specific requirements. This can be done by:

  1. Extending Existing Data Structures: Inheriting from existing collection classes and adding custom functionality.
  2. Implementing Interfaces: Implementing interfaces like ICollection<T>, IList<T>, IDictionary<TKey, TValue>, etc.
  3. Building from Scratch: Creating entirely new data structures based on your specific needs.

6.1.8 - Memory Management Considerations​

When working with data structures in C#, it's important to consider memory management:

  1. Value Types vs. Reference Types: Value types are stored on the stack, while reference types are stored on the heap.
  2. Garbage Collection: C# has automatic garbage collection, but inefficient use of data structures can lead to memory pressure.
  3. Disposal of Resources: Implementing IDisposable for data structures that manage unmanaged resources.

6.1.9 - Data Structure Selection Guidelines​

Here are some guidelines for selecting the appropriate data structure:

  1. Use arrays when you need fast access to elements by index and the size is fixed.
  2. Use List<T> when you need a dynamic array with fast access by index.
  3. Use LinkedList<T> when you need frequent insertions and deletions.
  4. Use Dictionary<TKey, TValue> when you need fast lookups based on a key.
  5. Use HashSet<T> when you need to store unique elements and check for membership.
  6. Use Queue<T> when you need FIFO (First-In-First-Out) behavior.
  7. Use Stack<T> when you need LIFO (Last-In-First-Out) behavior.
  8. Use SortedList<TKey, TValue> or SortedDictionary<TKey, TValue> when you need a sorted collection.
  9. Use concurrent collections when you need thread-safe operations.

In the following sections, we'll explore each of these data structures in detail, discussing their implementations, use cases, and performance characteristics in C#.