5. Data Structures, References and Memory

Introduction: From Values to Organized State

A program becomes useful when it can represent, preserve, retrieve, and transform information. A single variable is sufficient for a small calculation, but real software works with collections of users, transactions, messages, products, files, and events. The central concern of this chapter is therefore not merely how data is stored, but how the choice of representation affects access, modification, correctness, performance, and memory use.

Data structures provide organized ways of holding data. Arrays and strings support indexed sequences; records group related fields; lists support flexible collections; stacks and queues impose useful access disciplines; maps associate keys with values; and sets represent uniqueness. These structures are implemented through memory locations and references. Understanding the distinction between a value and a reference is essential because two variables may contain independent copies, or they may provide different paths to the same mutable object.

The chapter also introduces the operational ideas of stack and heap memory, aliasing, lifetime, mutability, and automatic memory management. These concepts explain many practical defects, including accidental modification of shared data, invalid references, memory leaks, excessive allocation, and poor algorithmic performance.

Learning Objectives

After studying this chapter, the student should be able to:

1. Select and use appropriate data structures for common programming problems.

2. Explain the organization and typical uses of arrays, strings, records, lists, stacks, queues, maps, and sets.

3. Distinguish value semantics from reference semantics.

4. Explain stack memory, heap memory, object lifetime, mutability, and aliasing.

5. Predict the effects of assignment, parameter passing, copying, and mutation.

6. Compare common data structures using access, insertion, deletion, and search considerations.

7. Apply automatic memory-management concepts to practical software design.

8. Identify common errors and make defensible data-structure choices in professional systems.

5.1 Data Structures as Models of Information

A data structure is a method of organizing data together with operations for accessing and modifying it. The same information can be represented in different ways, and the representation influences both the clarity of the program and its efficiency.

A useful distinction is between an abstract data type and its implementation. A queue, for example, is an abstract structure in which the first inserted item is the first removed. It may be implemented using an array, a linked list, or a language library. The abstract behavior remains the same even though the internal representation changes. This separation allows software developers to program against an interface while changing implementation details when requirements change.

Data structures should be evaluated against the operations a system performs most often. If a collection is frequently accessed by position, an array-like structure is usually appropriate. If items must be found by an identifier, a map may be more suitable. If duplicate values are irrelevant and membership testing is central, a set is often preferable. A technically correct structure can still be a poor engineering choice if it makes common operations unnecessarily expensive or obscures the domain model.

Arrays and indexed sequences

An array stores a fixed or dynamically managed sequence of elements, usually in contiguous or logically indexed positions. The index gives direct access to an element. In a typical array, accessing element `i` takes constant time, commonly expressed as O(1), because the address can be calculated from the starting address and element position.

Arrays are effective when the number of elements is known or changes infrequently and when positional access is important. They are less convenient when items are repeatedly inserted at the beginning or middle, because subsequent elements may need to be shifted. A dynamically resizable array usually allocates a larger internal block when its capacity is exceeded. This makes individual append operations efficient on average, although an occasional resize may be expensive.

The element type also matters. An array of primitive values may store values directly, whereas an array of objects may store references to objects. Consequently, copying the array may copy references rather than the objects themselves.

Strings and text representation

A string is a sequence of characters or, more precisely in many modern systems, a sequence of encoded units representing textual data. Strings may be mutable or immutable depending on the language. Immutable strings cannot be changed after creation; an apparent modification creates a new string. Immutability simplifies sharing and reduces certain side effects, but repeated concatenation can generate many temporary objects if a builder or buffer would be more appropriate.

Text handling also requires attention to character encoding. A visible character may occupy more than one byte, and some writing systems require multiple code points or combining marks. Applications that count, truncate, sort, or validate text should use APIs designed for the relevant character model rather than assuming that one character always equals one byte.

Records and objects

A record groups fields that describe one entity. For example, a student record may contain an identifier, name, programme, and enrolment date. Records improve cohesion because related values travel together. In object-oriented programming, a class may extend this idea by combining state with operations and access rules.

A record is usually preferable to several parallel arrays. Parallel arrays can become inconsistent when one array is updated and another is not. A collection of records expresses the relationship explicitly and enables operations such as `student.name` or `order.total` to reflect the domain model.

Lists

A list represents an ordered collection whose size can vary. An array-backed list provides rapid indexed access and efficient appending in typical implementations. A linked list stores nodes connected by references. Insertion or removal can be efficient once the relevant node is known, but finding that position may require traversal. Linked lists also incur memory overhead because each node stores link information and may have poorer processor-cache behavior.

