Data Structures: Arrays Flashcards
Data structure is a way of organizing and storing data so that it can be accessed and modified efficiently. Each has its own ways of organizing data, with its specific strengths and use cases.
Data structures can be categorized into linear and non-linear data structures, hash data structures, or graph
data structures.
The terms static and dynamic data structures refer how memory is allocated and managed within these structures.
Name all data structures within C# and describe static and dynamic.
Data Structure Type Key Characteristics Use Case
Array Linear Fixed size, indexed access Storing data when size is known ahead of time
List<T> Linear (Generic) Dynamic size, indexed access Storing dynamic collections with flexible size</T>
Dictionary<TKey, TValue> Associative (Key-Value) Fast lookups, unique keys, unordered Mapping IDs to names, or any key-value pair mapping
Queue<T> Linear (FIFO) First In, First Out order Task processing, job scheduling</T>
Stack<T> Linear (LIFO) Last In, First Out order Undo functionality, recursion</T>
LinkedList<T> Linear (Doubly Linked) Fast insertions/deletions at both ends Inserting/removing elements in the middle of a list</T>
HashSet<T> Unordered (Set) No duplicates, efficient membership checking Storing unique elements, set operations</T>
SortedList<TKey, TValue> Associative (Key-Value) Sorted by key, fast lookups Storing sorted key-value pairs
PriorityQueue<T, TPriority> Queue with Priority Process items based on priority Task scheduling with different priorities
Static Data Structures:
- Memory Allocation: The memory for static data structures is allocated at compile time, meaning their size is fixed and cannot be changed during the program’s execution.
- Size: The size of the structure must be known in advance and cannot be altered once it is set.
- Efficiency: They can be faster because there is no overhead for resizing or reallocation, as memory is pre-allocated.
- Examples:
-Arrays: In most programming languages, arrays have a fixed size once they are defined.
-Structures (structs) in C (when defined with fixed size).
Advantages:
- Faster access and less overhead for memory management.
- Simplicity in implementation.
Disadvantages:
- Waste of memory if the allocated size is too large.
- Inflexibility as the size cannot be adjusted dynamically.
Dynamic Data Structures
- Memory Allocation: The memory for dynamic data structures is allocated at runtime, meaning they can grow or shrink in size during program execution.
- Size: The size can be adjusted during the program’s execution, and memory is allocated and freed as needed.
- Efficiency: These structures may have more overhead due to the need for memory management, resizing, and pointer handling.
- Examples:
- Linked Lists: Memory for each node is allocated dynamically.
- Stacks/Queues (implemented with dynamic arrays or linked lists).
- Trees (such as Binary Search Trees, AVL Trees).
Advantages:
- More flexible as they can grow or shrink according to the needs of the program.
- More efficient use of memory when the exact size is unknown or changes frequently.
Disadvantages:
- Slower due to overhead of memory allocation and deallocation.
- More complex to implement due to the need to manage memory and pointers.
In C#, an array is a collection of elements of the same type stored in contiguous memory locations. Arrays are widely used when you need to store a fixed-size sequence of elements that are all of the same type.
Declare an Array.
Using the new keyword: This creates an array of a specified size.
int[] numbers = new int[5]; // Array of 5 integers
int[] numbers = new int[5] {1,2,3,4,5};
Array with initialization values: You can initialize the array with values at the time of declaration.
int[] numbers = {1, 2, 3, 4, 5};
Using Array class: You can also use the Array class to create and manage arrays.
int[] numbers = Array.CreateInstance(typeof(int), 5) as int[];
How would you access and modify an array?
Accessing
int[] numbers = {10, 20, 30, 40, 50};
Console.WriteLine(numbers[0]); // Output: 10
Console.WriteLine(numbers[3]); // Output: 40
Modifying
numbers[2] = 100; // Changing the value at index 2 to 100
Console.WriteLine(numbers[2]); // Output: 100
How would you get a Length of an array?
int length = numbers.Length;
Console.WriteLine(length); // Output: 5
How would you iterate through a loop?
for (int i = 0; i < numbers.Length; i++)
{
Console.WriteLine(numbers[i]);
}
or
foreach (int num in numbers)
{
Console.WriteLine(num);
}
Common Array Methods:
Array.Sort(): Sorts the array in ascending order.
Array.Sort(numbers);
Array.Reverse(): Reverses the array.
Array.Reverse(numbers);
Array.Copy(): Copies elements from one array to another.
int[] copy = new int[5];
Array.Copy(numbers, copy, 5);
Array.Clear(): Clears (sets to default values) elements in the array.
Array.Clear(numbers, 2, 3); // Clears elements from index 2 to 4
Multidimensional Arrays & Jagged Arrays
// 2D Arrays
int[,] number = {{1,2,3},{4,5,6}};
// Accessing ...
// Column 0 Column 1 Column 2
// row 0 1 2 3
// row 1 4 5 6
//[row, column]
int firstNum = number[0,0];
Console.WriteLine(firstNum);
foreach (int i in number)
{
Console.WriteLine(i);
}
Console.WriteLine("");
for (int i = 0; i < number.GetLength(0); i++)
{
for (int j = 0; j < number.GetLength(1); j++)
{
Console.WriteLine(number[i,j]);
}
}
// 3D Arrays
int[,,] ThreeDNumber = {{{1,1,1}, {2,2,2}}, {{1,2,2}, {2,1,1}}};
// Jagged Arrays (Array of an Array)
int[][] jagarr = {new int[] {1,2,3,4,5}, new int[] {6,7,8,9,10}};
for (int i = 0; i < jagarr.Length; i++)
{
for (int j = 0; j < jagarr[i].Length; j++)
{
Console.WriteLine(jagarr[i][j] + " ");
}
}
Arrays as an Argument in Methods:
public void PrintArray(int[] arr)
{
foreach (int num in arr)
{
Console.WriteLine(num);
}
}
int[] numbers = {1, 2, 3, 4};
PrintArray(numbers);
Array Limits:
- Fixed Size: Once an array is created in C#, its size cannot be changed (i.e., you cannot add or remove elements).
- Efficiency: Arrays can be inefficient in certain situations where the data size is frequently changing, so List<T> or other dynamic structures might be preferred in such cases</T>
