Arrays, Linked Structures, Stacks and Queues

Introduction and Context

Data structures determine how information is organized in memory and how efficiently programs can access, modify, and process it. In artificial intelligence and machine learning systems, data structures support data ingestion, feature storage, token processing, graph traversal, scheduling, buffering, and model implementation. Although sophisticated libraries often hide low-level details, effective AI and ML developers still need to understand the structures beneath those libraries.

This chapter examines arrays, dynamic arrays, linked structures, stacks, queues, and deques. The central design issue is the trade-off between contiguous storage, which provides excellent locality and fast indexed access, and linked storage, which provides flexible insertion and deletion but requires pointer traversal. Stacks, queues, and deques are abstract data types that can be implemented using either arrays or linked structures.

The analysis uses asymptotic complexity. The notation O(f(n)) describes an upper-bound growth rate for an operation as the number of elements, n, increases. Complexity describes growth, not exact execution time. Constant factors, memory hierarchy, programming language, and implementation details also affect performance.

Learning Objectives

By the end of this chapter, students should be able to:

1. Explain the memory layout and operational characteristics of arrays and linked structures.

2. Implement fixed-size arrays, dynamic arrays, singly linked lists, and doubly linked lists.

3. Compare time and space complexity for common operations.

4. Implement stacks, queues, and deques using appropriate underlying structures.

5. Explain locality, cache behavior, resizing, and memory-management considerations.

6. Select suitable structures for parsing, buffering, scheduling, and AI/ML applications.

7. Analyze design trade-offs in a realistic applied scenario.

1. Abstract Data Types and Concrete Data Structures

An abstract data type (ADT) specifies the behavior of a collection without prescribing its implementation. For example, a stack supports insertion and removal according to last-in, first-out (LIFO) order. An implementation specifies how that behavior is achieved, such as with an array or linked list.

This distinction is important. A queue may be implemented with a circular array, a linked list, or a concurrent queue supplied by a programming library. The ADT remains the same, but memory use, locality, capacity, and performance differ.

Common operations include:

• Access: retrieve an element at a specified position.
• Search: locate an element satisfying a condition.
• Insertion: add an element.
• Deletion: remove an element.
• Traversal: visit elements systematically.
• Update: replace an existing value.

The appropriate structure depends on the operations that dominate the workload.

2. Arrays and Contiguous Memory

An array stores elements in adjacent memory locations. If each element occupies w bytes and the first element begins at address B, the address of element i, using zero-based indexing, is:

\[

\text{address}(A[i]) = B + i w

\]

Here, i must satisfy 0 ≤ i < n, where n is the logical number of elements. This formula assumes fixed-size elements and a conventional contiguous representation.

Because the address can be calculated directly, indexed access is O(1). Inserting or deleting an element in the middle generally requires shifting later elements, so the worst-case time is O(n). Searching an unsorted array is O(n), while binary search is O(log n) only when the array is sorted and random access is available.

2.1 Array operations

Consider the array [12, 18, 25, 31]. Inserting 20 at index 2 requires shifting 25 and 31 one position to the right:

[12, 18, 20, 25, 31]

Two elements move, although the array now contains five values. Inserting at the beginning of an array of n elements may require n shifts; inserting at the end is O(1) when unused capacity exists.

Deletion is analogous. Removing the element at index 1 from [12, 18, 25, 31] requires shifting 25 and 31 left:

[12, 25, 31]

An implementation must distinguish logical size, the number of stored elements, from capacity, the number of allocated positions. Confusing these values causes out-of-bounds access or incorrect iteration.

2.2 Locality and performance

Arrays have strong spatial locality: nearby elements are stored near one another. When a processor loads one memory block into cache, neighboring elements may be loaded as well. Sequential traversal therefore tends to be efficient. Arrays also have low per-element overhead because they do not normally need a separate pointer field for every value.

These properties explain why arrays are often preferable for numerical vectors, matrices, image pixels, batches of features, and model parameters. A theoretically O(n) array traversal can outperform a theoretically O(n) linked-list traversal because of cache behavior and fewer allocations.

2.3 Fixed-size arrays

A fixed-size array has a capacity chosen at creation. It is appropriate when the required size is known or when predictable memory use is important. Examples include a 784-element vector for a 28 × 28 grayscale image, a fixed-size lookup table, or a bounded packet buffer.

Advantages include simple indexing, compact storage, and predictable allocation. Limitations include inability to grow without allocating a new array and copying elements.

3. Dynamic Arrays