The choice should not be based on the theoretical appeal of linked lists alone. In many application programs, a dynamic array is faster and simpler for ordinary iteration and appending. A linked structure becomes more attractive when stable node references, frequent local insertions, or specialized memory behavior are genuinely required.

Stacks and queues

A stack follows last-in, first-out order. Its principal operations are `push`, `pop`, and `peek`. Stacks model nested computation, undo histories, expression evaluation, browser navigation, and depth-first traversal. Function-call frames are also conceptually stack-like: the most recently entered call normally completes first.

A queue follows first-in, first-out order. Its operations are usually `enqueue`, `dequeue`, and `front` or `peek`. Queues model print jobs, customer requests, task scheduling, message processing, and breadth-first traversal. A circular array queue avoids repeatedly shifting elements by treating the array as wrapping around. In concurrent systems, queues may also provide synchronization between producers and consumers.

Maps and sets

A map, dictionary, or associative array stores key–value pairs. Keys normally identify values uniquely, although some libraries permit special policies for duplicate keys. A hash map commonly offers average-case constant-time insertion, lookup, and removal, subject to a good hash function and controlled load factor. A tree-based map generally offers logarithmic operations and maintains keys in sorted order.

A set stores unique elements and supports operations such as membership testing, insertion, removal, union, intersection, and difference. Sets are appropriate for enforcing uniqueness, checking permissions, recording visited nodes, or comparing groups. A set should be chosen instead of a list when order and duplicates are not part of the problem’s meaning.

5.2 Comparing Operations and Costs

Big-O notation describes how resource requirements grow as input size increases. It does not predict exact running time on a particular computer, but it helps compare designs. Typical costs include:

• Array indexing: O(1).
• Linear search in an unsorted array or list: O(n).
• Appending to a dynamic array: amortized O(1).
• Inserting into the middle of an array-backed list: O(n).
• Stack push and pop: commonly O(1).
• Queue insertion and removal: commonly O(1) with an appropriate implementation.
• Hash-map lookup: average O(1), with possible worst-case degradation.
• Balanced-tree map lookup: O(log n).

These are general patterns, not guarantees for every library. Memory locality, allocation overhead, ordering requirements, concurrency, and workload distribution also influence performance. For example, an O(n) scan over a small, contiguous array can outperform a theoretically faster structure because of lower overhead and better cache behavior.

A professional decision therefore begins by identifying required operations, expected data volume, ordering constraints, duplicate policy, update frequency, and lifecycle. Performance should be measured with representative data when it matters, rather than inferred solely from labels such as “fast” or “constant time.”

5.3 Values, References, and Assignment

A value is data considered independently of a particular storage location. An integer with value 7, a Boolean value, or an immutable string can often be reasoned about as a value. A reference is a handle that identifies an object or storage location elsewhere. The exact implementation of a reference is language-dependent; it may be represented by an address, pointer-like token, or managed handle.

Consider the conceptual example:

```text

numbers1 = [10, 20]

numbers2 = numbers1

numbers2[0] = 99

```

If the language assigns references to mutable arrays, both variables now observe `[99, 20]`, because they refer to one array. If the language or operation makes a copy, `numbers1` remains `[10, 20]`. The important question is not the spelling of assignment but the language’s semantic rule and the operation used to copy data.

Value semantics mean that assignment and parameter passing behave as though an independent value has been transferred. Changes to one value do not change another equal value. Reference semantics mean that variables may refer to one shared object; mutation through one reference is visible through other references to that object.

Many languages combine these models. Primitive values may be copied directly, while class instances, arrays, and collections are accessed through references. Even this description must be treated carefully: a language may pass a reference by value, meaning that the reference itself is copied but both copies identify the same object. Reassigning the parameter then does not reassign the caller’s variable, while mutating the referenced object may be visible to the caller.

Shallow and deep copying

A shallow copy creates a new outer collection but preserves references held by its elements. A deep copy recursively creates independent copies of nested mutable objects, subject to the language and library’s definition of copyability. For example, copying a list of records may produce a new list while the records remain shared. This is often the source of unexpected changes.

Deep copying is not automatically superior. It may be expensive, fail for objects linked to files or network resources, and duplicate state that should remain shared. Alternatives include immutable objects, explicit update methods, copy-on-write strategies, or carefully defined ownership rules.

5.4 Memory, Lifetime, and Aliasing

