Section 1. Abstract Data Types Test

This section introduces the foundational concepts of Abstract Data Types (ADTs) in computer science. It covers the separation of interface from implementation, enabling modular software design and algorithmic reasoning. The section provides a detailed classification and overview of both linear ADTs (arrays, sets, linked lists, stacks, queues) and non-linear ADTs (associative arrays, trees, graphs), detailing their defining characteristics, core operations, primary advantages, limitations, and real-world applications.

1.1. ADT Concept

In computer science, data is a representation of facts, values, measurements, or symbols that can be stored, transmitted, and processed by a computer system.

A data type defines a set of possible values and a set of operations that can be performed on those values. For example, an integer type defines whole numbers and operations such as addition, subtraction, multiplication, and comparison.

An abstract data type (ADT) is a mathematical model of a data structure that specifies:

  • what kind of values can be stored;

  • what operations are allowed;

  • what behavior these operations must have.

An ADT describes the logical behavior of a data structure independently of its underlying data representation or physical memory layout.

For example, a stack is defined by the operations push, pop, and peek, and by the rule that the last inserted element is the first one removed. This rule is independent of whether the stack is implemented using an array, a linked list, or another internal representation.

The concept of abstract data types was formalized in the 1970s, while Donald Knuth’s The Art of Computer Programming played a major role in systematizing data structures and algorithms. ADTs became one of the foundations of modular programming, software design, and algorithm analysis.

The main purpose of ADTs is to separate interface from implementation. The interface defines what operations are available, while the implementation defines how these operations are actually performed.

This separation allows programmers and engineers to reason about data structures at different levels of abstraction.

1.2. Classification of Abstract Data Types

Abstract data types can be classified according to several criteria.

One common classification separates data structures into linear and non-linear structures.

Linear data structures organize elements sequentially. Each element has a logical predecessor and/or successor, except for the first and last elements. Arrays, linked lists, stacks, and queues are common examples of linear structures.

It is important to note that linear structure does not always mean contiguous memory storage. Arrays are usually stored in contiguous memory locations, while linked lists are linear only in a logical sense and connect elements through references or pointers.

Non-linear data structures organize elements in hierarchical, relational, or network-like forms. Trees and graphs are typical examples of non-linear structures.

Another classification separates structures into homogeneous and heterogeneous structures.

  • A homogeneous data structure stores elements of the same type.

  • A heterogeneous data structure can combine values of different types.

In many programming languages, this distinction is strict. In JavaScript, however, arrays and objects can store values of different types, which makes them flexible but also requires careful design discipline.

The main categories discussed in this section are:

  • Linear abstract data types:

    • arrays;

    • sets;

    • linked lists;

    • stacks;

    • queues.

  • Non-linear abstract data types:

    • associative arrays;

    • trees;

    • graphs.

1.3. Linear Abstract Data Types

Linear abstract data types organize data as a sequence of elements. The logical order of elements is one of their defining properties.

Linear structures are widely used because many computational tasks naturally involve sequences: lists of records, input streams, execution histories, buffers, tasks, commands, and ordered collections.

1.3.1. Arrays

An array is a linear abstract data type that stores a collection of elements and provides access to each element by an index.

In its fundamental or static form, an array has a fixed size and stores elements in contiguous memory locations. This allows direct random access to any element using its index.

If the base address of the array is known, the address of an element can be calculated using the formula:

address = base_address + index * element_size

This property makes arrays one of the most important and efficient data structures in computer science.

Characteristics of Arrays

  • Indexed access - Each element can be accessed directly by its numeric index.

  • Contiguous memory model - Classical arrays store elements in adjacent memory locations.

  • Fixed size in the classical model - The number of elements is usually defined at creation time.

  • Homogeneous storage in low-level languages - In languages such as C, arrays usually store elements of the same type.

  • Efficient traversal - Arrays are well suited for sequential iteration.

Main Operations on Arrays

  • access(index) - Returns the element stored at the specified index.

  • update(index, value) - Replaces the element at the specified index.

  • insert(index, value) - Inserts a new element at a specified position.

  • delete(index) - Removes an element from a specified position.

  • search(value) - Finds the position of a value in the array.

  • length() - Returns the number of elements.

Advantages of Arrays

  • Fast random access - Any element can be accessed directly by index.

  • Memory locality - Contiguous storage improves cache efficiency on modern hardware.

  • Simple structure - Arrays are easy to understand and implement.

  • Efficient iteration - Sequential traversal is usually fast.

Limitations of Arrays

  • Expensive insertion and deletion in the middle - Elements may need to be shifted.

  • Fixed size in the classical model - Resizing may require allocating a new array.

  • Wasted memory - If the allocated size is larger than needed, memory may be unused.

  • Limited flexibility - Arrays are less flexible than linked structures for frequent structural changes.