A dynamic array maintains a contiguous block with a capacity greater than or equal to its current size. When the block becomes full, the implementation allocates a larger block and copies the existing elements.

A common policy doubles capacity. If the old capacity is c, the new capacity is 2c. Other policies are possible; the choice affects memory overhead and copying frequency.

3.1 Append and amortized analysis

A single append is usually O(1), but an append that triggers resizing is O(n), because n elements may be copied. Nevertheless, appending n elements to an initially empty dynamic array takes O(n) total time under geometric growth.

Suppose capacities are 1, 2, 4, 8, and so on. The total number of copied elements before reaching a capacity near n is bounded by:

\[

1 + 2 + 4 + \cdots + 2^k < 2^{k+1}

\]

Since the final capacity is proportional to n, the total copying is O(n). Thus the average cost per append over a long sequence is O(1), called amortized constant time. Amortized analysis does not claim that every append is constant time; it distributes occasional expensive operations across the sequence.

3.2 Resizing policy

Geometric growth offers efficient append performance but temporarily uses additional memory. Increasing capacity by only one position on each overflow causes repeated copying and can make insertion of n elements take O(n²) time. A very large growth factor reduces copying but wastes more unused memory. Production libraries choose policies that balance allocation cost, memory overhead, and implementation constraints.

Dynamic arrays are particularly useful when the final collection size is unknown but indexed access and compact traversal remain important.

4. Linked Structures

A linked structure stores elements in separate nodes connected by references or pointers. A singly linked node contains a value and a reference to the next node:

```text

Node:

value

next

```

The list is represented by a reference called `head`. An empty list has `head = null`.

Unlike an array, nodes need not be adjacent in memory. This makes insertion and deletion flexible, but it reduces locality and requires pointer dereferencing.

4.1 Singly linked lists

To traverse a singly linked list:

```text

current = head

while current is not null:

visit(current.value)

current = current.next

```

Accessing the element at position i requires following i links, so indexed access is O(n). Searching is also O(n). Inserting at the head is O(1): create a node, set its next reference to the current head, and update head.

If a reference to the node immediately before an insertion position is already available, insertion is O(1). Finding that position may still require O(n) traversal. This distinction is essential when interpreting linked-list complexity.

A singly linked list with a tail reference can append in O(1), provided the tail is updated correctly. Without a tail reference, appending requires traversal and is O(n).

4.2 Doubly linked lists

A doubly linked node contains `previous` and `next` references:

```text

Node:

value

previous

next

```

Doubly linked lists support traversal in both directions and can delete a known node in O(1), because its predecessor is directly available. They use more memory and require more pointer updates than singly linked lists.

A robust implementation maintains invariants such as:

• If the list is empty, both head and tail are null.
• The head’s previous reference is null.
• The tail’s next reference is null.
• For every node, `node.next.previous` refers back to node when node.next exists.

Violating these invariants can cause lost nodes, cycles, or invalid memory access in low-level languages.

4.3 Sentinel nodes

A sentinel node is a dummy node placed at a boundary, often at both ends of a doubly linked list. It does not represent user data. Sentinel nodes reduce special cases because insertion and deletion can use uniform pointer-update logic even when the list is empty or an operation occurs at an end.

4.4 Linked structures and memory management

Linked structures require allocation for individual nodes. In garbage-collected languages, unreachable nodes are eventually reclaimed, although excessive short-lived allocation can still create overhead. In manual-memory languages, every allocated node must be released exactly once. Common errors include memory leaks, dangling pointers, double deletion, and accidental cycles.

Linked lists are not automatically faster than arrays. They are advantageous when frequent structural changes occur at known positions and random indexing is unimportant. They are often disadvantageous for numerical workloads dominated by sequential traversal.

5. Comparative Complexity and Design Choice

For n elements, typical complexities are as follows:

| Operation | Array / dynamic array | Singly linked list | Doubly linked list |

|---|---:|---:|---:|

| Indexed access | O(1) | O(n) | O(n) |

| Search, unsorted | O(n) | O(n) | O(n) |

| Insert at beginning | O(n) for a packed array | O(1) | O(1) |

| Delete at beginning | O(n) for a packed array | O(1) | O(1) |

| Append with suitable capacity/tail | O(1) amortized | O(1) with tail | O(1) with tail |

| Insert after known position | O(n) in general | O(1) | O(1) |

| Extra link overhead | Low | One reference per node | Two references per node |

The table describes typical implementations, not universal laws. For example, a dynamic array can remove the last element in O(1), while deletion from the middle requires shifting. A linked list can find an element quickly only if an external reference or additional indexing structure is available.