At a simplified conceptual level, a running program uses a call stack and a heap. The stack holds call-related data such as parameters, local variables, return information, and temporary state. It is organized around nested procedure calls and is usually managed automatically as calls begin and end. The heap holds dynamically created objects whose lifetimes may not correspond directly to one function call.

This model is useful but not a complete description of every implementation. Optimizing compilers may keep values in registers, move objects, eliminate allocations, or represent some objects differently. The conceptual distinction remains valuable for understanding scope and lifetime.

A local variable stored in a stack frame normally ceases to be directly accessible when its call returns. An object created during the call may continue to exist if a reference to it is returned or stored elsewhere. In a garbage-collected language, the object becomes eligible for collection when no reachable reference can lead to it. Eligibility is not the same as immediate deletion.

Aliasing occurs when two or more references designate the same mutable object. Aliasing is not inherently incorrect. It can avoid unnecessary copying and allow components to cooperate through shared state. However, it creates a reasoning obligation: a change made through one alias may affect code using another alias. Hidden aliases make debugging particularly difficult.

A related problem is an escaped reference. If a class returns a direct reference to its internal mutable list, callers can modify supposedly private state. Defensive copying, immutable views, controlled accessors, or methods that perform validated updates can preserve encapsulation.

Mutability and state control

A mutable object can change after creation. An immutable object cannot; a new object is produced when a different state is required. Immutability supports safer sharing, easier testing, and more reliable concurrent execution. Mutability can be more efficient when large structures must be updated repeatedly, but it requires disciplined ownership and synchronization.

A useful design question is: who is allowed to change this object, and at what times? Clear ownership reduces accidental interference. In larger systems, immutable data-transfer objects, persistent collections, transactional updates, and controlled state managers are common ways to limit mutation.

5.5 Automatic Memory Management

In manual memory-management systems, a programmer explicitly allocates and releases memory. This can provide control but introduces risks such as leaks, double release, use-after-free, and dangling references. In automatic memory-management systems, a runtime identifies objects that are no longer reachable and reclaims their memory.

Tracing garbage collectors generally begin with root references, such as active stack variables and global objects, and follow references to identify reachable objects. Unreachable objects can be reclaimed. Reference counting instead maintains counts of incoming references; it can reclaim an object when the count reaches zero, but simple reference counting cannot by itself reclaim cycles.

Automatic memory management reduces a class of programming errors but does not eliminate memory problems. A program can retain objects unnecessarily by placing them in a global cache, listener registry, session table, or long-lived collection. This is often called a logical memory leak: the runtime sees the objects as reachable even though the application no longer needs them. Excessive temporary allocation may also cause pauses or increased CPU use.

Resource management is a separate issue. File handles, sockets, database connections, locks, and transactions may require explicit closing or structured cleanup even in a garbage-collected language. Memory reclamation does not necessarily release these external resources promptly.

5.6 Choosing Structures in Application Design

A useful design process begins with the domain. Identify the entities, their relationships, permitted duplicates, required ordering, expected operations, and lifecycle. Then select an abstract structure before selecting a concrete library type. For example, an online store may represent products by a map keyed by product code, the items in a customer’s order by an ordered list, discount codes by a set, and pending fulfilment tasks by a queue.

The design should also distinguish authoritative state from derived state. A map of users may be authoritative, while a set of active user identifiers may be a cache or index. If both are mutable and updated independently, inconsistency becomes possible. Encapsulating updates in one service or transaction reduces this risk.

In web applications, data structures appear at several layers. A request may be parsed into a record or object, validated fields may be held in a map, authorization roles may be represented as a set, and asynchronous jobs may enter a queue. At the database boundary, indexes and transaction mechanisms provide related forms of organization. At the API boundary, serialization must define whether nested objects are copied, referenced, or represented by identifiers; network transmission generally produces a separate representation rather than shared memory.

5.7 Illustrative Case Study: A Notification Processing Service

Background

A fictional company, Northstar Learning, operates a platform that sends email, SMS, and in-app notifications. During peak enrolment periods, users may generate thousands of notification requests per minute.

Situation and problem

The initial implementation stored pending notifications in a list. Workers repeatedly scanned the list for items ready to send. Duplicate requests were common, and a separate list of processed identifiers was used to prevent repeated delivery. Under load, scans became slow, duplicate tracking consumed increasing memory, and a maintenance script occasionally modified the list while workers were processing it.

Analysis

The pending work had queue semantics: notifications should generally be processed in arrival order, with retry rules for failures. The processed identifiers required set semantics because membership, not ordering or duplication, was important. Notification records needed fields such as recipient, channel, payload, retry count, and scheduled time, so a record or class was more appropriate than parallel arrays.

