Data Structures and Abstraction

Introduction and Context

Computer science is concerned not only with computation, but also with the disciplined organization of information and the design of interfaces through which computation is performed. A data structure is a systematic way of representing, storing, and relating data so that required operations can be performed efficiently. Abstraction is the practice of exposing essential behavior while concealing implementation details.

These ideas are inseparable. A data structure is useful because it supports an abstract model of interaction: a stack supports “insert at the top” and “remove from the top,” while its implementation may use an array or a linked list. Good software engineering depends on selecting an abstraction that expresses the problem clearly and a representation that satisfies performance, memory, reliability, and maintainability requirements.

At postgraduate level, data structures should therefore be studied not as a catalogue of containers, but as a relationship among:

• an abstract data type (ADT),
• a concrete representation,
• an operation set,
• correctness conditions, and
• resource costs.

The same abstract operation may have very different time and space costs under different representations. Conversely, an implementation that is fast for one workload may be inappropriate for another.

Learning Objectives

After completing this chapter, a learner should be able to:

1. Distinguish data, data structures, abstract data types, and interfaces.
2. Explain abstraction, encapsulation, representation independence, and invariants.
3. Analyze time and space complexity using asymptotic notation.
4. Select and justify arrays, linked structures, stacks, queues, hash tables, trees, heaps, and graphs for particular applications.
5. Explain the operation and limitations of major data structures.
6. Apply amortized analysis to dynamic arrays and related structures.
7. Design data structures using contracts and representation invariants.
8. Evaluate a data-structure choice in a realistic technical case.

1. From Data Representation to Abstract Data Types

1.1 Data structures and operations

A data structure consists of data items, relationships among those items, and operations that preserve the structure’s intended properties. For example, a binary search tree contains nodes arranged according to an ordering relation. Its operations may include search, insertion, deletion, and traversal.

An abstract data type specifies behavior without prescribing a representation. A finite set ADT might provide operations such as:

• add(x) — include element x;
• remove(x) — delete x if present;
• contains(x) — test membership;
• size() — return the number of elements.

The set ADT does not state whether elements are stored in an array, linked list, hash table, or tree. This separation permits implementation changes without requiring clients to change their reasoning or source code.

1.2 Interface, implementation, and abstraction barrier

An interface defines the operations visible to a client. An implementation supplies the internal representation and algorithms. The abstraction barrier prevents clients from depending on internal details.

For a queue, the interface may be:

• enqueue(x);
• dequeue();
• front();
• isEmpty().

The client relies on first-in, first-out behavior, not on whether the queue uses a circular array, linked nodes, or a concurrent buffer. This property is called representation independence.

Encapsulation is the programming mechanism that helps enforce the abstraction barrier. Private fields, module boundaries, opaque types, and controlled mutation reduce the number of assumptions that can be violated by other components.

1.3 Contracts and invariants

A data-structure operation can be specified using:

• Preconditions: what must be true before execution;
• Postconditions: what is guaranteed after successful execution;
• Invariants: properties that remain true whenever the structure is externally observable.

For a queue, an invariant is that removal returns the earliest element not previously removed. For a binary search tree, one common invariant is:

• every key in the left subtree is less than the node’s key;
• every key in the right subtree is greater than the node’s key.

If duplicate keys are allowed, the ordering rule must explicitly define where equal keys are placed or how counts are stored.

A representation invariant might state that a dynamic array has 0 ≤ size ≤ capacity, that all occupied positions lie in a specified prefix, and that no client can access unoccupied memory through the public interface. Algorithms should be designed to preserve these invariants after every mutation.

2. Measuring Efficiency

2.1 Cost models

Algorithm analysis requires a cost model. In a unit-cost RAM model, arithmetic on machine-sized integers, array indexing, assignment, and comparison are treated as constant-time operations. This model is useful but incomplete: very large integers, cache behavior, disk access, synchronization, and allocation may have nonconstant or highly variable costs.

