Going from zero to a professional software engineer can be done solely with the help of free resources on the Internet. But developers who follow this path often ignore the concept of data structures. They think that this knowledge will not benefit them as they will only develop simple applications.

However, paying attention to data structures is important from the very beginning of the learning curve as they improve the efficiency of applications. While this doesn’t mean that you need to apply these structures everywhere – it is equally important to understand when they will be unnecessary.

What is a data structure?

Regardless of profession, everyday work involves data. A chef, a software engineer, or even a fisherman all work with some form of data.

Data structures are containers that store data in a specific format. This specific format gives the data structure certain qualities that distinguish it from other structures and make it suitable (or conversely, unsuitable) for certain usage scenarios.

Let’s take a look at some of the most important data structures that can help you create effective solutions.

Arrays

Arrays are one of the simplest and most commonly used data structures. Data structures such as queues and stacks are based on arrays and linked lists.

Each element in the array is assigned a positive integer that indicates the position of the element. This number is called an index. In most programming languages, indexes start at zero. This concept is called zero-based numbering.

There are two types of arrays: one-dimensional and multidimensional. The former are the simplest linear structures, while the latter are nested and include other arrays.

Basic operations with arrays

  • Get – get an array element by a specified index;
  • Insert – insert an array element by a given index;
  • Length – get the number of elements in the given array;
  • Delete – delete an array element by the specified index. It can be performed either by setting the undefined value or by copying the array elements, except for the one to be deleted, into a new array;
  • Update – updates the value of an array element by the specified index;
  • Traverse – loop through an array to perform functions on array items;
  • Search – search for a certain element in a given array using the selected algorithm.

There are several types of linked lists.

  • Single-link. The elements can only be traversed in the forward direction;
  • Double-linked. Elements can be traversed in both forward and backward directions. Nodes include an additional pointer, known as prev, pointing to the previous node;
  • Circular linked. These are linked lists in which the previous (prev) pointer of the “head” points to the “tail” and the next pointer of the “tail” points to the “head”.
    Basic operations with linked lists
  • Insertion – adding a node to a list. This can be done based on a desired location such as head, tail, or somewhere in the middle;
  • Delete – deleting a node at the beginning of the list or based on a specified key;
  • Display – displays the full list;
  • Search – search for a node in the given linked list;
  • Update – update the value of the node in the given key.

Application of linked lists

As building blocks of complex data structures such as queues, stacks, and some types of graphs.
In image slideshows, as the images follow each other strictly.
In dynamic structures for memory allocation.
In operating systems for easy tab switching.

Stack

A stack is a linear data structure that is created on the basis of arrays or linked lists. A stack follows the Last-In-First-Out (LIFO, “first-in-first-out”) principle, meaning that the last element to enter the stack will be the first to leave it. The reason why this structure is called a stack is that it can be visualized as a stack of books on a table.

Basic operations with stack

  • Push – insert an element into the upper part of the stack;
  • Pop – remove an element from the upper part of the stack and return the element;
  • Peek – view an element in the upper part of the stack;
  • isEmpty – check if the stack is empty.
    Application of stacks
  • In the browser navigation history;
  • To implement recursion;
  • In stack-based memory allocation.

Queue

Like a stack, a queue is another type of linear data structure based on either arrays or linked lists. Queues differ from stacks in that they are based on the First-In-First-Out (FIFO, “first-in-first-out”) principle, where the item that enters the queue first will be the first to leave it.

A real-world analogy of a “queue” data structure is a queue of people waiting to buy a movie ticket.

Basic operations with queues
Enqueue – inserting an element to the end of the queue.
Dequeue – deletes an element from the front of the queue.
Top/Peek – returns an element from the front of the queue without deleting it.
isEmpty – checks the contents of the queue.

Application of queues

Serving multiple requests on a single shared resource.
Flow control in multithreaded environments.
Load balancing.

Graph

A graph is a data structure that is a relationship of nodes, which are also called vertices. A pair (x,y) is called an edge. It indicates that node x is connected to node y. An edge can indicate weight/cost, that is, the cost of traveling along a path between two nodes.

Key Terms

  • Size – the number of edges in the graph;
  • Order – the number of vertices in the graph;
  • Contiguity – the case when two nodes are connected by the same edge;
  • Loop – a vertex connected by an edge to itself;
  • Isolated node – a node that is not connected to other nodes;
  • Graphs are divided into two types. They are distinguished mainly by the directions of the path between two vertices.

Tree

A tree is a hierarchical data structure consisting of vertices (nodes) and the edges that connect them. Trees are often used in artificial intelligence systems and complex algorithms because they provide an efficient approach to problem solving. A tree is a special type of graph that contains no cycles. Some argue that trees are completely different from graphs, but these arguments are subjective.

It’s important for developers to know at least the basics of these structures because when implemented correctly, they can help improve the efficiency of your applications.

By Algorithm basics