The maintenance script and worker threads also shared mutable collections without a defined synchronization policy. This created races in which an item could be sent twice or removed while being examined. Holding all historical identifiers forever created a logical memory-retention problem.

Approach and solution

The design was changed to use:

• A queue for ready-to-send notification records.
• A priority queue or time-ordered structure for scheduled notifications.
• A set with an expiry policy for recently processed identifiers.
• Immutable notification payloads after validation.
• A controlled worker interface rather than direct access to internal collections.
• Explicit retry and dead-letter handling for messages that repeatedly failed.

The service treated the queue as the owner of pending work. Workers obtained an item through an atomic operation, and completion status was recorded through a defined protocol. Metrics were added for queue length, processing delay, retry count, duplicate rate, and memory use.

Outcome

The revised model aligned each structure with the operation it supported. Membership checks no longer required list scans, and workers did not compete through unprotected direct mutation. Expiring historical identifiers bounded memory growth, while immutable payloads reduced accidental changes during processing.

Learning points

The case demonstrates that data-structure selection is a design decision, not a syntactic preference. It also shows that reference sharing, mutation, concurrency, and memory lifetime are connected. A correct abstract structure still requires a clear ownership and synchronization policy.

5.8 Common Errors, Risks, and Professional Practice

Several mistakes recur in application development. Using a list for frequent key lookup leads to avoidable linear searches. Using a set when order is part of the user-visible result loses required information. Removing items from a collection while iterating may skip elements or trigger a runtime error. Assuming that copying a collection copies every nested object can introduce aliasing defects.

Other problems arise from boundary cases: empty collections, duplicate keys, null or missing values, integer overflow in index calculations, invalid encodings, and queues that grow without bound. A stack may overflow through unbounded recursion. A map may behave unexpectedly if mutable objects are used as keys and then changed, because their hash or equality behavior may no longer match their position.

Good practice includes documenting ownership, choosing immutable values where practical, exposing interfaces rather than internal collections, validating keys and indices, defining duplicate and ordering policies, and measuring resource use. Tests should check not only normal results but also whether an operation unexpectedly mutates an input, whether two objects are independent after copying, and whether resources are released when processing fails.

Security and governance considerations are also relevant. A collection may contain personal data, credentials, or financial information. Retaining data longer than necessary increases exposure and may conflict with organizational policy or data-protection obligations. Logs and caches should avoid unnecessary sensitive values. Access control must apply to the operations that reveal or mutate structures, not merely to the data structure’s name.

5.9 Current Directions

Modern programming environments increasingly provide immutable collections, ownership or borrowing systems, persistent data structures, concurrent queues, and memory-safe languages. These approaches make sharing rules more explicit and can prevent classes of invalid-memory errors at compile time. Managed runtimes continue to improve garbage collection through generational, concurrent, and low-pause techniques, although every strategy involves trade-offs.

Data-intensive applications also use specialized structures such as probabilistic membership filters, distributed maps, columnar representations, and external queues. These tools are valuable when scale or latency justifies their complexity. They should not replace basic structures without a clear workload analysis. Artificial intelligence systems likewise depend on arrays, tensors, maps, graphs, caches, and queues; the same concerns about copying, memory pressure, batching, and ownership remain applicable.

Chapter Summary

Data structures organize information around the operations a program must perform. Arrays provide indexed access, strings represent text, records group related fields, lists represent ordered collections, stacks and queues impose access disciplines, maps associate keys with values, and sets represent uniqueness. Their performance depends on implementation and workload, so structure selection should follow domain requirements rather than habit.

Value semantics provide independent data behavior, while reference semantics permit multiple variables to designate one object. Shallow copying may preserve nested aliases, whereas deep copying attempts to duplicate nested state. Mutability makes shared objects powerful but introduces side effects and synchronization concerns. The conceptual distinction between stack and heap memory helps explain scope, lifetime, and object retention. Automatic memory management reclaims unreachable objects but does not prevent logical leaks or replace explicit management of external resources. Professional software therefore combines suitable structures with clear ownership, controlled mutation, secure retention, testing, and measurement.

Key Terms

Data structure: An organized representation of data together with operations for using it.

Abstract data type: A specification of behavior independent of a particular implementation.

Array: An indexed sequence supporting direct positional access.

String: A sequence representing textual data under a character-encoding model.

Record: A compound value containing named related fields.

List: An ordered collection whose size may vary.

Stack: A last-in, first-out collection.

Queue: A first-in, first-out collection.

Map: A collection associating keys with values.