For an input size n, asymptotic notation describes growth as n becomes large:

• O(g(n)) is an upper-bound class;
• Ω(g(n)) is a lower-bound class;
• Θ(g(n)) means both an upper and lower bound of that order.

For example, scanning an unsorted array for a target has worst-case time Θ(n), because up to n elements may need to be inspected. Access by a known array index is Θ(1) under the RAM model.

Big-O does not mean “the exact running time.” It suppresses constants and lower-order terms. An algorithm requiring 100n operations and one requiring n² operations are both technically O(n²), but the notation is most informative when a tight bound is stated: the first is Θ(n), while the second is Θ(n²) under the relevant assumptions.

2.2 Time, space, and workload

Complexity may be described for best, average, expected, amortized, or worst-case behavior. These are not interchangeable. A hash table may have expected constant-time lookup under assumptions about hashing and load factor, while its worst-case lookup is linear if many keys collide.

Space analysis includes auxiliary memory used by an algorithm and, where relevant, the memory occupied by the input structure. Recursive algorithms also consume call-stack space. In production systems, memory locality and allocation overhead can influence performance even when two structures have the same asymptotic complexity.

2.3 Amortized analysis

Amortized analysis determines the average cost per operation over a sequence, without assuming a probability distribution. A dynamic array that doubles its capacity may occasionally perform an expensive resize, but the total cost of many append operations remains linear.

Suppose an initially empty array doubles its capacity whenever it becomes full. During n appends, copying occurs at capacities 1, 2, 4, …, with total copying cost less than:

The n ordinary writes plus fewer than 2n copied elements give total work less than 3n. Thus the amortized cost per append is O(1), although an individual resize costs O(n). The guarantee depends on the growth policy and assumes sufficient memory is available.

3. Fundamental Sequential Structures

3.1 Arrays and dynamic arrays

An array stores elements in contiguous logical positions. Its principal strengths are direct indexing, compact storage, and good cache locality. Access to position i is constant time because the address can be computed from a base address and an element-size offset.

Insertion or deletion in the middle generally requires shifting elements. If an array contains n items and insertion occurs near the beginning, the worst-case cost is Θ(n). Appending is Θ(1) when space is available and amortized Θ(1) for a geometrically growing dynamic array.

A dynamic array must manage capacity separately from logical size. Excessive capacity wastes memory; insufficient capacity causes frequent resizing. Growth factors greater than one provide amortized constant-time appends, but the choice affects memory overhead and copying frequency.

3.2 Linked lists

A linked list stores nodes connected by references. A singly linked node contains a value and a reference to the next node; a doubly linked node additionally contains a previous reference.

Linked structures support insertion and deletion in constant time when the relevant node or predecessor is already known. Finding a position by rank requires traversal and is Θ(n). They avoid contiguous allocation but incur reference overhead and often exhibit weaker cache locality than arrays.

A linked list is appropriate when frequent local insertions and deletions dominate, especially when stable node identity is useful. It is less appropriate when random access, compactness, or traversal speed is central.

3.3 Stacks and queues

A stack obeys last-in, first-out (LIFO) order. Its principal operations are push, pop, and top. Stacks support expression evaluation, recursion management, depth-first search, undo operations, and syntax parsing.

A queue obeys first-in, first-out (FIFO) order. Its principal operations are enqueue and dequeue. Queues model scheduling, breadth-first search, event processing, and producer–consumer systems.

A queue implemented with an array should normally use circular indexing. If capacity = C, the next position can be computed as:

Here i is an index from 0 through C − 1, and mod denotes the remainder operation. The structure must separately track size or distinguish full and empty states; otherwise, identical front and rear positions may be ambiguous.

4. Associative Structures: Hash Tables and Maps

A map associates keys with values. A hash table applies a hash function to a key and uses the resulting value to select a table position. Because the table usually has fewer positions than possible keys, collisions are unavoidable.

Two common collision strategies are:

