Book Image

C# Data Structures and Algorithms - Second Edition

By : Marcin Jamro
Book Image

C# Data Structures and Algorithms - Second Edition

By: Marcin Jamro

Overview of this book

Building your own applications is exciting but challenging, especially when tackling complex problems tied to advanced data structures and algorithms. This endeavor demands profound knowledge of the programming language as well as data structures and algorithms – precisely what this book offers to C# developers. Starting with an introduction to algorithms, this book gradually immerses you in the world of arrays, lists, stacks, queues, dictionaries, and sets. Real-world examples, enriched with code snippets and illustrations, provide a practical understanding of these concepts. You’ll also learn how to sort arrays using various algorithms, setting a solid foundation for your programming expertise. As you progress through the book, you’ll venture into more complex data structures – trees and graphs – and discover algorithms for tasks such as determining the shortest path in a graph before advancing to see various algorithms in action, such as solving Sudoku. By the end of the book, you’ll have learned how to use the C# language to build algorithmic components that are not only easy to understand and debug but also seamlessly applicable in various applications, spanning web and mobile platforms.
Table of Contents (13 chapters)

Preface

Hello, I am Marcin!

It is so nice to meet you and to invite you to an amazing journey through various data structures and algorithms presented in this book. As you could already know, developing applications is certainly something exciting to work on, but it is also challenging, especially if you need to solve some complex problems. In such cases, you often need to take care of performance to ensure that the solution will work smoothly on devices with limited resources. Such a task could be really difficult and could require significant knowledge regarding not only the programming language but also data structures and algorithms. However, have you ever thought profoundly about them and their impact on the performance of your applications? If not, it is high time to take a look at this topic, and this book is a great place to start!

Did you know that replacing even one data structure with another could cause the performance results to increase hundreds of times or even more? Does it sound impossible? Maybe, but it is true! As an example, I would like to tell you a short story about one of the projects in which I was involved some time ago. The aim was to optimize the algorithm to find connections between blocks on a graphical diagram. Such connections should be automatically recalculated, refreshed, and redrawn as soon as any block has moved in the diagram. Of course, connections cannot go through blocks and cannot overlap other lines, and the number of crossings and direction changes should be limited. Depending on the size and the complexity of the diagram, the performance results differ significantly. However, while conducting tests, we received results in the range of 1 ms to almost 800 ms for the same test case. What was perhaps the most surprising aspect is that such a huge improvement was reached mainly by... changing the data structures of two sets.

Are you interested in knowing the influence of choosing a suitable data structure on the performance of your application? Do you want to know how you can increase the quality and performance of your solution by choosing the right accompanying algorithm? Are you curious about real-world scenarios where various data structures can be applied, as well as which algorithms could be used to solve some common problems? Unfortunately, the answer to such questions is not simple. However, within this book, you will find a lot of information about data structures and algorithms, presented in the context of the C# programming language, with many examples, code snippets, illustrations, and detailed explanations. Such content could help you to answer the aforementioned questions while developing the next great solutions, which could be used by many people all over the world! Are you ready to start your adventure with data structures and algorithms? If so, welcome on board of this book!

The book covers many data structures, starting with simple ones, namely arrays and a few of their variants, as representatives of random access data structures. Then, lists are introduced, together with their sorted, linked, and circular versions. The book also explains limited access data structures, based on stacks and queues, including a priority and a circular queue. Following this, we introduce you to the dictionary data structure, which allows you to map keys to values and perform fast lookup. The sorted variant of a dictionary is supported, as well. If you want to benefit from high-performance, set-related operations, you can use another data structure, namely a hash set. One of the most powerful constructs is a tree, which exists in many variants, including a binary tree, a binary search tree, a self-balancing tree, a trie, and a heap. The last data structure we analyze is a graph, supported by many interesting algorithmic topics, such as graph traversal, minimum spanning tree, node coloring, and finding the shortest path.

Arrays, lists, stacks, queues, dictionaries, hash sets, trees, tries, heaps, and graphs, as well as accompanying algorithms – a broad range of subjects await you on the next pages! Let’s start the adventure and take the first step toward your mastery of data structures and algorithms, which hopefully will have a positive effect on your projects and on your career as a software developer!