This content originally appeared on DEV Community and was authored by Firdavs Kasymov
If you are a beginner or new to computer programming, some of the first things you will have to learn include data structures and algorithms. Data structures and algorithms are basics in programming that every developer and software engineer needs to know. Just like you learnt algebra in your first mathematics lessons, learning data structures and algorithms is crucial if you want to become a good programmer.
In today’s article, article, we will share with you everything you need to know about these two topics. Let’s jump right in!
What are data structures?
Data structures refer to the programmatic way of storing data so that it can be accessed and used effectively. It is through data structures that programmers are able to reference and manipulate data depending on the objective of the program being written. Every application uses various types of data structures in one way or another.
Having knowledge about the different data structures will help you learn how each of them works so that you choose the right one depending on the problem at hand.
Types of data structures
There are several types of data structures, but the ones every programmer needs to know are about six. These include the following;
Linear data structures
- Arrays An array is the simplest type of data structure that contains elements of the same data type. That means one array cannot contain integers and strings at the same. It has to be only one data type. Arrays are also used to create more complex data types that I am about to share in the next paragraphs. Items in an array are indexed in order starting from 0.
- Stacks This is the data structure type where items are stored using the LIFO (Last in First Out) principle. This simply means the items put last are removed first. Just like a pile of papers, the papers you put last are the ones will have to remove first.
- Linked Lists Type of data structure where a sequence of elements are arranged in linear order and are all connected together. That means you have to access these items in order. Random access is not possible.
- Queues This type is just like stacks, but instead of using the LIFO structure, it uses the FIFO (First In First Out) structure. That means the items added first are removed first and vice-versa.
Non-linear data structures
- Graphs This is the type of data structure that consists of nodes that are usually referred to as vertices. Each vertex is connected to other vertices through edges to form a structure.
- Tree This is another type of non-linear data structure which also consists of a collection of vertices and edges. Unlike in graphs, there can only be one edge between two vertices in tree data structures.
What is an algorithm?
In programming, an algorithm refers to a set of instructions that are written to accomplish a predefined task. An algorithm is not a complete program, but simply the core logic of the program. Algorithms are expressed either as informal high-level descriptions as pseudocode or using a flowchart.
The performance of an algorithm is measured based on two parameters; time complexity and space complexity. An efficient algorithm takes less time to execute and also takes up less space in computer RAM. Algorithms with more lines of code usually take up more RAM than those with fewer lines. As a programmer, your aim should be to create algorithms that take less time to execute and also take up less RAM.
Properties of an algorithm
Any algorithm must have the following properties;
- Input: There should be zero or more inputs supplied to the algorithm
- Output: The algorithm should bear at least one output
- Definiteness: Every step of the algorithm needs to be clearly defined
- Finiteness: Every algorithm should have a finite number of steps
- Correctness: Every step of an algorithm must produce correct output
Types of Algorithms
There are various types of algorithms, but there are 6 main ones that every programmer needs to know;
- Recursive Algorithm This refers to the type of algorithm that repeatedly calls itself until the problem is solved. A certain condition in the algorithm has to be met for the execution to stop.
- Divide and conquer algorithms This is the type of algorithm where the algorithm to solve a certain problem is divided into two parts; the first part divides the problem into sub-problems of the same type. In the second part, these smaller subproblems are solved and then added together to form a solution for the overall problem.
- Dynamic programming algorithms This is the type of algorithm that works by recalling the results from the previous run and using them to find the next solution. With these algorithms, a problem is also broken down into small problems that are solved once and their solutions stored for future use. Dynamic programming algorithms are usually used to solve optimization problems.
- Greedy algorithm This refers to the type of problem-solving strategy that involves finding a locally optimum solution at each stage with the hope of using these solutions to find a globally optimum solution. This type of algorithm is normally used to solve optimization problems that require the maximum or minimum optimum results. Greedy algorithms are also pretty easy to implement. Some of the popular applications of greedy algorithms include; CPU Scheduling algorithms, Minimum spanning trees, Dijkstra shortest path algorithm, Fit algorithm in memory management, and Travelling salesman problem.
- Brute force algorithms These are algorithms that involve interacting with all the possible solutions to search for one or more solutions that solve a certain function. You can think of this as trying all the possible combinations of numbers to find the passcode of a certain device. This type of algorithm is usually used when there is no other algorithm that can be used to speed up the process of solving a certain problem, so one has to check all the possible solutions to figure out which one solves the problem.
- Backtracking algorithms These are algorithms where a problem is solved using an incremental approach. So, if a solution is not found at one stage, it is removed and we backtrack to find another solution. These algorithms are usually used to find a solution to decision problems.
How to boost the performance of a program by using the correct algorithms?
As you will see in your programming journey, some of the problems can be solved using any of the algorithm types we have just shared. However, there will be a difference in performance depending on the type of algorithm you choose to use. Let’s look at some of the factors you need to look at while choosing which algorithm to use.
- Running Time Time complexity is one of the key factors you need to consider while choosing the appropriate algorithm to use. With all other factors constant, it is always best to choose an algorithm that solves the problem in less time. The time difference becomes significant when you have to use multiple algorithms to solve one big problem at hand.
- Memory consumption The applications where these algorithms are implemented work with limited computing resources. That is why it is important to choose an algorithm type that takes up less memory space. Memory space usually depends on the size of input data needed for the algorithm to solve the problem at hand.
- Parallel processing If the problem requires parallel processing for faster execution, then it is ideal to choose a type of algorithm that involves dividing the problem into smaller subproblems that can be solved independently and the solutions later combined to form the overall solution for the bigger problem. In such a case, divide and conquer algorithms are always the best choice.
- Accuracy requirements You need to first look at the problem a figure out how accurate the output of an algorithm needs to be to solve the problem at hand. You should then choose the fastest algorithm that yields a solution within the acceptable range of accuracy.
Learning materials
A curated list of awesome places to learn and/or practice agorithms:
https://github.com/tayllan/awesome-algorithmsTo practice your knowledge about algorithms and data structures you can use the below resources:
https://www.hackerrank.com
https://leetcode.com/
Final thoughts
There is a lot more you can learn about data structures and algorithms. Use the basics we have shared as a stepping stone to learning more about these two topics. You will have to dive deeper into the different types of data structures to figure out when to use which and the impact your choice will have on the performance of your program.
There are also more specific data structures and algorithm types that we haven’t covered in this article. However, the ones we have looked at are the common types that you will often encounter in your programming journey.
This content originally appeared on DEV Community and was authored by Firdavs Kasymov
Firdavs Kasymov | Sciencx (2022-05-07T20:30:20+00:00) Data Structures And Algorithms. Retrieved from https://www.scien.cx/2022/05/07/data-structures-and-algorithms/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.