1. Separate chaining: each table position references a bucket containing several entries.
2. Open addressing: all entries remain in the table, and a probing sequence searches for an available position.

The load factor for a table with m positions and n stored entries is:

A lower load factor generally reduces collisions but consumes more memory. Under suitable assumptions—such as a sufficiently uniform hash function and controlled load factor—lookup, insertion, and deletion have expected Θ(1) cost. Worst-case cost remains Θ(n).

Hash tables do not naturally maintain sorted order. They are therefore excellent for membership tests and key-based retrieval, but poor for ordered traversal, predecessor queries, or range reporting. Security-sensitive systems must also consider adversarial inputs designed to produce collisions; randomized hashing, robust hash functions, and bounded resource policies may be necessary.

5. Trees and Priority Structures

5.1 Tree terminology

A tree is a connected acyclic structure with a hierarchical organization. Important terms include root, parent, child, leaf, depth, height, subtree, and degree. A binary tree has at most two children per node.

In a binary search tree (BST), the ordering invariant allows search to follow one branch at each comparison. If the tree height is h, search, insertion, and deletion take O(h). A balanced BST maintains h = Θ(log n), producing logarithmic operations. An unbalanced tree may degenerate into a chain with h = Θ(n).

A useful traversal property is that in-order traversal of a BST visits keys in sorted order. This makes trees suitable for ordered maps and range queries.

5.2 Balanced search trees

Balanced trees, including AVL trees and red–black trees, impose structural conditions that bound height. AVL trees maintain a stricter balance condition and may perform more rebalancing; red–black trees use a looser coloring invariant and often provide efficient updates in general-purpose libraries.

The exact balancing rule is less important than the design principle: a local invariant is maintained so that global height remains logarithmic. Rotations preserve the search-tree ordering while changing local structure.

5.3 Heaps and priority queues

A priority queue returns the element with minimum or maximum priority rather than the oldest inserted element. A binary heap is commonly represented in an array. For zero-based indexing, the children of node i are at indices 2i + 1 and 2i + 2, when those indices exist.

In a min-heap, each parent key is no greater than its children. The minimum is at the root. Insertion and removal of the minimum take O(log n), while inspection takes O(1). Building a heap from n arbitrary items using bottom-up heap construction takes Θ(n), not Θ(n log n), because most nodes are near the leaves and require little downward adjustment.

Priority queues support operating-system scheduling, discrete-event simulation, graph algorithms, network routing, and resource allocation.

6. Graphs: Modeling Relationships

A graph consists of vertices and edges. It may be directed or undirected, weighted or unweighted, and may permit multiple edges or self-loops depending on the application.

Two principal representations are:

Here V is the number of vertices and E is the number of edges. For a sparse graph, E is much smaller than V²; an adjacency list is generally preferable. For a dense graph or workloads dominated by edge-existence queries, a matrix may be justified.

Breadth-first search (BFS) uses a queue and explores vertices by increasing distance in an unweighted graph. With adjacency lists, its time complexity is Θ(V + E), assuming each vertex and edge is processed a constant number of times. BFS can compute shortest path lengths measured in number of edges.

Depth-first search (DFS) uses a stack explicitly or through recursion. It supports reachability, cycle detection, topological ordering in directed acyclic graphs, and connected-component analysis. Its adjacency-list complexity is also Θ(V + E).

The choice of representation is an abstraction decision: a graph interface may expose neighbors and edge operations while hiding whether the implementation uses lists, matrices, compressed sparse formats, or distributed storage.

7. Designing Data Structures Through Abstraction

A disciplined design process begins with the problem’s operations rather than with a favorite implementation.

Step 1: Identify semantic requirements

Determine whether the application needs ordering, uniqueness, duplicate preservation, random access, priority retrieval, range queries, persistence, or concurrency. A database index requiring ordered range scans has different requirements from a cache requiring fast membership and replacement.

Step 2: Define the ADT contract

Specify operation meanings, error behavior, accepted values, mutation rules, and complexity expectations. For example, remove(k) must state whether absence returns a special value, raises an exception, or has no effect.