6. Stacks

A stack is a LIFO ADT. Its principal operations are:

• `push(x)`: place x on the top.
• `pop()`: remove and return the top element.
• `peek()`: return the top element without removing it.
• `isEmpty()`: test whether the stack contains no elements.

An attempted `pop` or `peek` on an empty stack is called underflow. A bounded implementation may also experience overflow when it is full.

6.1 Array-based stack

A dynamic array is a natural stack implementation. The top is represented by the current size. `push` appends to the end; `pop` removes the last element. Both operations are O(1) amortized, and indexed storage gives good locality.

```text

push(x):

append x to dynamic array

pop():

if array is empty: report underflow

x = last element

remove last element

return x

```

6.2 Linked stack

A linked stack inserts and removes at the head. Both operations are O(1), but each element requires a node allocation and a link. A linked stack is useful when capacity must grow without relocating all existing elements, although allocation overhead may be significant.

6.3 Applications

Stacks support function-call management, undo operations, depth-first search, expression evaluation, syntax parsing, and backtracking. In compiler construction, a parser may push symbols and intermediate states. In AI, stacks are used in nonrecursive tree and graph traversal and in search procedures such as depth-first exploration.

7. Queues

A queue is a FIFO ADT. Its principal operations are:

• `enqueue(x)`: add x at the rear.
• `dequeue()`: remove and return the front element.
• `front()`: inspect the front element.
• `isEmpty()`: test whether the queue is empty.

Queues model waiting lines and work pipelines. They are used in breadth-first search, print scheduling, event processing, network communication, and machine-learning data pipelines.

7.1 The inefficient array queue

If a queue removes items by shifting every remaining element toward index zero, each dequeue can be O(n). Repeatedly dequeuing n items can then require O(n²) total time. This is a common implementation mistake.

7.2 Circular-array queue

A circular queue treats an array as a ring. It maintains a front index and a size, or alternatively front and rear indices with an agreed empty/full convention. When an index reaches the physical end, it wraps to zero.

With `front` as the index of the first element and `size` as the number of elements, the rear insertion position is:

\[

\text{rear index} = (front + size) \bmod capacity

\]

The modulo operation is applicable because valid physical positions range from 0 through capacity − 1. Enqueue and dequeue are O(1) when capacity is available. A dynamic circular queue may resize when full.

7.3 Linked queue

A linked queue maintains both `front` and `rear` references. Enqueue inserts after rear; dequeue removes at front. Both operations are O(1). When the final element is removed, both references must be set to null. Failure to update rear creates an invalid reference to a removed node.

8. Deques

A deque—double-ended queue—supports insertion and removal at both ends:

• `addFront`, `removeFront`
• `addRear`, `removeRear`

A deque can be implemented efficiently using a circular array or doubly linked list. A singly linked list is less suitable because removing from the rear requires traversal unless additional structure is maintained.

Deques support sliding-window algorithms, task schedulers, palindrome testing, browser history, and monotonic queue techniques. A deque can also behave as either a stack or a queue, depending on which ends are used.

9. Worked Example: Choosing a Structure for a Sliding Window

Suppose a streaming system must maintain the most recent 1,000 sensor readings. New readings arrive continuously, and the oldest reading must be discarded when a new one arrives. The system also computes the average by scanning the current window.

A naïve array that inserts at the front and shifts 999 values on every arrival has O(n) update cost. A linked list can remove from the front and append at the rear in O(1), but scanning 1,000 separately allocated nodes may have poor locality.

A circular array of capacity 1,000 provides O(1) insertion and removal without shifting. If the average is recomputed by scanning the entire window, that calculation remains O(n), but the update itself is O(1). If a running sum is maintained, the average update is also O(1): subtract the value leaving the window, add the new value, and divide by the current number of readings. This optimization is valid only when numerical issues and changes in window size are handled appropriately.

The circular array is generally preferable because the window has a known bounded capacity and the data are scanned frequently. A deque is an appropriate ADT abstraction; the circular array is a suitable implementation.

10. Applied Case: An AI Inference Pipeline

Background

Consider an illustrative image-classification service receiving requests from many clients. Each request contains an image and metadata. The service must accept requests, process them in batches, and record intermediate preprocessing steps for diagnostics.

Problem

The system needs to:

1. Buffer incoming requests when inference workers are busy.

2. Preserve arrival order for standard requests.

3. Allow urgent requests to bypass ordinary work under controlled policy.

4. Store a batch compactly for vectorized model execution.

