6.2 - Arrays and Lists
Arrays and lists are fundamental data structures in C# that store collections of elements. While they serve similar purposes, they have different characteristics and use cases. This section explores arrays and lists in detail, including their implementations, operations, and performance considerations.
6.2.1 - Static vs. Dynamic Arrays
An array is a fixed-size, sequential collection of elements of the same type. It is the simplest and most efficient data structure for storing and accessing a collection of elements.
6.2.1.1 - Declaring and Initializing Arrays
There are several ways to declare and initialize arrays in C#:
// Declaration with size
int[] numbers = new int[5];
// Declaration with initialization
int[] numbers = new int[] { 1, 2, 3, 4, 5 };
// Shorthand initialization
int[] numbers = { 1, 2, 3, 4, 5 };
// Multi-dimensional array
int[,] matrix = new int[3, 3];
// Jagged array (array of arrays)
int[][] jaggedArray = new int[3][];
jaggedArray[0] = new int[] { 1, 2, 3 };
jaggedArray[1] = new int[] { 4, 5 };
jaggedArray[2] = new int[] { 6, 7, 8, 9 };
6.2.1.2 - Accessing Array Elements
Array elements are accessed using zero-based indexing:
int[] numbers = { 1, 2, 3, 4, 5 };
// Accessing elements
int firstElement = numbers[0]; // 1
int thirdElement = numbers[2]; // 3
// Modifying elements
numbers[1] = 10; // { 1, 10, 3, 4, 5 }
6.2.1.3 - Array Properties and Methods
Arrays in C# inherit from the System.Array class, which provides various properties and methods:
int[] numbers = { 1, 2, 3, 4, 5 };
// Properties
int length = numbers.Length; // 5
int rank = numbers.Rank; // 1 (number of dimensions)
// Methods
Array.Sort(numbers); // Sort the array
Array.Reverse(numbers); // Reverse the array
int index = Array.IndexOf(numbers, 3); // Find the index of an element
Array.Clear(numbers, 0, numbers.Length); // Clear the array
6.2.1.4 - Multi-dimensional Arrays
C# supports multi-dimensional arrays, which can be rectangular or jagged:
// Rectangular array (2D)
int[,] matrix = new int[3, 3] {
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 }
};
// Accessing elements in a 2D array
int element = matrix[1, 2]; // 6
// Jagged array (array of arrays)
int[][] jaggedArray = new int[3][];
jaggedArray[0] = new int[] { 1, 2, 3 };
jaggedArray[1] = new int[] { 4, 5 };
jaggedArray[2] = new int[] { 6, 7, 8, 9 };
// Accessing elements in a jagged array
int element = jaggedArray[2][1]; // 7
6.2.1.5 - Array Performance
Arrays offer the following performance characteristics:
- Access: O(1) - Constant time access to elements by index
- Search: O(n) - Linear time for unsorted arrays, O(log n) for sorted arrays using binary search
- Insertion: O(n) - Linear time, as elements may need to be shifted
- Deletion: O(n) - Linear time, as elements may need to be shifted
6.2.1.6 - Array Limitations
Arrays have several limitations:
- Fixed Size: Once created, the size of an array cannot be changed.
- Homogeneous Elements: All elements must be of the same type.
- Inefficient Insertions/Deletions: Inserting or deleting elements requires shifting other elements.
6.2.2 - List Manipulation with List<T>
Lists in C# are dynamic arrays that can grow or shrink in size. The most commonly used list type is List<T>, which is a generic collection that provides type safety.
6.2.2.1 - Declaring and Initializing Lists
// Declaration with no elements
List<int> numbers = new List<int>();
// Declaration with initial capacity
List<int> numbers = new List<int>(10);
// Declaration with initialization
List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
// Declaration from an existing collection
int[] array = { 1, 2, 3, 4, 5 };
List<int> numbers = new List<int>(array);
6.2.2.2 - List Operations
List<T> provides various methods for adding, removing, and manipulating elements:
List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
// Adding elements
numbers.Add(6); // { 1, 2, 3, 4, 5, 6 }
numbers.Insert(2, 10); // { 1, 2, 10, 3, 4, 5, 6 }
numbers.AddRange(new int[] { 7, 8, 9 }); // { 1, 2, 10, 3, 4, 5, 6, 7, 8, 9 }
// Removing elements
numbers.Remove(3); // { 1, 2, 10, 4, 5, 6, 7, 8, 9 }
numbers.RemoveAt(1); // { 1, 10, 4, 5, 6, 7, 8, 9 }
numbers.RemoveRange(2, 3); // { 1, 10, 7, 8, 9 }
numbers.Clear(); // {}
// Accessing elements
int element = numbers[2]; // Access by index
bool contains = numbers.Contains(5); // Check if an element exists
int index = numbers.IndexOf(5); // Find the index of an element
int lastIndex = numbers.LastIndexOf(5); // Find the last index of an element
// Other operations
numbers.Sort(); // Sort the list
numbers.Reverse(); // Reverse the list
List<int> subList = numbers.GetRange(1, 3); // Get a sublist
6.2.2.3 - List Properties
List<T> provides several properties:
List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
int count = numbers.Count; // Number of elements
int capacity = numbers.Capacity; // Current capacity
6.2.2.4 - List<T> Implementation
List<T> is implemented as a dynamic array that automatically resizes when needed:
- When a List<T> is created, it allocates an internal array with an initial capacity.
- As elements are added, if the count exceeds the capacity, the list automatically resizes by:
- Allocating a new, larger array (typically twice the size of the original)
- Copying all elements from the old array to the new array
- Replacing the old array with the new one
6.2.2.5 - List Performance
Lists offer the following performance characteristics:
- Access: O(1) - Constant time access to elements by index
- Search: O(n) - Linear time for unsorted lists, O(log n) for sorted lists using binary search
- Insertion/Deletion at the end: Amortized O(1) - Constant time on average
- Insertion/Deletion in the middle: O(n) - Linear time, as elements need to be shifted
6.2.2.6 - List vs. Array
Here's a comparison of List<T> and arrays:
| Feature | Array | List<T> |
|---|---|---|
| Size | Fixed | Dynamic |
| Memory Allocation | Contiguous | Contiguous (with resizing) |
| Type Safety | Yes | Yes (with generics) |
| Performance (Access) | O(1) | O(1) |
| Performance (Insert/Delete) | O(n) | O(1) at end, O(n) in middle |
| Memory Overhead | Minimal | Higher due to capacity management |
| Built-in Methods | Limited | Extensive |
6.2.3 - Performance Considerations
When working with arrays and lists, consider the following performance aspects:
6.2.3.1 - Memory Allocation
- Arrays: Arrays allocate a contiguous block of memory when created. The size is fixed, so memory usage is predictable.
- List<T>: Lists allocate an internal array with an initial capacity and resize when needed. This can lead to memory overhead if the capacity is much larger than the actual number of elements.
// Optimizing memory usage with List<T>
List<int> numbers = new List<int>(100); // Preallocate capacity for 100 elements
numbers.TrimExcess(); // Trim unused capacity
6.2.3.2 - Access Patterns
The way you access elements can significantly impact performance:
// Sequential access is cache-friendly
int[] array = new int[1000];
for (int i = 0; i < array.Length; i++)
{
array[i] = i; // Sequential access
}
// Random access can cause cache misses
Random random = new Random();
for (int i = 0; i < 1000; i++)
{
int index = random.Next(array.Length);
int value = array[index]; // Random access
}
6.2.3.3 - Resizing Operations
For List<T>, resizing operations can be expensive:
// Avoid frequent resizing
List<int> inefficient = new List<int>();
for (int i = 0; i < 10000; i++)
{
inefficient.Add(i); // May cause multiple resizes
}
// More efficient approach
List<int> efficient = new List<int>(10000);
for (int i = 0; i < 10000; i++)
{
efficient.Add(i); // No resizing needed
}
6.2.4 - Common Operations and Algorithms
Here are some common operations and algorithms used with arrays and lists:
6.2.4.1 - Linear Search
public static int LinearSearch<T>(List<T> list, T item)
{
for (int i = 0; i < list.Count; i++)
{
if (EqualityComparer<T>.Default.Equals(list[i], item))
return i;
}
return -1; // Item not found
}
6.2.4.2 - Binary Search (for sorted lists)
public static int BinarySearch<T>(List<T> list, T item) where T : IComparable<T>
{
int left = 0;
int right = list.Count - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
int comparison = list[mid].CompareTo(item);
if (comparison == 0)
return mid; // Item found
if (comparison < 0)
left = mid + 1; // Search in the right half
else
right = mid - 1; // Search in the left half
}
return -1; // Item not found
}
6.2.4.3 - Filtering
public static List<T> Filter<T>(List<T> list, Predicate<T> predicate)
{
List<T> result = new List<T>();
foreach (T item in list)
{
if (predicate(item))
result.Add(item);
}
return result;
}
// Usage
List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
List<int> evenNumbers = Filter(numbers, n => n % 2 == 0);
6.2.4.4 - Mapping
public static List<TResult> Map<T, TResult>(List<T> list, Func<T, TResult> mapper)
{
List<TResult> result = new List<TResult>(list.Count);
foreach (T item in list)
{
result.Add(mapper(item));
}
return result;
}
// Usage
List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };
List<int> squared = Map(numbers, n => n * n);
6.2.5 - LINQ with Lists
LINQ (Language Integrated Query) provides a powerful way to query and manipulate lists:
List<int> numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Filtering
var evenNumbers = numbers.Where(n => n % 2 == 0);
// Mapping
var squared = numbers.Select(n => n * n);
// Sorting
var sorted = numbers.OrderByDescending(n => n);
// Aggregation
int sum = numbers.Sum();
int max = numbers.Max();
double average = numbers.Average();
// Combining operations
var result = numbers
.Where(n => n % 2 == 0)
.Select(n => n * n)
.OrderBy(n => n)
.Take(3);
6.2.6 - Best Practices
Here are some best practices for working with arrays and lists in C#:
- Choose the Right Collection: Use arrays for fixed-size collections and List<T> for dynamic collections.
- Specify Initial Capacity: If you know the approximate size of a List<T> in advance, specify the initial capacity to avoid frequent resizing.
- Use Generic Collections: Prefer generic collections (List<T>) over non-generic ones (ArrayList) for type safety and performance.
- Avoid Unnecessary Resizing: Minimize operations that cause resizing, such as frequent insertions at the beginning or middle of a list.
- Use LINQ for Complex Operations: LINQ provides a concise and readable way to perform complex operations on collections.
- Consider Memory Usage: Be mindful of memory usage, especially with large collections.
- Use ReadOnlyCollection<T>: When passing a collection to a method that should not modify it, consider using ReadOnlyCollection<T>.
6.2.7 - Real-World Applications
Arrays and lists are used in various real-world applications:
- Data Processing: Storing and processing large datasets.
- User Interfaces: Managing collections of UI elements.
- Game Development: Storing game objects, player data, etc.
- Financial Applications: Managing transactions, portfolios, etc.
- Web Applications: Handling collections of users, products, orders, etc.
In the next section, we'll explore stacks and queues, which are specialized data structures with specific access patterns.