Data structures Part I

Data structures are foundamental in computer science and software development since they offer a concrete solution for a problem. They implement algorithms. For this reason, changing the data strucutre affect the entire program performance. Decide the right data strucutre to solve our problem is crucial for the permormance of the entire program.

Data strucutres can be defined as the concrete implementation of an interface. If an interface is the definition of a problem, the data strucure is the concrete solution of a problem [1].

Basic definitions

The interface is a mathematical model on data types which define the behaviour from the point of view of a user of the data. If you are a software engineer or developer their are also called Application Interface (API), meanwhile if you are a CS researcher their are called Abstract Data Type (ADP)[2].

It is possible give the following definitions:

• An Interface is a specification: they describe the supported operations.
• A Data Structure is a representation: they store data and implement algorithms that support operations on data.

So we can summarize the concept in the following table [2]:

Interface (API,ADP)	Data Strucutre
define specification	define implementation
what data can store	how data can store
define operations	define algorithms

Foundamental Interfaces

The two foundamental interfaces are [1]:

1. Containers (or sequence): retrive element by indexing
2. Dictionaries (or set): retrieve element based on key values or content.

In addition, there are two special case of containers which are the:

• stacks
• queues (priority)

1. Containers

The container is characterized by the following three properties:

• Access: the way of accessing the objects of the container. In the case of arrays, access is done with the array index. In the case of stacks, access is done according to the LIFO (last in, first out) order and in the case of queues it is done according to the FIFO (first in, first out) order;
• Storage: the way of storing the objects of the container
• Traversal: the way of traversing the objects of the container.

Typically, the basic operations implemented by a container are exploited in the Fig. 1 [2]:

Notice that a static container has a fixed size, while the dynamic container can change its size, removig its elements or adding new one.

2. Dictionaries

Dictionary stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection. We can call set the collection of only keys.

The container is characterized by the following three operations:

• Remove
• Insert
• Find

Typically a dictionary can be ordered or unordered. This depend on the data structure data implement the dictionary.

Foundamental Data Strucutres

The most common data structures are the following [1]:

• Arrays
• staic: A fixed-size collection of elements of the same type stored in contiguous memory locations.
• dynamic: A variable-size collection of elements, that allows elements to be added or removed.
• Lists
• singly-linked list: A collection of nodes where each node contains a data element and a reference (or link) to the next node in the sequence.
• doubled-linked list: Similar to a singly-linked list, but each node also contains a reference to the previous node.
• Trees
• binary search tree: A binary tree where each node has at most two children. For each node, the left subtree contains only nodes with values less than the node's value, and the right subtree only nodes with values greater than the node's value.
• binary tree: tree data structure in which each node has at most two children. It is not necessarily ordered like a binary search tree.
• heap: A special tree-based data structure that satisfies the heap property. For a max heap, each parent node is greater than or equal to its children; for a min heap, each parent node is less than or equal to its children.
• Hash table: A data structure that implements an associative array, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

C++ Example

In C++ the standard library, provides the container library (not to be confused with the container ADT) which implement a generic collection of class templates and algorithms that allow programmers to easily implement common data structures [3]. There are three (since C++11) classes of containers:

• Sequence containers: implement data structures which can be accessed sequentially.
• std::array: static contiguous array
• std::vector: dynamic contiguous array
• std::deque: double-ended queue
• std::foward_list: singly-linked list
• std::list: doubly-linked list
• Associative containers: implement sorted data structures that can be quickly searched (O(log n) complexity).
• std::set: collection of unique keys, sorted by keys
• std::map: collection of key-value pairs, sorted by keys, keys are unique
• std::multiset: collection of keys, sorted by keys
• std::multimap: collection of key-value pairs, sorted by keys
• Unordered associative containers: implement unsorted (hashed) data structures that can be quickly searched (O(1) average, O(n) worst-case complexity).
• std::unordered_set: collection of unique keys, hashed by keys
• std::unordered_map: collection of key-value pairs, hashed by keys, keys are unique
• std::unordered_multiset: collection of keys, hashed by keys
• std::unordered_multimap: collection of key-value pairs, hashed by keys

In addition to this three classic categories, the c++ standard define also the following two categories:

• Container adaptors: provide a different interface for sequential containers.
• std::stack: adapts a container to provide stack (LIFO data structure)
• std::queue: adapts a container to provide queue (FIFO data structure)
• std::priority_queue: adapts a container to provide priority queue
• Views: provide flexible facilities for interacting with one- or multi-dimensional views over a non-owning array of elements.
• std::span: a non-owning view over a contiguous sequence of objects
• std::mdspan: a multi-dimensional non-owning array view

References

[1]: S.S. Skiena. "The Algorithm Design Manual", Springer, 2020.
[2]: MIT Course. "Introduction To Algorithms", MIT OpenCourseWare, Spring 2020.
[3]: C++ container library in the standard

---