5. Support undoing the most recent preprocessing transformation during debugging.

Analysis

A FIFO queue is appropriate for ordinary requests because fairness and arrival order matter. A deque can support insertion of urgent requests at the front, although unrestricted priority insertion may starve ordinary requests. A dynamic array is suitable for assembling a batch because model libraries typically expect contiguous tensors and benefit from locality. A stack is suitable for recording reversible preprocessing operations.

Approach and solution

The service uses:

• A bounded or back-pressure-aware queue for incoming requests.
• A deque for controlled urgent-request handling.
• A dynamic array or tensor buffer for each inference batch.
• A stack of transformation records for diagnostic undo operations.

When a worker takes a request, it removes it from the appropriate queue. The batch builder appends compatible requests until a maximum batch size or timeout is reached. The preprocessing component pushes each transformation record onto a stack. If a diagnostic rollback is requested, records are popped in reverse order.

Outcome

The design matches each operation pattern to an appropriate structure. Contiguous batches improve compatibility with numerical kernels; queues decouple arrival from processing; the stack naturally models reversal; and the deque provides limited flexibility for urgent work.

Learning points

First, an ADT should be selected based on required behavior, while implementation should be selected based on capacity, locality, concurrency, and memory constraints. Second, operational fairness is a system property, not merely a data-structure property. Third, bounded queues and explicit back pressure are important: accepting unlimited requests can exhaust memory and degrade service for all users.

11. Implementation Quality and Best Practices

Reliable implementations should observe the following practices:

• Define empty, full, and boundary behavior explicitly.
• Maintain size and capacity separately where necessary.
• Document whether indices are zero-based and whether ranges are inclusive or exclusive.
• Check preconditions for underflow, overflow, and invalid indices.
• Preserve representation invariants after every mutation.
• Prefer library implementations in production unless a custom structure is justified.
• Benchmark realistic workloads rather than relying only on asymptotic notation.
• Consider cache locality, allocation frequency, object overhead, and garbage collection.
• Use tests for empty structures, singleton structures, repeated insertion and deletion, capacity transitions, and duplicate values.
• For concurrent systems, use synchronization or concurrency-safe abstractions; ordinary stacks and queues are not automatically thread-safe.

12. Challenges, Limitations, and Contemporary Developments

The main limitation of arrays is that contiguous storage makes arbitrary growth and middle insertion expensive. The main limitations of linked structures are pointer overhead, poor locality, allocation cost, and more complicated memory management. Stacks and queues are conceptually simple, but production systems must also address bounded capacity, cancellation, fairness, blocking behavior, and concurrency.

Modern systems increasingly use specialized structures such as lock-free queues, segmented arrays, ring buffers, memory pools, and cache-conscious containers. GPU and tensor workloads strongly favor contiguous layouts and regular access patterns. Distributed data pipelines use queues and buffers across process or network boundaries, where serialization, back pressure, and fault recovery become as important as local asymptotic complexity.

In AI applications, data structures can affect energy consumption and latency. Compact contiguous representations may reduce memory traffic, while excessive copying or allocation can increase both cost and environmental impact. Systems handling user data must also apply appropriate access control, retention policies, and secure deletion practices. A queue containing personal data is not merely a technical buffer; it is part of the system’s governance boundary.

Chapter Summary

Arrays provide constant-time indexed access through contiguous memory and usually offer strong cache locality. Their main weaknesses are costly resizing and shifting during middle insertion or deletion. Dynamic arrays address unknown final sizes through resizing, commonly using geometric growth; appends are O(1) amortized although individual resizing operations are O(n).

Linked structures store elements in nodes connected by references. They support efficient insertion and deletion when the relevant position is already known, but indexed access and search are generally O(n). Doubly linked lists use additional memory to support reverse traversal and simpler deletion of known nodes.

Stacks implement LIFO behavior and are useful for parsing, recursion management, undo operations, and depth-first search. Queues implement FIFO behavior and support buffering, scheduling, breadth-first search, and pipelines. Circular arrays and linked queues avoid the inefficiency of shifting elements during dequeue. Deques support operations at both ends and are useful for sliding windows and flexible scheduling.

The best structure depends on the dominant operations, memory layout, locality, capacity, concurrency, and application requirements. In AI and ML systems, arrays and dynamic arrays are particularly important for numerical data, while stacks, queues, and deques organize computation and data movement.

Key Terms

Array: A collection of elements stored in contiguous positions.

Abstract data type: A behavioral specification independent of implementation.

Capacity: The number of positions currently allocated by a structure.

