Of the many subfields within computer science, algorithms and data structures may be the most fundamental—it seems to characterize computer science like perhaps no other. What is involved in the study of algorithms and data structures?

Why Must They Go Together?

data structures and algorithms were mentioned together. Why?

• Computing systems are concerned with the storage and retrieval of information.
• For systems to be economical, the data must be organized (into data structures) in such a way as to support efficient manipulation (by algorithms).
• Choosing the wrong algorithms and data structures makes a program slow at best and unmaintainable and insecure at worst.

How Do They Go Together?

It’s very helpful to think of the data type as the bridge between data structures and algorithms.

Data Types

So these data types are the key to everything right? What are they, exactly?

First of all, note that programs manipulate information, and information in a program is represented with entities. Entities are things like numbers, text, lists, and so on. To help us understand entities, it helps to classify them into types.

We have an intuition about what types are. As a first approximation, a type is just a set of values, for example:

• ℕ={0,1,2,3,4,...}
• ℤ={...,−2,−1,0,1,2,...}
• 𝔹={𝖿𝖺𝗅𝗌𝖾,𝗍𝗋𝗎𝖾}
• ℝ=the set of all real numbers
• ℂ=the set of complex numbers
• ℍ=the set of quaternions
• 𝖯𝗋𝗂𝗆𝖺𝗋𝗒𝖢𝗈𝗅𝗈𝗋={𝖱𝖤𝖣,𝖦𝖱𝖤𝖤𝖭,𝖡𝖫𝖴𝖤}
• 𝖲𝗎𝗂𝗍={𝖲𝖯𝖠𝖣𝖤𝖲,𝖧𝖤𝖠𝖱𝖳𝖲,𝖣𝖨𝖠𝖬𝖮𝖭𝖣𝖲,𝖢𝖫𝖴𝖡𝖲}
• 𝖳𝗐𝗈𝖣𝗂𝗆𝖾𝗇𝗌𝗂𝗈𝗇𝖺𝗅𝖯𝗈𝗂𝗇𝗍=ℝ×ℝ
• 𝖢𝖺𝗋𝖽={1..13}×𝖲𝗎𝗂𝗍
• 𝖣𝖾𝖼𝗄=the set of all permutations of Card
• 𝖲𝗆𝖺𝗅𝗅𝖱𝖾𝖺𝗅={𝑥∣𝑥∈ℝ∧0.0≤𝑥∧𝑥≤1.0}
• 𝖢𝗈𝗅𝗈𝗋=𝖯𝗋𝗂𝗆𝖺𝗋𝗒𝖢𝗈𝗅𝗈𝗋→𝖲𝗆𝖺𝗅𝗅𝖱𝖾𝖺𝗅
• 𝖡𝖳𝖲𝖬𝖾𝗆𝖻𝖾𝗋𝗌={Jin,Suga,J-Hope,RM,Jimin,V,Jungkook}
• 𝖫𝗂𝗌𝗍<𝖨𝗇𝗍𝖾𝗀𝖾𝗋>=ℤ∗
• 𝖫𝗂𝗌𝗍<𝛼>=𝛼∗ (woah—that type is parametrized by a type variable)
• 𝖳𝗋𝖾𝖾<𝛼>=𝛼×𝖳𝗋𝖾𝖾<𝛼>∗ 🤯

That’s not really good enough, though! The reason why entities have certain types is that they behave in certain ways: you can multiply numbers, reverse lists, capitalize text, block users, revoke credentials, promote employees, and so on. Properly specifying a type requires defining how the entities of that type behave.

These behaviors are captured (algebraically 😮😮😮) as operations with zero or more inputs and a single output. For example:

The same thing can be said without pictures, for example:

Ah, now we have behaviors. A data type is a set of values together with operations that define their behavior.
Not every operation is applicable to every type. Types provide constraints on what we can and cannot say.

Abstract Data Types
As an aside: you will sometimes hear the term abstract data type, abbreviated “ADT.” People use this term to emphasize the fact that the “internal structure and internal workings of the operations” are somehow unknown to the outside world. Only the effects of the operations matter. To many people, though, saying “data type” is enough—all datatypes are “abstract” in that sense.

A useful exercise is to identify things in your world and try to list as many behaviors as you can. Here is a starter set:

Data Structures

A data structure is an arrangement of data for the purpose of being able to store and retrieve information. Usually a data structure exists in order to provide a physical representation of a data type.

For example, a list (a data type, which we saw above) can be represented by an array (a data structure) or by attaching a link from each element to its successor (another kind of data structure).

Wait, what are arrays and links?

Building Blocks

Data structures are built with three primary structuring mechanisms:

Let’s dive in. A object, also known as an record, struct, or named tuple, is a single entity that has many properties, where each property has a name and a value, which is another entity. Here is a simple object, can you guess what it represents?

An array is an entity that has a number of constituent elements, packed tightly together in memory and indexable by small natural numbers. In most programming languages, the first index is 0, in others (Julia, Lua, MATLAB), the first index is 1. Here are some cities in Alaska to visit (in order, because arrays are ordered):

Important: Note that were the properties of a object come together to make one conceptual thing; arrays are generally thought of as a collection of distinct things.