Introduction to Data Structures

Data structures are the backbone of any software, but for many beginners — and even experienced programmers — this concept can seem abstract or even intimidating. The goal of this article is to serve as a starting point and provide an introduction to data structures in a simple and practical way.

We will cover everything from the basic concept of data to an introduction to the most well-known structures, with clear and objective examples.

If you are just getting started or want to strengthen your foundations, this guide is for you.

What is Data and How Does a Computer Represent Them?

Before talking about data structures, it is essential to understand what data are and how they are handled by a computer.

What is Data?

Broadly speaking, a computer works with two types of information: data and instructions. Data are information that can be interpreted or processed, while instructions define how the computer will process that data.

We can classify data into three main types:

• Numeric (integers and real numbers): such as 5, 42, 47.3, or -10;
• Characters: such as “Hello, world!”;
• Boolean: such as true or false.

In short, any piece of information that you want to store or manipulate in a program is considered data.

How Does a Computer Represent Data?

At its most fundamental level, a computer works only with digital electrical signals that can take two basic values: on = 1 and off = 0. Everything a computer does ultimately boils down to a sequence of zeros and ones.

Each 0 or 1 is called a bit, and groups of 8 bits form a byte. Everything on a computer — text, numbers, images, and sounds — is translated into this binary language, meaning it is represented as bits and bytes.

For Example:

• The number 5 in binary is represented as 00000101.
• The letter A is translated into binary based on tables such as ASCII (for example, 01000001).

This simplified representation allows the computer to process and store large volumes of information.

Primitive Data Types

The most basic data types present in a computer program are called primitive types. These types are used as the foundation for building all more complex data structures and are present in all programming languages.

The most basic primitive types are:

Integer Numbers

Integer numbers represent numeric values without decimal places, such as -10, 0, or 42.

Integers are stored as sequences of bits (0s and 1s), so to understand how a computer represents an integer, you just need to convert it from decimal to binary.

To represent negative numbers, programming languages adopt a standard of reserving the leftmost bit of the number to represent the sign (0 for positive and 1 for negative).

Additionally, it is possible to represent an unsigned integer, in this way using all bits to represent the value of the number itself, allowing larger numbers but without negative values.

Example: For an 8-bit integer (1 byte):

1. For a signed integer variable, the number 37 is represented as 00100101, while the number -37 is represented as 10100101;
2. If we define the variable as an unsigned integer type, the number 37 remains 00100101, but the number -37 does not exist. In this case, the leftmost digit is part of the number, so using the number 10100101 from the previous example, instead of -37, the value of the variable would be 165.

To run your own tests, you can use this decimal-to-binary number converter.

The range of values that can be represented depends on the number of bytes used to represent the number. The table below shows how many numbers can be represented in an integer variable, according to the size of the variable in bytes.

Floating-Point Numbers (floats)

Floating-point numbers are how a computer represents rational numbers, such as 3.14, 0.1, or 0.999…

The representation of a floating-point number by a computer, in a simplified way, works as follows:

The bits of the number are divided into three parts: sign, exponent, and mantissa. The mantissa defines the value of the number, and the exponent defines the magnitude, that is, the position of the decimal point.

For a 4-byte floating-point number, a common representation is 1 bit for the sign S, 8 bits for the exponent E, and 23 bits for the mantissa M. The number is then converted using the formula $n = (-1)^S x 2^{(E – 127)} x 1.M$

Example: The number 35.5 represented in floating point:

• Sign: 0
• Exponent: 10000100₂ = 132₁₀
• Mantissa: 00011100000000000000000₂

Applying the formula, we have:

$(-1)^0 x 2^{(132 – 27)} x 1.00011100000000000000000_2 = 1 x 2^5 x 1.109375_{10} = 35.5$

We will not go too deep into floating-point arithmetic in this article. For a deeper understanding of the topic, see the articles below.

• Floating-point arithmetic – all you need to know, explained interactively;
• Floating-point arithmetic;
• Floating-Point Arithmetic: Issues and Limitations.

If you want to see the conversion in practice, you can use this floating-point calculator.

Characters (Text)

To represent characters, a table is used that maps numbers to text characters, such as the ASCII table. Each character is associated with a decimal number, which is internally converted to binary for the computer to process.

Booleans

Boolean data are used to represent the result of logical expressions, meaning they have only two possible values: True and False.

Some languages have specific types to represent boolean values and reserved keywords for the possible values, as in the example below in Java:

boolean trueValue = true;
boolean falseValue = false;

boolean trueValue = true;
boolean falseValue = false;

Other languages, such as C, do not have dedicated types for this and use only the numbers 1 or 0 to represent logical values, where 1 is true and 0 is false.

int trueValue = 1;
int falseValue = 0;

int trueValue = 1;
int falseValue = 0;

Structured Data Types

Structured data types are structures that allow data to be organized in a more complex way. Unlike primitive data types, which can hold a single value, structured types are composed of multiple values. These values can be primitive types, other structured types, and can be of the same type or different types.

The most well-known structured types are arrays, and records.

What are Arrays?

Arrays are structured data types used to organize a collection of data of the same type in an indexed structure, which allows direct access to each individual value.

Arrays are used in situations where we need to work with long lists of data of the same type and need to access this data directly. In this case, instead of declaring multiple variables, we can declare a single array with a size equal to the maximum amount of data we will need.