Set: A collection of unique elements.

Value semantics: Behavior in which data is treated as an independent value when copied or passed.

Reference semantics: Behavior in which variables may identify the same object.

Mutability: The ability of an object to change after creation.

Aliasing: The existence of multiple references to the same object.

Shallow copy: A copy of an outer structure that may retain references to nested objects.

Deep copy: A copy that recursively duplicates eligible nested objects.

Stack memory: Call-oriented storage associated with active procedure execution.

Heap memory: Dynamically managed storage for objects with independently extending lifetimes.

Garbage collection: Automatic reclamation of objects that are no longer reachable.

Memory leak: Retention of memory or resources that an application no longer needs.

Review Questions

Short Answer Questions

1. What is the difference between an abstract data type and its implementation?

2. Why is a set generally more suitable than a list for membership testing with unique values?

3. Define aliasing and explain why it can cause unexpected side effects.

4. What is the difference between a shallow copy and a deep copy?

5. Why does garbage collection not eliminate the need to close files and database connections?

Long Answer Questions

1. Compare arrays, linked lists, stacks, and queues in terms of organization, typical operations, and suitable applications.

2. Explain value semantics and reference semantics using assignment, parameter passing, and mutation examples.

3. Describe the conceptual roles of stack memory and heap memory, including how object lifetime may extend beyond a function call.

4. Explain how maps and sets are implemented conceptually and discuss the performance and ordering trade-offs between hash-based and tree-based structures.

5. Discuss how immutability, encapsulation, and ownership rules reduce defects in large software systems.

Analytical / Application Questions

1. A system must process customer requests in arrival order, prevent duplicate request identifiers, and retrieve customer records by identifier. Select suitable structures for each requirement and justify your choices.

2. A method returns its internal mutable list to callers. Analyze the risks and propose at least two alternatives that preserve encapsulation.

3. A program copies a list of mutable objects and changes one object through the copied list, after which the original list also appears changed. Explain the cause and recommend an appropriate remedy, considering both shallow and deep copying.

22. Multiple Choice Questions with Answers

Question 1

A program frequently retrieves a customer record using a unique customer identifier. Which structure is most directly suited to this operation?

A. Stack

B. Map

C. Queue

D. Set

Correct Answer: B. Map

Question 2

Two variables refer to the same mutable list. A modification through one variable is visible through the other. This situation is called:

A. Encapsulation

B. Overloading

C. Aliasing

D. Serialization

Correct Answer: C. Aliasing

Question 3

Which operation is typically O(1) in an array-backed sequence?

A. Accessing an element by index

B. Inserting an element at the beginning

C. Searching an unsorted sequence

D. Removing an element from the middle

Correct Answer: A. Accessing an element by index

Question 4

A queue is the appropriate abstraction for which situation?

A. Undoing the most recent edit

B. Ensuring that each permission appears only once

C. Processing tasks in arrival order

D. Retrieving values by named keys

Correct Answer: C. Processing tasks in arrival order

Question 5

What does a shallow copy of a list containing mutable objects usually do?

A. Copies the outer list but may retain references to the same objects

B. Copies every nested object recursively

C. Converts all objects into immutable values

D. Deletes the original list

Correct Answer: A. Copies the outer list but may retain references to the same objects

Question 6

An object remains reachable through a global cache even though the application no longer needs it. In a garbage-collected system, this is best described as:

A. A stack overflow

B. A logical memory-retention problem

C. A syntax error

D. A value-semantic copy

Correct Answer: B. A logical memory-retention problem

Question 7

Which design best protects a class from callers accidentally modifying its internal mutable collection?

A. Return the internal collection directly

B. Expose a defensive copy or immutable view

C. Store the collection in a local variable only during construction

D. Replace the collection with a stack regardless of use

Correct Answer: B. Expose a defensive copy or immutable view

Question 8

Which statement about a hash-based map is generally correct?

A. Lookup is always O(n)

B. Lookup is typically average-case O(1), subject to implementation and hashing

C. It always maintains keys in sorted order

D. It permits no values to be associated with keys

Correct Answer: B. Lookup is typically average-case O(1), subject to implementation and hashing

Question 9

Which structure most naturally models nested function calls and depth-first traversal?

A. Stack

B. Queue

C. Set

D. Record

Correct Answer: A. Stack

Question 10

A developer chooses a list for a collection where duplicates are irrelevant and rapid membership testing is central. Which alternative is generally more appropriate?

A. Set

B. Stack

C. Record

D. String

Correct Answer: A. Set