Step 3: State invariants

Write properties that must hold after construction and every public operation. Invariants make correctness review and testing more systematic.

Step 4: Select a representation

Compare candidate structures using expected workload, memory limits, locality, update frequency, concurrency requirements, and failure behavior. Asymptotic complexity is necessary but not sufficient.

Step 5: Prove or test correctness

Use loop invariants, induction, contracts, property-based testing, and adversarial cases. Testing can reveal defects but cannot by itself establish correctness for every input.

Step 6: Benchmark representative workloads

Benchmarks should include realistic data distributions, warm-up behavior, allocation costs, cache effects, and tail latency where relevant. A benchmark that measures only average throughput may hide unacceptable worst-case delays.

8. Worked Example: Choosing a Structure for an Event Scheduler

Assume a system maintains n future events, each with a timestamp, and repeatedly removes the earliest event while inserting newly generated events.

A FIFO queue is incorrect because insertion order may differ from timestamp order. An unsorted array makes insertion cheap but requires scanning all events to find the earliest, yielding Θ(n) removal. A sorted array gives Θ(1) access to the earliest item but may require Θ(n) insertion due to shifting. A binary min-heap supports both insertion and removal in O(log n), with constant-time access to the minimum.

If the scheduler also requires frequent queries such as “return every event between times t₁ and t₂,” an ordered balanced tree may be more suitable. If events are processed in batches and timestamps are bounded integers, specialized bucket or radix-based methods may outperform comparison-based structures. The correct decision follows from the operation distribution, not from the name of the data structure alone.

9. Applied Case: A University Learning Platform

Background

This illustrative case concerns a university platform that manages course enrolments, student submissions, discussion relationships, and asynchronous notifications.

Problem

The initial system stored enrolments in lists and searched them sequentially. As the number of students increased, login authorization and course-page loading became slow. Notifications also arrived out of order because they were processed according to network arrival rather than priority and time.

Analysis

The platform requires several distinct abstractions:

• a map from student identifier to student profile;
• a set of authorized course memberships;
• a priority queue for urgent notifications;
• a graph for representing prerequisite relationships;
• a queue for ordinary notification processing.

A single universal structure would create poor trade-offs. Sequential membership search is Θ(n). A hash-based set offers expected Θ(1) membership under an appropriate load factor. A priority queue provides O(log n) insertion and removal of the highest-priority notification. A directed graph represents prerequisite edges and supports cycle detection to identify invalid curricula.

Approach and solution

The design exposes interfaces rather than representations. Authorization calls isEnrolled(student, course); it does not access hash buckets directly. Notification services call submit(notification) and next(); they do not depend on heap indices. The graph module validates that a prerequisite graph is acyclic before publishing a curriculum.

Each module records error behavior and invariants. For example, deleting a student must remove or safely transfer all dependent records, and notification priorities must use a documented ordering rule for ties. Metrics track average and tail latency, memory consumption, collision behavior, queue depth, and failed authorization attempts.

Outcome

The revised design reduces expected membership lookup cost and separates policy from representation. It also improves maintainability: changing the hash-table implementation or priority-queue library does not alter higher-level services. However, the system must still address hash-flooding attacks, privacy of student records, auditability of authorization decisions, and consistency when multiple services update related structures.

Learning points

1. One application often requires several ADTs.
2. Complexity must be matched to workload rather than quoted in isolation.
3. Abstraction reduces coupling and permits implementation evolution.
4. Security, privacy, and consistency are part of data-structure engineering.

10. Limitations, Risks, and Professional Practice

10.1 Complexity is not the whole performance story

Constant factors, cache locality, branch prediction, allocation, garbage collection, and synchronization can dominate real execution. A compact array may outperform a theoretically comparable linked structure because it reduces pointer chasing and improves locality.

10.2 Mutation and aliasing