In modern programming languages, arrays are often implemented as dynamic arrays that can grow and shrink at runtime. JavaScript arrays are dynamic and can store values of different types, but the abstract concept of an array remains based on indexed access.

Applications of Arrays

Arrays are used in many areas of computing, including:

  • storing ordered collections of values;

  • implementing matrices and multidimensional data;

  • representing tables and buffers;

  • implementing stacks, queues, heaps, and hash tables;

  • supporting efficient iteration in algorithms.

1.3.2. Sets

A set is an abstract data type that stores a collection of unique values. Its defining characteristic is the uniqueness invariant: a set does not allow duplicate elements.

In the mathematical sense, sets are unordered collections. They do not provide indexed access and do not require positional ordering. However, some programming language implementations preserve insertion order during iteration. For example, JavaScript’s Set object preserves insertion order.

Although sets are not linear in the same strict sense as arrays or linked lists, they are often discussed alongside collection-based ADTs because they store individual elements and support membership operations.

Characteristics of Sets

  • Unique elements - Each value can appear only once.

  • Membership-based access - The primary operation is checking whether an element belongs to the set.

  • Dynamic size - Sets can grow or shrink as elements are added or removed.

  • No indexed access - Elements are not normally accessed by position.

Main Operations on Sets

  • contains(element) - Checks whether an element exists in the set.

  • add(element) - Checks whether a value exists in the set.

  • remove(element) - Removes a value from the set.

  • size() - Returns the number of unique elements.

  • union(set) - Returns a set containing elements from both sets.

  • intersection(set) - Returns a set containing only common elements.

  • difference(set) - Returns a set containing elements from one set that are not in another.

Advantages of Sets

  • Efficient deduplication - Sets automatically prevent duplicate values.

  • Fast membership testing - Many implementations provide efficient lookup.

  • Clear semantics - Sets directly model mathematical collections of unique elements.

  • Useful for algorithmic state tracking - Sets are frequently used to track visited elements.

Limitations of Sets

  • No positional access - Sets do not usually support indexing.

  • No key-value association - Sets store values, not pairs.

  • Implementation-dependent ordering - Mathematical sets are unordered, even if some implementations preserve insertion order.

Applications of Sets

Sets are used for:

  • removing duplicates from data;

  • checking membership efficiently;

  • representing mathematical sets;

  • tracking visited nodes in graph traversal;

  • filtering data streams;

  • comparing collections.

1.3.3. Linked Lists

A linked list is a linear abstract data type in which elements are stored as nodes. Each node contains data and one or more references to other nodes.

Unlike arrays, linked lists do not require contiguous memory. Elements can be stored in different memory locations and connected through references.

The first node of a linked list is usually called the head. The last node usually points to null, unless the list is circular.

Types of Linked Lists

There are several common types of linked lists.

  • Singly linked list - Each node stores data and a reference to the next node.

  • Doubly linked list - Each node stores data, a reference to the next node, and a reference to the previous node.

  • Circular linked list - The last node points back to the first node.

  • Circular doubly linked list - Each node has previous and next references, and the list forms a closed cycle.

Main Operations on Linked Lists

  • insertFirst(value) - Inserts a new node at the beginning.

  • insertLast(value) - Inserts a new node at the end.

  • insertAfter(node, value) - Inserts a new node after a specified node.

  • delete(value) - Removes a node containing the specified value.

  • find(value) - Searches for a node containing the specified value.

  • traverse() - Visits all nodes in sequence.

Advantages of Linked Lists

  • Dynamic size - The structure can grow and shrink at runtime.

  • Efficient insertion and deletion at known positions - Nodes can be relinked without shifting many elements.

  • No need for contiguous memory - Nodes may be stored anywhere in memory.

  • Useful for implementing other ADTs - Stacks, queues, and adjacency lists can be based on linked lists.

Limitations of Linked Lists

  • No direct random access - Accessing an element requires traversal from the head or tail.

  • Additional memory overhead - Each node stores references in addition to data.

  • Lack of spatial locality - Non-contiguous allocation reduces CPU cache performance due to pointer chasing.

  • More complex implementation - Pointer or reference management can introduce errors.

Applications of Linked Lists

Linked lists are used for:

  • implementing stacks and queues;

  • representing adjacency lists in graphs;

  • managing dynamic memory;

  • building undo and redo systems;

  • implementing polynomial and sparse matrix representations;

  • creating circular buffers and scheduling structures.

1.3.4. Stacks

