In this tutorial, we’ll have a general overview of data structures. It makes part of my online course on Data Structures & Algorithms which covers different types of data structures and algorithms and their implementation in JavaScript.
If you take the course, I’m hoping by the end of it you’ll acquire the necessary tools that will help you to pick the right data structure to solve any specific problem. Moreover, I’m hoping also that it would help you to have an easier time answering future interview questions about data structures and algorithms.
Data Structures: Concepts
To explain what are data structures, let’s reverse engineer the expression ‘data structure’. We can clearly see that it is composed of two main terms, data and structure.
‘data’ can be generally defined as a set of items. Whereas, ‘structure’ can be defined as the arrangement of something. Now, if we combine the two definitions, we will have something like this: a data structure is an arrangement of a set of items.
In the context of computer science, a data structure is a way of arranging data in a specialized format on a computer memory so that it can be efficiently managed i.e. stored, processed, and retrieved.
Now, to build a solid foundation in data structures, I would like to walk you through some important related concepts first.
# How Is Data Stored in Computers?
Data are stored in memory as numbers composed of 0 and 1 digits (based on the binary system). Each digit is called ‘Bit’. A bit is the smallest unit of memory. At the level of hardware, each bit is an electrical device called a ‘transistor’. When the transistor is OFF, it represents the value 0 in memory. On the other hand, when it is ON, it represents the value 1.
You can imagine memory in a computer as a stack of shelves. Each shelf is a succession of eight bits. Every eight bits (a shelf) is often called a ‘byte’. Each shelf is accessible via a unique identifier.
When you write ‘var a = 1;’ in your code, your machine would allocate 8 shelves (8 bytes) starting at the memory address ‘0’ (The memory address could be any other unique identifier, we’re assuming it is 0 just for the sake of this example). The binary representation of the number 1 would look something like 00000000.00000000.00000000.00000000.00000000.00000000.00000000.00000001.
If you would like, another day, access the value of the variable a, your machine knows that it is at the memory address ‘0’ and it is a number. Therefore, it is going to count 8 bytes (case of JavaScript).
Different types of data have different representations in your computer’s memory. This is what leads us to talk about the next concept…
# What Are Data Types?
Simply put, a data type identifies what type of value a variable holds and what set of operations are allowed on it. A data type gives an insight to the compiler (or the interpreter) on how would you (as a programmer) use a variable.
Different programming languages have different types of data. But they can be mainly classified into two categories. There are primitive data types that are predefined by the language such as integers, floats, booleans, strings, chars…etc. They represent the most basic immutable types of values that a variable can accept and are implemented differently in different languages. On the other side, there are composite data types ( native to the language or defined by the user). These are constructed using a combination of primitives such as objects, arrays, maps, lists, stacks…etc
Since we are concerned with JavaScript. It has seven (07) primitives: Number, String, Undefined, Null, Boolean, BigInt, and Symbol. And many composite data types: Object, Function, Array, Set, Map, Date,…etc. You can find an exhaustive list of built-in data types in JavaScript here.
# How do Data Structures Relate to Data Types?
Actually, when we’ve been talking about composite (compound) data types, we were referring at the same time to data structures. If we would like to define data structures once again, we could say that a data structure is a collection of data types. However, they differ from primitive data types in the way they are implemented. What do we mean by that?
The implementation of primitive data types is abstract (hidden) and language-specific. For example, a value is directly assigned to a primitive data type, and most likely you don’t know how it is done.
On the contrary, data structures (composite data types) are concretely implemented. It means that they concretely define the way to deal with the data. For example, to add an element to a ‘stack’, you would use the push() method.
Data Structures: The Classification
Despite the choice of programming language, data structures can be categorized in different ways. Though, generally, they can be classified as Linear and Non-Linear data structures.
A data structure is said to be linear if the data is arranged in a straight sequential order one after the other. Good examples of that are arrays, stacks, queues, and linked lists as shown in the diagram above.
On the other hand, a data structure is said to be non-linear when the data is arranged in non-sequential order, or in a hierarchical manner instead. Examples of that are graphs and trees.
Data Structures: Basic Operations
The data within a data structure is processed by means of a set of different methods. However, it is common that the following seven(07) basic operations are used for data management in data structures.
- Selecting: accessing a particular item within a data structure.
- Traversing: visiting each item within a data structure at least once.
- Inserting: adding a new item to a data structure.
- Deleting: removing an item from a data structure.
- Searching: finding a specific item within a data structure that satisfies one or more conditions.
- Sorting: arranging the items within a data structure in a specific logical order.
- Merging: Combining two data structures into a single one.
Data Structures: The Right Choice
Choosing the right data structure to solve a particular problem would depend on many factors,
- Operations frequency: you should take into consideration the frequency with which operations are performed since it is going to help you quantify the resource constraints (mainly time and memory).
- Time complexity: same operations have different time execution in different data structures. Therefore, if you think time is crucial for you to solve a problem, you need then to take time complexity into consideration for your data structure choice.
- Space complexity: same as in time complexity, if the amount of memory space is a crucial constraint for you to solve a problem, then you should choose the data structure that fits this requirement.
Time complexity and space complexity are often expressed in big O notation — If you don’t know what is big O notation, don’t worry. This is going to be the object of our next blog post.
Data Structures: Benefits
We can sum up the need for data structures in two main points,
# Efficiency
We have already mentioned that choosing the right data structure to solve a problem helps you to increase the efficiency of your solution. Therefore, data is processed in the most appropriate way possible.
# Abstraction
Through the use of data structures, you ensure a high level of readability and simplicity by hiding the low-level details of the associated operations. The only thing a data structure provides is an interface to manipulate the data.
That’s it for this first read in this series.
If you have any questions or feedback, please, use the comment section. And stay tuned for upcoming tutorials…
Wait for a second, please! Before we leave, if you want, let’s connect…