When two components hold references to the same mutable structure, an update by one component may violate assumptions held by another. Defensive copying, immutable views, ownership disciplines, or controlled synchronization can reduce these risks.

10.3 Concurrency

A data structure that is correct in a single-threaded setting may fail under concurrent access. Atomicity, visibility, linearizability, lock ordering, and lock-free progress conditions must be specified where relevant. Thread-safe access often imposes overhead, so concurrency requirements should be identified at the design stage.

10.4 Persistence and failure

In-memory structures lose state on failure unless backed by durable storage. Persistent data structures preserve previous versions through structural sharing, supporting snapshots and safer updates at the cost of additional indirection and memory. Distributed structures must additionally address replication, partitioning, consistency, and network failure.

10.5 Ethics, privacy, and governance

Data structures influence what can be queried, retained, linked, or deleted. Indexes and logs can expose sensitive relationships even when the main data is protected. Systems should apply data minimization, access control, retention limits, encryption, audit logging, and legally appropriate deletion procedures. In educational, health, financial, and employment contexts, seemingly efficient joins or graphs can enable intrusive profiling.

11. Contemporary Developments

Modern systems increasingly use specialized structures such as bloom filters, count–min sketches, compact tries, suffix structures, learned indexes, columnar formats, and compressed sparse representations. Probabilistic structures trade exactness or update guarantees for lower memory and faster approximate queries. For example, a Bloom filter can report that an item is definitely absent or possibly present, but a positive result may be a false positive.

Machine-learning systems also depend on data structures: tensors, sparse matrices, parameter stores, priority queues, and graph representations. Learned indexes may use models to predict record positions, but they do not eliminate the need for fallback search and careful handling of distribution shifts. Artificial intelligence can assist in code generation or structure selection, but generated implementations require human verification of contracts, complexity, security, and edge cases.

Best-Practice Checklist

• Begin with an ADT and explicit operation semantics.
• State preconditions, postconditions, and representation invariants.
• Choose a structure according to workload and constraints.
• Report worst-case and expected costs distinctly.
• Consider memory locality, allocation, and tail latency.
• Protect abstraction barriers and avoid unnecessary exposure of internals.
• Test empty, singleton, duplicate, maximum-size, and adversarial cases.
• Document concurrency, persistence, error, and ownership behavior.
• Measure realistic workloads rather than relying only on asymptotic theory.
• Treat privacy, security, and deletion requirements as design constraints.

Chapter Summary

Data structures organize data and support operations; abstract data types define those operations independently of representation. Abstraction barriers, encapsulation, contracts, and invariants provide the foundation for reliable and maintainable designs. Arrays offer direct access and locality, linked structures support local updates, stacks and queues impose LIFO and FIFO policies, hash tables provide expected constant-time associative operations, trees support hierarchy and ordered access, heaps support priority operations, and graphs model relationships.

Asymptotic analysis explains how costs grow, while amortized analysis explains sequences containing occasional expensive operations. Complexity must be interpreted alongside memory behavior, workload distribution, concurrency, persistence, and security. Professional data-structure design begins with requirements, defines an ADT, selects a representation, preserves invariants, validates correctness, and benchmarks realistic use. The central lesson is that data structures are not isolated programming tricks; they are abstractions that connect computational models to dependable software systems.

Key Terms

Abstract data type: A specification of data behavior and operations independent of implementation.

Abstraction: Representation of essential behavior while concealing unnecessary details.

Abstraction barrier: Boundary separating a public interface from its implementation.

Amortized analysis: Analysis of average cost over a sequence of operations without requiring probability assumptions.

Array: Indexed collection usually stored in contiguous positions.

Binary search tree: A binary tree organized according to a key-ordering invariant.

Complexity: Measurement of resource growth, commonly time or space, as input size increases.

Encapsulation: Restriction of direct access to internal state through controlled interfaces.

Graph: Structure consisting of vertices and edges representing relationships.

Hash table: Associative structure using a hash function to locate entries.

