{ "cells": [ { "cell_type": "markdown", "id": "21ab0011", "metadata": {}, "source": [ "# Introduction\n", "\n", "The term **data structure** could mean any structure (such as a list, array, tree,\n", "dictionary, etc) that stores data. By definition, you can say that a class as\n", "simple as an employee object storing employee-specific data is a structure.\n", "Academically, however, it is common to more focus on data structure as a data\n", "organization and storage format (hash, array, etc) that is usually chosen for\n", "efficient access to data. A data structure, therefore, can refer to a collection of data\n", "values, the relationship among them, and the functions or operations that can\n", "be applied to them. [^data-structure-wiki]\n", "\n", "On the other hand, when we talk about data structures, we are often referring to commonly\n", "implemented structured sets of data, and they are sometimes called \"collections\". Collections\n", "are sets of data including lists, dictionaries, trees, etc. From the\n", "implementation perspective, a collection is an `abstract data type` that is\n", "a grouping of items of often the same data type such as string or integer.\n", "\n", "In .NET, the namespace (and hence types) that store the sets of data is System.Collections.\n", "Therefore in .NET we tend to use the term **collections** for any of the data structures\n", "used to store sets of data implemented in the .NET platform, including arrays. [^data-structure-vs-collection]\n", "\n", "From the implementation perspective, implemented data structure are called collections: [^microsoft-collections-and-data-structure]\n", "\n", "> Similar data can often be handled more efficiently when stored and\n", "> manipulated as a collection. You can use the System.Array class or the classes\n", "> in the System.Collections, System.Collections.Generic, System.Collections.Concurrent,\n", "> and System.Collections.Immutable namespaces to add, remove, and modify either\n", "> individual elements or a range of elements in a collection.\n", "\n" ] }, { "cell_type": "markdown", "id": "09248476", "metadata": {}, "source": "## C# Collections\n\nAccording to the C# language reference, [^csharp-collections]\n\n> The .NET runtime provides many collection types that store and manage groups of\n> related objects. Some of the collection types, such as System.Array, System.Span\\,\n> and System.Memory\\ are recognized in the C# language. In addition, interfaces\n> like System.Collections.Generic.IEnumerable\\ are recognized in the language for\n> enumerating the elements of a collection.\n\nCollection types represent different ways to collect data, such as hash tables, queues,\nstacks, bags, dictionaries, and lists. Commonly used collection types may be grouped\ninto two groups:\n\n- Indexable collections: such as List that base on the List\\ class.\n- Key/value pair collections: such as Dictionary that bases on the Dictionary\\ class.\n\nIn addition to indexable vs key/value, collections are also grouped into two types in C#: non-generic\ncollections and generic collections: [#generic-non_generic-collections]\n\n- Generic Collections: In the System.Collections.Generic namespace, collection classes like\n List\\, Dictionary\\, Queue\\, Stack\\, and Hashset\\.\n- Non-generic Collections: In the System.Collections namespace, the non-generic collection\n includes non-generic collection types such as ArrayList, SortedList, Stack, Queue, Hashtable, and BitArray.\n\nCollections vary in how they store, sort, and compare elements, and how they\nperform searches. As for how to choose among the collections to use, the .NET\nfundamentals documentation offers a general guideline by considering several aspects.\n[^selecting-collection-class]" }, { "cell_type": "markdown", "id": "7f9c4316", "metadata": {}, "source": "## Commonly Used Collection types\n\nIn C#, collection types represent different ways to collect data, such as hash tables,\nqueues, stacks, bags, dictionaries, and lists. All collections are based on the\n`ICollection` or `ICollection` **interfaces**, either directly or indirectly.\n`IList` and `IDictionary` and their generic counterparts all derive from these\ntwo interfaces.\n\nIn collections based on IList or directly on ICollection, every element contains\nonly a value. These types include: [^commonly-used-types]\n\n- **Array**\n- ArrayList\n- **List\\**\n- Queue\n- ConcurrentQueue\\\n- Stack\n- ConcurrentStack\\\n- LinkedList\\\n\nIn collections based on the `IDictionary` interface, every element contains both\na key and a value. These types include:\n\n- Hashtable\n- SortedList\n- SortedList\\\n- **Dictionary\\**\n- ConcurrentDictionary\\\n\nWhile these collection types (classes) are implemented in C#, you should note that\nthey are based on common data structures: [^data-structure-wiki]\n\n- Array: An array is a number of elements in a specific order, typically all of\n the same type.\n- Linked List: A linked list is a linear collection of data elements of any type,\n called nodes, where each node has itself a value, and points to the next node in\n the linked list.\n- Record: A record (also called tuple or struct) is an aggregate data structure.\n A record is a value that contains other values, typically in fixed number and\n sequence and typically indexed by names.\n- Hash Tables: Hash tables, also known as hash maps, are data structures that provide\n fast retrieval of values based on keys. They use a hashing function to map keys\n to indexes in an array, allowing for constant-time access in the average case.\n- Graphs: Graphs are collections of nodes connected by edges, representing\n relationships between entities.\n- Stacks and Queues: Stacks and queues are abstract data types that can be implemented\n using arrays or linked lists. A stack has two primary operations: push\n (adds an element to the top of the stack) and pop (removes the topmost element from\n the stack), that follow the Last In, First Out (LIFO) principle. Queues have two\n main operations: enqueue (adds an element to the rear of the queue) and dequeue\n (removes an element from the front of the queue) that follow the First In, First\n Out (FIFO) principle.\n- Trees: Trees represent a hierarchical organization of elements. A tree consists\n of nodes connected by edges, with one node being the root and all other nodes\n forming subtrees." }, { "cell_type": "markdown", "id": "592efa0d", "metadata": {}, "source": "## Collection Examples\n\nThe following examples are consolidated from the previous standalone section." }, { "cell_type": "markdown", "id": "a30d5f83", "metadata": {}, "source": "## Arrays\n\nIn C#, arrays are among the most fundamental and basic data structures. They offer a\nstraightforward method for storing a sequential collection of pieces of the same\nkind in a given size. Since arrays are the basis for many other intricate data\nstructures and algorithms, it is imperative that you understand them as discussed\nin Chapter 8. Basic operations and examples with arrays include:\n\n- Declaring an array: int[] numbers = new int[5];\n- Initializing an array: int[] numbers = { 1, 2, 3, 4, 5 };\n- Accessing array elements: numbers[0] ///// 1\n- Modifying elements: numbers[2] = 10; // Modifies the third element to be 10\n- The Length property: The Length property provides the number of elements in the array::\n numbers.Length;\n- Iterating through an array:" }, { "cell_type": "code", "execution_count": null, "id": "04a1d8e3", "metadata": {}, "outputs": [], "source": [ "%%csharp\n", "for (int i = 0; i < numbers.Length; i++) // Using for loop\n", "{\n", " Console.WriteLine(numbers[i]);\n", "}\n", "foreach (int num in numbers) // Using foreach loop\n", "{\n", " Console.WriteLine(num);\n", "}" ] }, { "cell_type": "markdown", "id": "1975f309", "metadata": {}, "source": "## Stacks\n\nStacks are a fundamental data structure in computer science that follows the\nLast In, First Out (**LIFO**) principle. In C#, the Stack\\ class, found\nin the System.Collections.Generic namespace, provides a collection that allows\nadding and removing elements in a `last-in-first-out` manner.\n\n- To **declare** a stack using the Stack\\ class:\n\n" }, { "cell_type": "code", "execution_count": null, "id": "50d19ebc", "metadata": {}, "outputs": [], "source": [ " Stack stack = new Stack();\n" ] }, { "cell_type": "markdown", "id": "f77cb4f5", "metadata": {}, "source": [ "\n", "- To `push` to **add elements** to the `top` of the stack:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "8a9675d2", "metadata": {}, "outputs": [], "source": [ " stack.Push(1);\n", " stack.Push(2);\n", " stack.Push(3);\n" ] }, { "cell_type": "markdown", "id": "065b5219", "metadata": {}, "source": [ "\n", "After the operations, the stack will contain {3, 2, 1} as shown below:" ] }, { "cell_type": "code", "execution_count": null, "id": "a067db4b", "metadata": {}, "outputs": [], "source": [ "Stack stack = new Stack();\n", "stack.Push(1);\n", " stack.Push(2);\n", " stack.Push(3);\n", "stack" ] }, { "cell_type": "markdown", "id": "3888caaf", "metadata": {}, "source": [ "- The `Pop()` method is used to remove and return the top element from the stack\n", " (remember stacks are `first-in-last-out`):" ] }, { "cell_type": "code", "execution_count": null, "id": "e735daf3", "metadata": {}, "outputs": [], "source": [ "stack\n", "stack.Pop()\n", "stack" ] }, { "cell_type": "markdown", "id": "db6fef20", "metadata": {}, "source": [ "- The `Peek` method is used to view the top element of the stack without removing it:" ] }, { "cell_type": "code", "execution_count": null, "id": "1c045b75", "metadata": {}, "outputs": [], "source": [ "stack\n", "stack.Peek()" ] }, { "cell_type": "markdown", "id": "2203288a", "metadata": {}, "source": [ "- Also, you can use the `Count` method to check if a stack is empty:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "5b887186", "metadata": {}, "outputs": [], "source": [ " if (stack.Count == 0)\n", " {\n", " Console.WriteLine(\"Stack is empty\");\n", " }\n" ] }, { "cell_type": "markdown", "id": "ed588332", "metadata": {}, "source": "## Queues\n\nQueues are another fundamental data structure commonly used in computer science\nthat follows the **First In, First Out** (`FIFO`) principle. In C#, the Queue\\ class,\nfound in the System.Collections.Generic namespace, provides a collection that\nallows adding and removing elements in a first-in-first-out manner. [#professional]\n\n- To declare a queue using the Queue\\ class:\n\n" }, { "cell_type": "code", "execution_count": null, "id": "3a611c8e", "metadata": {}, "outputs": [], "source": [ " Queue queue = new Queue();\n" ] }, { "cell_type": "markdown", "id": "231c1d4b", "metadata": {}, "source": [ "\n", "- To add elements to a queue collection, you use `Enqueue` method:\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "64c83514", "metadata": {}, "outputs": [], "source": [ " queue.Enqueue(\"Task 1\");\n", " queue.Enqueue(\"Task 2\");\n", " queue.Enqueue(\"Task 3\");\n" ] }, { "cell_type": "markdown", "id": "dd2cdca5", "metadata": {}, "source": [ "\n", "as see in csharprepl:" ] }, { "cell_type": "code", "execution_count": null, "id": "b357f1c3", "metadata": {}, "outputs": [], "source": [ "Queue queue = new Queue();\n", "queue.Enqueue(\"Task 1\");\n", " queue.Enqueue(\"Task 2\");\n", " queue.Enqueue(\"Task 3\");\n", "queue" ] }, { "cell_type": "markdown", "id": "70978c03", "metadata": {}, "source": [ "- In contrast to `Enqueue`, the `Dequeue` method is used to remove and return the\n", " front element from the queue:" ] }, { "cell_type": "code", "execution_count": null, "id": "bd1ab5e6", "metadata": {}, "outputs": [], "source": [ "queue\n", "queue.Dequeue()\n", "queue" ] }, { "cell_type": "markdown", "id": "b496826f", "metadata": {}, "source": [ "- Also, to check if a queue is empty, use the `Count()` method:" ] }, { "cell_type": "code", "execution_count": null, "id": "5fc423b7", "metadata": {}, "outputs": [], "source": [ " if (queue.Count == 0)\n", " {\n", " Console.WriteLine(\"Queue is empty\");\n", " }\n" ] }, { "cell_type": "markdown", "id": "tup00", "metadata": {}, "source": "## Tuples\n\nA **tuple** groups multiple values without defining a class. It is lightweight and ideal for returning multiple values from a method, or for short-lived paired data that does not need its own type.\n\n```csharp\n(Type1, Type2) myTuple = (value1, value2);\n```", "outputs": [] }, { "cell_type": "markdown", "id": "tup01", "metadata": {}, "source": "### Creating Tuples", "outputs": [] }, { "cell_type": "code", "id": "tup02", "metadata": {}, "source": "// Unnamed fields \u2014 accessed as .Item1, .Item2\nvar point = (3, 7);\nConsole.WriteLine($\"x={point.Item1}, y={point.Item2}\");\n\n// Named fields \u2014 much clearer\nvar person = (Name: \"Alice\", Age: 30);\nConsole.WriteLine($\"{person.Name} is {person.Age}\");", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "id": "tup03", "metadata": {}, "source": "### Returning Multiple Values\n\nBefore tuples you needed `out` parameters or a custom class. Now:", "outputs": [] }, { "cell_type": "code", "id": "tup04", "metadata": {}, "source": "static (int Min, int Max) MinMax(int[] arr)\n{\n int min = arr[0], max = arr[0];\n foreach (int n in arr)\n {\n if (n < min) min = n;\n if (n > max) max = n;\n }\n return (min, max);\n}\n\nint[] data = { 5, 2, 8, 1, 9, 3 };\nvar result = MinMax(data);\nConsole.WriteLine($\"Min={result.Min}, Max={result.Max}\"); // Min=1, Max=9", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "id": "tup05", "metadata": {}, "source": "### Destructuring\n\nUnpack a tuple into separate variables in one statement.", "outputs": [] }, { "cell_type": "code", "id": "tup06", "metadata": {}, "source": "var (min, max) = MinMax(new[] { 5, 2, 8, 1, 9, 3 });\nConsole.WriteLine($\"Min={min}, Max={max}\"); // Min=1, Max=9\n\n// Discard values you don't need with _\nvar (name, _) = (\"Alice\", 30);\nConsole.WriteLine(name); // Alice", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "id": "tup07", "metadata": {}, "source": "### Tuples in Collections\n\nUseful for paired data without a dedicated class.", "outputs": [] }, { "cell_type": "code", "id": "tup08", "metadata": {}, "source": "var students = new List<(string Name, int Score)>\n{\n (\"Alice\", 88),\n (\"Bob\", 72),\n (\"Carol\", 95),\n};\n\nforeach (var (name, score) in students)\n Console.WriteLine($\"{name}: {score}\");\n\n// Sort by score descending\nvar top = students.OrderByDescending(s => s.Score).First();\nConsole.WriteLine($\"Top student: {top.Name} ({top.Score})\");", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "id": "tup09", "metadata": {}, "source": "### When to Use Tuples vs. Classes\n\n| Use Tuples when | Use a Class when |\n|---|---|\n| Returning 2\u20133 related values | Data has behavior (methods) |\n| Short-lived, internal use | Shared across the codebase |\n| Clarity from named fields | Need inheritance or interfaces |", "outputs": [] }, { "cell_type": "markdown", "id": "189db583", "metadata": {}, "source": [ "```{rubric} Footnotes\n", "```\n", "\n", "[^data-structure-wiki]: See, e.g., the Data structure [Wikipedia entry](https://en.wikipedia.org/wiki/Data_structure).\n", "\n", "[^data-structure-vs-collection]: See a Q&A discussion at [Microsoft](https://learn.microsoft.com/en-us/answers/questions/1522979/difference-between-data-structure-and-collection-i)\n", "\n", "[^microsoft-collections-and-data-structure]: In the .NET fundamentals documentation, the term \"data structures\" only appears in the article title [Collections and Data Structure](https://learn.microsoft.com/en-us/dotnet/standard/collections/)\n", "\n", "[^csharp-collections]: See C# language reference: [Collections](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/builtin-types/collections)\n", "\n", "[^selecting-collection-class]: .NET fundamentals documentation: [Selecting a Collection Class](https://learn.microsoft.com/en-us/dotnet/standard/collections/selecting-a-collection-class)\n", "\n", "[^commonly-used-types]: .NET fundamentals documentation: [Commonly used collection types](https://learn.microsoft.com/en-us/dotnet/standard/collections/commonly-used-collection-types)\n", "\n", "[^generic-non-generic-collections]: See [C# Generic & Non-generic Collections](https://www.tutorialsteacher.com/csharp/csharp-collection#:~:text=C%23%20includes%20specialized%20classes%20that,generic%20collections%20and%20generic%20collections.)\n", "List/Dictionary implementation details are covered in Chapter 9 (Collections).\n" ] }, { "cell_type": "markdown", "id": "859ec770", "metadata": {}, "source": [] } ], "metadata": { "jupytext": { "cell_metadata_filter": "-all", "main_language": "python", "notebook_metadata_filter": "-all" }, "language_info": { "name": "csharp" } }, "nbformat": 4, "nbformat_minor": 5 }