A stack is a linear abstract data type that follows the Last In, First Out principle, commonly abbreviated as LIFO.

This means that the last element inserted into the stack is the first element removed from it.

The insertion operation is called push, and the removal operation is called pop.

Main Operations on Stacks

  • push(value) - Adds a value to the top of the stack.

  • pop() - Removes and returns the top value.

  • peek() - Returns the top value without removing it.

  • isEmpty() - Checks whether the stack is empty.

  • size() - Returns the number of elements.

Characteristics of Stacks

  • Restricted access - Elements are accessed only from the top.

  • LIFO behavior - The most recently added element is removed first.

  • Simple interface - Stack operations are small and clearly defined.

  • Useful for nested structures - Stacks naturally model recursion and nested expressions.

Applications of Stacks

Stacks are used in:

  • function call management;

  • recursion;

  • expression evaluation;

  • syntax parsing;

  • undo operations;

  • browser history;

  • depth-first search;

  • backtracking algorithms.

1.3.5. Queues

A queue is a linear abstract data type that follows the First In, First Out principle, commonly abbreviated as FIFO.

This means that the first element inserted into the queue is the first element removed from it.

The insertion operation is usually called enqueue, and the removal operation is called dequeue.

Main Operations on Queues

  • enqueue(value) - Adds a value to the rear of the queue.

  • dequeue() - Removes and returns the front value.

  • front() - Returns the front value without removing it.

  • isEmpty() - Checks whether the queue is empty.

  • size() - Returns the number of elements.

Common Variations

  • Simple queue - Elements are inserted at the rear and removed from the front.

  • Circular queue - The last position connects back to the first position, improving fixed-buffer utilization.

  • Priority queue - Elements are removed according to priority rather than insertion order.

  • Deque - A double-ended queue that allows insertion and removal at both ends.

Applications of Queues

Queues are used in:

  • task scheduling;

  • print job management;

  • breadth-first search;

  • buffering data streams;

  • handling asynchronous events;

  • managing requests in operating systems and servers.

1.4. Non-Linear Abstract Data Types

Non-linear abstract data types organize elements in structures that are not simple sequences.

Instead of a single logical order, they represent hierarchical, associative, or network-like relationships.

The most important non-linear ADTs are associative arrays, trees, and graphs.

1.4.1. Associative Arrays

An associative array is an abstract data type that stores a collection of key-value pairs. Each key appears at most once in the collection and is used to access its associated value.

Associative arrays are also known as maps, dictionaries, or symbol tables, depending on the programming language and context.

Unlike regular arrays, associative arrays:

  • use keys instead of numeric indexes;

  • associate each key with a value;

  • usually do not guarantee positional ordering, depending on implementation;

  • are optimized for key-based lookup.

An associative array follows these rules:

  • a value can be accessed using its key;

  • the same value may be stored under multiple different keys;

  • a single key can map to only one value at a time;

  • keys must be distinguishable from one another.

Main Operations on Associative Arrays

  • insert(key, value) - Adds a key-value pair.

  • find(key) - Returns the value associated with the key.

  • remove(key) - Deletes the key-value pair.

  • contains(key) - Checks whether a key exists.

  • size() - Returns the number of key-value pairs.

Hash-Based Associative Arrays

«Associative arrays are most commonly implemented using hash tables (providing $O(1)$ average-time complexity) or balanced search trees (providing $O(\log n)$ worst-case guarantees).

A hash table uses a hash function to convert a key into an index in an internal array. This makes lookup, insertion, and deletion efficient on average.

The idea of hashing was significantly developed by Hans Peter Luhn in 1953. Later, hashing became one of the fundamental techniques for building efficient symbol tables, dictionaries, caches, and databases.

Applications of Associative Arrays

Associative arrays are used for:

  • dictionaries and maps;

  • frequency counting;

  • caching;

  • indexing records by identifiers;

  • symbol tables in compilers;

  • configuration storage;

  • database indexing concepts.

1.4.2. Trees

A tree is a non-linear abstract data type that represents hierarchical relationships between elements.

A tree consists of nodes connected by edges. One node is designated as the root. Every node except the root has exactly one parent, and a node may have zero or more children.

Trees are acyclic, which means they do not contain cycles.

Hierarchical Model

Tree terminology includes the following concepts:

  • Root - The top node of the tree.

  • Parent - A node that has one or more children.

  • Child - A node connected below another node.

  • Leaf - A node with no children.

  • Internal node - A node with at least one child.

  • Subtree - A tree formed by a node and its descendants.

  • Depth - The distance from the root to a node.

  • Height - The length of the longest path from a node to a leaf.

Fundamental Properties

A tree with n nodes has exactly n - 1 edges.