Heap: Tree-based priority structure satisfying a parent–child ordering property.

Invariant: Property that remains true at defined points during execution.

Load factor: Ratio of stored entries to hash-table positions.

Queue: FIFO abstract data type.

Representation independence: Ability to change an implementation without changing client behavior.

Stack: LIFO abstract data type.

Tree: Connected acyclic structure with hierarchical relationships.

Worst-case complexity: Maximum resource cost over inputs of a specified size.

Review Questions

Short Answer Questions

1. What is the difference between an abstract data type and a data-structure implementation?
2. Define a representation invariant and give one example for a dynamic array.
3. Why does a binary search tree become inefficient when it is highly unbalanced?
4. What does the load factor of a hash table represent?
5. Distinguish a stack from a queue in terms of removal order.

Long Answer Questions

1. Explain abstraction, encapsulation, contracts, and representation independence in data-structure design.
2. Compare arrays and linked lists with respect to access, insertion, deletion, memory, and locality.
3. Explain collision handling in hash tables and distinguish expected from worst-case complexity.
4. Describe binary search trees, balanced trees, and heaps, emphasizing their invariants and applications.
5. Explain how graph representation affects memory use and traversal performance.

Analytical / Application Questions

1. A system performs one million membership tests, occasional insertions, and no range queries. Compare a sorted array, linked list, balanced tree, and hash table, and justify a recommendation.
2. Design an ADT for a task scheduler that supports priority, cancellation, and retrieval of the next task. State its operations, invariants, and likely implementation trade-offs.
3. A graph has 100,000 vertices and 150,000 edges. Decide whether an adjacency matrix or adjacency list is more appropriate for breadth-first search, and justify the decision using asymptotic space and traversal analysis.

Multiple Choice Questions with Answers

Question 1

Which property primarily defines an abstract data type?

A. Its memory address layout

B. Its observable operations and behavior

C. The programming language used to implement it

D. The number of machine words it occupies

Correct Answer: B. Its observable operations and behavior

Question 2

Under the RAM model, what is the typical time complexity of accessing an array element by a known index?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: A. Θ(1)

Question 3

Which structure follows last-in, first-out ordering?

A. Queue

B. Heap

C. Stack

D. Hash table

Correct Answer: C. Stack

Question 4

A hash table contains 80 entries and has 100 positions. What is its load factor?

A. 0.08

B. 0.8

C. 1.25

D. 20

Correct Answer: B. 0.8

Question 5

What is the expected lookup complexity of a well-designed hash table with a controlled load factor?

A. Θ(1)

B. Θ(log n)

C. Θ(n) always

D. Θ(n²)

Correct Answer: A. Θ(1)

Question 6

Which traversal of a binary search tree visits keys in sorted order?

A. Pre-order

B. Post-order

C. Level-order

D. In-order

Correct Answer: D. In-order

Question 7

With adjacency lists, what is the time complexity of breadth-first search for a graph with V vertices and E edges?

A. Θ(V)

B. Θ(E²)

C. Θ(V + E)

D. Θ(V² + E)

Correct Answer: C. Θ(V + E)

Question 8

What is the main purpose of a heap in a priority queue?

A. To preserve insertion order exactly

B. To provide efficient access to the highest- or lowest-priority item

C. To guarantee constant-time range queries

D. To store only unique keys

Correct Answer: B. To provide efficient access to the highest- or lowest-priority item

Question 9

Why can dynamic-array append be amortized Θ(1) when an individual resize costs Θ(n)?

A. Resizing never copies elements

B. The total copying cost over many geometric expansions is linear

C. Every append performs binary search

D. The array always has infinite capacity

Correct Answer: B. The total copying cost over many geometric expansions is linear

Question 10

Which choice best protects representation independence?

A. Allowing clients to modify internal fields directly

B. Publishing the exact node layout as part of every interface

C. Exposing operations while hiding internal representation

D. Using only arrays in every implementation

Correct Answer: C. Exposing operations while hiding internal representation