Circular buffer: An array-based structure whose indices wrap around at the end.

Deque: A double-ended queue supporting insertion and removal at both ends.

Dynamic array: A resizable array that maintains logical size and capacity.

FIFO: First-in, first-out ordering used by queues.

Garbage collection: Automatic reclamation of memory that is no longer reachable.

Head: Reference to the first node of a linked structure.

LIFO: Last-in, first-out ordering used by stacks.

Locality: The tendency of a program to reuse nearby or recently accessed memory.

Node: A linked-structure record containing data and one or more references.

Overflow: An attempt to add to a full bounded structure.

Pointer/reference: A value identifying another memory location or object.

Queue: An ADT that normally removes elements in FIFO order.

Sentinel node: A dummy boundary node used to simplify linked-list operations.

Stack: An ADT that normally removes the most recently added element.

Tail/rear: Reference or position associated with the final element.

Underflow: An attempt to remove or inspect an element from an empty structure.

Amortized analysis: Analysis of average cost over a sequence of operations.

Review Questions

Short Answer Questions

1. Why is indexed access O(1) in an array but O(n) in a linked list?

2. Distinguish logical size from capacity in a dynamic array.

3. What ordering principle does a stack implement?

4. Why can shifting elements make a naïve array queue inefficient?

5. State one advantage and one disadvantage of a doubly linked list.

Long Answer Questions

1. Explain the memory layout, operations, and locality characteristics of arrays and linked structures.

2. Describe dynamic-array resizing and explain why append is O(1) amortized under geometric growth.

3. Compare array-based and linked implementations of stacks and queues.

4. Explain how a circular queue works, including the role of modular index arithmetic.

5. Discuss how data-structure choice affects an AI inference pipeline.

Analytical / Application Questions

1. A workload performs one million indexed reads and only occasional insertions at the end. Should an array, linked list, or deque be preferred? Justify the choice.

2. Design a structure for maintaining the last 500 events in a stream while supporting insertion of new events and removal of the oldest event. Explain the complexity of each operation.

3. A scheduler gives urgent jobs unrestricted access to the front of a deque. Analyze the risk to fairness and propose a data-structure or policy modification.

Multiple Choice Questions with Answers

Question 1

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

A. Accessing an element by index

B. Inserting at the first position

C. Deleting from the middle

D. Searching an unsorted array

Correct Answer: A. Accessing an element by index

Question 2

Why is dynamic-array append O(1) amortized under geometric growth?

A. Every append performs no memory operation

B. The total number of copied elements across resizes is O(n)

C. Resizing never copies existing elements

D. The array remains permanently full

Correct Answer: B. The total number of copied elements across resizes is O(n)

Question 3

Which structure naturally implements LIFO behavior?

A. Queue

B. Deque used only at the rear

C. Stack

D. Circular buffer used as FIFO

Correct Answer: C. Stack

Question 4

What is the usual time complexity of removing from the front of a linked queue with a front reference?

A. O(log n)

B. O(n)

C. O(n log n)

D. O(1)

Correct Answer: D. O(1)

Question 5

What is the main locality advantage of an array over a linked list?

A. Array nodes can be allocated anywhere

B. Adjacent elements are stored near one another

C. Arrays never require capacity management

D. Arrays support constant-time middle insertion

Correct Answer: B. Adjacent elements are stored near one another

Question 6

In a circular queue with front index f, size s, and capacity c, where is the next rear insertion position?

A. f + s

B. f − s

C. (f + s) mod c

D. s mod f

Correct Answer: C. (f + s) mod c

Question 7

Which operation is O(1) in a singly linked list when a reference to the predecessor node is already available?

A. Inserting after that node

B. Accessing an arbitrary index

C. Searching for a value

D. Finding the tail without a tail reference

Correct Answer: A. Inserting after that node

Question 8

Which application most directly requires stack behavior?

A. Breadth-first traversal

B. Undoing the most recent transformation

C. Processing requests in arrival order

D. Maintaining a fixed image vector

Correct Answer: B. Undoing the most recent transformation

Question 9

What is a principal cost of a doubly linked list compared with a singly linked list?

A. It cannot traverse forward

B. It requires two references per node

C. It cannot delete a known node efficiently

D. It always uses contiguous memory

Correct Answer: B. It requires two references per node

Question 10

Which structure is generally well suited to maintaining a fixed-size sliding window with frequent removal of the oldest item?

A. A circular array

B. An unsorted binary tree

C. A stack used only for push

D. A fixed array that shifts all elements on every update

Correct Answer: A. A circular array