Data structures are one of the most important concepts in computer science, because, next to algorithms, they have the biggest influence over the time and space complexity of a program. Programmers need to understand the fundamentals of data structures when they’re writing software to ensure the most efficient performance or to balance memory constraints with performance costs, according to C Plus Plus.com. Computer science students usually take two semesters of courses on data structures in their second and third years, and to have a good, working understanding of data structures, it’s necessary to know an equal amount about data structures, algorithms and time and space complexity.
Choosing the Right Data Structures
In certain circumstances, a program that stores a list of objects in memory can achieve better performance by storing them in a binary search tree rather than a linked list or array. In other circumstances, the opposite is true. The reason is that a binary search tree allows you to find and insert objects in logarithmic time, while linear time is required to search a linked list or to insert objects into an array. On the other hand, because the print function for all three data structures requires O(n), or linear, time, it makes sense to use an array when you know the array indexes and can get objects in O(1), or constant, time.
Big O notation is a way of putting functions into categories based on their performance or space costs. The function inside parentheses in big O notation is a generalization of the time complexity of a category of functions as n approaches infinity. For example, the function y = 2n is O(n), because, as n grows, the constant term, 2, becomes insignificant. Likewise, the function y = 2n^2 + n is O(n^2), or polynomial, because, as n approaches infinity, the constant and lower-order terms are dwarfed by the most significant term, n^2. The most significant term always cancels out the lower-order terms, and this fact is why functions are put into categories.
Uses of Data Structures
Different programs call for different data structures, and depending on what you need to do, you may need to use stacks, dequeues, arrays, hash maps, linked lists or trees. Stacks are useful when you need to read in values but you don’t know how many values there are going to be. When you’re reading values in from a file, you can use a stack to store them temporarily so that you can count them and allocate space for them in memory. Stacks are also used by compilers to store function calls and to manage recursion because they always store the most recent value on top.
This fact is useful when a function calls another function that calls another function — a typical scenario — so that popping the last value off the top of the stack reveals the previous function call. The number one goal in programming is to choose the data structures and algorithms with the lowest time complexity, and sometimes you have to be inventive and rearrange your program to improve its performance.
Related Resource: Object Oriented Programming
As software becomes more and more important, understanding computer science concepts is an increasingly useful skill. These concepts form a branch of discrete mathematics, and they can all be proven by pure math without experimentation. To get a complete understanding of data structures and algorithms, it’s usually necessary to take several college courses.