There is exactly one path from the root to any node.

Because of these properties, trees are useful for representing hierarchical data, decision processes, and sorted collections.

Structural Classification

Common types of trees include:

  • Binary tree - Each node has at most two children.

  • Binary search tree - A binary tree where left descendants are smaller and right descendants are greater than the node.

  • AVL tree - A self-balancing binary search tree.

  • B-tree - A balanced tree structure widely used in databases and file systems.

  • Trie - A tree used to store strings by prefixes.

  • Heap - A tree-based structure used to implement priority queues.

Historical Context

Tree structures became central to computer science with the development of symbolic computation, parsing, searching, and file organization.

John McCarthy’s work on Lisp in 1960 popularized recursive list and tree-like structures in programming language theory.

Donald Knuth later systematized tree algorithms in The Art of Computer Programming, making trees one of the core topics in the study of data structures.

Applications of Trees

Trees are used in:

  • file systems;

  • database indexes;

  • syntax trees in compilers;

  • decision trees;

  • search algorithms;

  • priority queues;

  • autocomplete systems;

  • hierarchical document models.

1.4.3. Graphs

A graph is a non-linear abstract data type that represents relationships between objects.

A graph consists of a set of vertices and a set of edges. Vertices represent entities, while edges represent connections or relationships between them.

Graphs are among the most general and powerful structures in computer science.

Relational Model

A graph is commonly written as:

G = (V, E)

where:

  • V is a set of vertices;

  • E is a set of edges connecting vertices.

If edges have direction, the graph is called a directed graph or digraph.

If edges have no direction, the graph is called an undirected graph.

Typological Spectrum

Common types of graphs include:

  • Undirected graph - Edges have no direction.

  • Directed graph - Edges have direction.

  • Weighted graph - Edges have associated weights or costs.

  • Unweighted graph - Edges have no weights.

  • Connected graph - There is a path between every pair of vertices.

  • Disconnected graph - Some vertices cannot be reached from others.

  • Cyclic graph - The graph contains at least one cycle.

  • Acyclic graph - The graph contains no cycles.

  • Directed acyclic graph - A directed graph with no directed cycles.

  • Multigraph - Multiple edges may connect the same pair of vertices.

  • Hypergraph - An edge may connect more than two vertices.

Mathematical Foundations

Graph theory began with Leonhard Euler’s solution to the Seven Bridges of Königsberg problem in 1736.

This problem is widely considered the origin of graph theory. Euler showed that the possibility of walking through all bridges exactly once depends on the degree of the vertices.

Later, graph theory became essential in network analysis, optimization, transportation, scheduling, and computer science.

In the twentieth century, researchers such as Paul Erdős contributed significantly to random graph theory and combinatorics.

Graph algorithms also became central to operations research. For example, Lester Ford and Delbert Fulkerson developed important methods related to network flows in the 1950s.

Abstract Operations

Common graph operations include:

  • addVertex(vertex) - Adds a new vertex.

  • addEdge(source, target) - Adds an edge between vertices.

  • removeVertex(vertex) - Removes a vertex and its incident edges.

  • removeEdge(source, target) - Removes an edge.

  • getNeighbors(vertex) - Returns adjacent vertices.

  • hasPath(source, target) - Checks whether a path exists.

  • traverse(start) - Visits vertices according to a traversal strategy.

Graph Representations

Graphs are commonly represented using:

  • Adjacency matrix - A two-dimensional matrix that indicates whether edges exist between vertices.

  • Adjacency list - A collection where each vertex stores a list of its neighbors.

  • Edge list - A list of all edges in the graph.

Each representation has different memory and performance characteristics.

An adjacency matrix is simple and provides fast edge lookup, but it can consume large amounts of memory for sparse graphs.

An adjacency list is usually more memory-efficient for sparse graphs and is widely used in practical graph algorithms.

Applications of Graphs

Graphs are used in:

  • computer networks;

  • social networks;

  • transportation systems;

  • dependency analysis;

  • compilers;

  • recommendation systems;

  • search engines;

  • routing algorithms;

  • project scheduling;

  • artificial intelligence.

1.5. Summary

Abstract data types provide a formal way to describe data structures independently of implementation details.

The main idea of an ADT is to define what operations are available and what behavior they must have, while hiding the internal representation.

Linear ADTs, such as arrays, linked lists, stacks, and queues, organize data sequentially.

Set-like ADTs focus on uniqueness and membership.

Associative arrays organize data as key-value pairs.

Trees represent hierarchical relationships.

Graphs represent general relationships between entities.

Understanding these abstract models is essential before studying concrete implementations, algorithmic complexity, memory behavior, and performance on real computer architectures.