What is a data structure?

Reading time5 min

In brief

Article summary

A data structure is a way of organizing data so that it can be processed more easily. It provides a concrete implementation of an abstract data type, which is not a built-in data type.

An abstract data type is associated with a set of operations that can be performed on it. It is called an abstract data type because it does not specify how the data is represented or how the operations are implemented.

Main takeaways

  • Abstract data types are data structures which are not built-in data types.

  • When using abstract data types, operations on the data are defined independently on how they are implementated (implementation is abstracted away).

  • Many types of abstract data types exist, e.g., linked list, stack, queue, tree, graph.

Article contents

1 — What is a data structure?

Data structures allow to store and retrieve data, perform operations on data, and solve specific problems. By understanding data structures, you can:

  • Decide which data structure is best for a given situation.
  • Write programs that run faster or use less memory.
  • Understand how to approach and solve complex problems in a systematic way.

Data types such as int, float, etc. are built-in data types, on which we can perform basic operations such as addition, subtraction, division, multiplication, etc. However, there may be situations where we need to define operations for our user-defined data types. These operations can only be defined when we need them. So, to simplify the process of solving problems, we can create data structures along with their operations and such data structures that are not built-in are known as “abstract data types” (ADT).

2 — Some commonly found ADT

Common abstract data types include:

  • Linked list – A data structure in which elements are not stored at contiguous memory locations. The elements in a linked list are linked using “pointers”, i.e., a link to the next element. They are of different types, e.g., singly-linked list, doubly linked list, circular linked list, doubly circular linked list. Operations performed on Linked list include: initialization, inserting elements, deleting elements, searching for elements, updating elements, traversing elements and reversing a linked list.

  • Stack – A data structure that follows a particular order in which the operations are performed. The order is Last In First Out (LIFO), i.e., the data item stored last will be accessed first. Entering and retrieving data is possible from only one end. The entering and retrieving of data is also called push and pop operation in a stack.

  • Queue – A data structure that follows a particular order in which the operations are performed. The order is First In First Out (FIFO), i.e., the data item stored first will be accessed first. A few basic operations performed on a queue are push (also called enqueue), pop (also called dequeue).

  • Tree – A data structure, also known as a non-linear and hierarchical data structure, where the elements are arranged in a tree-like structure. In a tree, the topmost node is called the “root node”. Each node contains some data, and data can be of any type. It consists of a central node, structural nodes, and sub-nodes which are connected via edges. Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure. Trees introduce numerous concepts such as node, root, branch, height of a tree, degree of a tree, etc. There are different types of trees: binary tree, binary search tree, AVL tree, B-tree, etc. Some common operations include: insert an element, search a element, traverse (Depth-First-Search traversal, Breadth-First-Search traversal) or balance.

  • Graph – A (non-linear) data structure that consists of vertices (or nodes) and edges. It consists of a finite set of vertices and set of edges that connect a pair of nodes. The graph is used to solve more challenging and complex programming problems. Graphs introduce numerous conecpts such as path, degree, adjacent vertices, connected components, etc. Some common operations performed on graphs include : add/remove a vertex, add/remove an edge, traverse, cycle detection, etc.

In the rest of the course, we will focus on some common data structures, which are built-in data types (lists, sets, tuples, and dictionaries) and some abstract data types (linked list, stack, and queue).

To go further

Looks like this section is empty!

Anything you would have liked to see here? Let us know on the Discord server! Maybe we can add it quickly. Otherwise, it will help us improve the course for next year!

To go beyond