An array can have one or multiple dimensions. A one-dimensional array represents a simple list of values, accessed through a single index, while multi-dimensional arrays are used to organize data in rows, columns, or more complex structures, enabling the representation of more structured data.

We can think of a two-dimensional array as an array of arrays, forming a two-dimensional structure. In the same way, it is possible to create an array of two-dimensional arrays, resulting in a three-dimensional structure, and so on.

What Are Records

Records, or structs, are data types that allow grouping values of different types, enabling the definition of a custom data type that can take on a more complex semantic role.

For example, we can define a record called User that contains the user’s name, age, and ID number, and then declare variables of type User to store all this information in a single variable in our program.

#include <stdio.h>
#include <string.h>

struct User {
    char name[50];
    int age;
    char idCode[11];
};

int main()
{
    struct User u;
    strcpy(u.name, "Frank");
    u.idade = 30;
    strcpy(u.idCode, "12345678901");

    printf("Name: %s\n, Age: %d\n, ID: %s\n", u.name, u.age, u.idCode);

    return 0;
}

#include <stdio.h>
#include <string.h>

struct User {
    char name[50];
    int age;
    char idCode[11];
};

int main()
{
    struct User u;
    strcpy(u.name, "Frank");
    u.idade = 30;
    strcpy(u.idCode, "12345678901");

    printf("Name: %s\n, Age: %d\n, ID: %s\n", u.name, u.age, u.idCode);

    return 0;
}

Abstract Data Types (ADTs)

Abstract Data Types, or ADTs, are a theoretical concept in Computer Science that aims to define, in an abstract way, sets of data, their relationships, operations, and rules for organization and manipulation, without worrying about the specific details of how these rules are implemented.

An example is the Stack ADT, which defines a structure where multiple elements can be inserted, and where those elements must necessarily be removed in the reverse order in which they were inserted — that is, the last element to be inserted is the first to be removed.

A stack can be implemented using an array, or it can be implemented using a dynamic structure based on records, such as a linked list. It does not matter which implementation is used, as long as it follows the rule mentioned above and guarantees the correct order of insertion and removal of elements.

Some common ADTs are Queues, Stacks, Graphs, Trees, and Hash Tables.

What Are Data Structures?

The term “data structures” can be used in any context that involves some of the more complex data types mentioned earlier. Any group of data organized in a structured way, designed to perform specific operations, can be considered a data structure.

However, in general, whenever you come across the term “data structures,” the context will usually be the implementation of one of the well-known ADTs.

As mentioned in the previous section, the Abstract Data Type defines the rules for organizing data and the operations that must be performed on that data, while the data structure itself deals with all the implementation details.

Why Do You Need to Know About Data Structures?

Understanding data structures is essential for several reasons:

1. Code Efficiency: Choosing the right structure can dramatically improve your program’s performance.
2. Problem-Solving Skills: Many programming challenges involve organizing and processing data efficiently.
3. Relevance in Technical Interviews: Job interviews often test your understanding of structures such as lists, stacks, or trees.
4. Real-World Applications: Data structures are present in almost everything, from search engines to social media applications.

When and How to Choose the Right Data Structure?

The choice of a data structure depends on:

1. Frequent operations: Such as searching, inserting, or removing data.
2. Data volume: Large datasets may require optimized structures.
3. Available memory: Some structures consume more memory than others.

Examples:

• Stack: Ideal for tasks such as undo/redo operations.
• Hash: Ideal for scenarios where we have a large set of data in memory and perform many lookups by a specific key.
• B-Tree: Ideal when working with data stored on disk.

Books on Data Structures

Even though it is entirely possible to understand data structures effectively through content available on the Internet and in courses, it is important to know that much of this content is based on books that are considered references in the field. So, if you want to dive deeper and gain a more detailed understanding of the subject, it is recommended to look into some of these references.

Below are some books that are references in many computer science courses:

1. “Introduction to Algorithms” – Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
   • The bible of algorithms and data structures, commonly referred to as “CLRS”.
   • It covers data structures and algorithms in a detailed and comprehensive way. It is ideal for university students.
   • It is the foundation of virtually every computer science course. If you want to choose a single book to understand the theoretical foundations, go with “CLRS”.

2. Cracking the Coding Interview” – Gayle Laakmann McDowell
   • It includes a review of fundamental data structure concepts.
   • It is focused on practical exercises and programming interviews.
   • It covers the content in a more superficial way, but for those who just want a high-level understanding and examples of how data structures are applied in programming interviews, it is a good choice.

Conclusion

Data structures are essential for any developer. They allow you to organize information efficiently and solve problems with confidence. Mastering these concepts is a major step toward professional growth.

In future articles, we will explore structures such as linked lists, trees, and graphs in detail. Subscribe so you don’t miss the upcoming content!

Thanks a lot, and see you next time!

Andrew Cavalcante Pacifico

Bachelor’s degree in Computer Science from the Federal University of Amazonas, with an MBA in Project Management from Fundação Getulio Vargas.

Currently works as an Engineering Manager at Méliuz.

With 20 years of experience in the field, has worked with a bit of everything: C, C++, Java, C#, Delphi, Node.js, AWS, PHP, Python, React, Angular, jQuery, and a whole bunch of other things that don’t even exist anymore 😀

Related posts:

What Do Square Brackets Mean in Regex?