Sequential data structures organize elements according to a linear order. That order may be represented physically, as in an array whose elements occupy adjacent memory locations, or logically, as in a linked structure whose elements are connected by references. The distinction is fundamental in advanced computing because algorithmic complexity alone does not determine performance. Cache locality, allocation cost, memory fragmentation, resizing policy, pointer representation, concurrency, and workload characteristics can be equally important.

For artificial intelligence and machine-learning systems, these choices arise in feature pipelines, token buffers, graph-processing support structures, event queues, replay memories, schedulers, sparse data representations, and streaming systems. A theoretically elegant structure may perform poorly if it causes excessive cache misses or allocator activity. Conversely, a memory-efficient structure may introduce indirection and unpredictable latency.

This chapter examines dynamic arrays, linked structures, deques, circular buffers, skip lists, and memory-efficient representations. The emphasis is not merely on operations, but on design trade-offs: which structure should be selected for a particular access pattern, memory hierarchy, and performance objective?

Learning Objectives

1. Representation, Cost, and the Memory Hierarchy

The traditional RAM model treats every memory access as having equal cost. Modern processors violate this assumption. A contiguous array allows hardware prefetchers to anticipate subsequent accesses, whereas a linked list may require a separate cache-line fetch for every node. Thus, two structures with the same asymptotic traversal complexity, O(n), can have very different running times.

Spatial locality means that nearby addresses are likely to be used close together in time. Temporal locality means that recently used data is likely to be reused. Arrays generally provide strong spatial locality; linked structures often provide weaker locality unless nodes are allocated from a pool or arranged by a locality-aware allocator.

The total memory occupied by a node is not just its payload. It includes references, metadata, alignment padding, allocator headers, and sometimes garbage-collection bookkeeping. If a node contains a payload of P bytes and two references of R bytes, its raw logical size is approximately P + 2R, but the actual allocated size may be rounded upward to satisfy alignment constraints.

2. Dynamic Arrays

A dynamic array stores elements in a contiguous region with a logical size and a physical capacity. Let n denote the number of stored elements and C the capacity. The invariant is:

When an insertion would make n exceed C, a larger region is allocated and the existing elements are copied. A common growth rule is geometric expansion:

Here, g is the growth factor. The ceiling ensures an integer capacity. The rule applies when the current capacity is insufficient; it does not imply that every insertion reallocates memory.

2.1 Operations and amortized analysis

Indexing is O(1) because the address of element i can be computed from the base address and element size. Insertion at the end is usually amortized O(1), although an individual resizing insertion costs O(n) because elements must be copied. Insertion or deletion near the beginning is O(n) because many elements must be shifted.

Suppose a capacity starts at 1 and doubles whenever full. Across n append operations, the number of copied elements is bounded by:

where the final copied capacity is less than or equal to n up to the last expansion. Therefore, the total copying work is linear, and the average copying cost per append is constant. This is an amortized result, not a guarantee that each operation is constant-time.

The choice of g affects both time and space. A larger g reduces the frequency of reallocations but may leave more unused capacity. A smaller g reduces slack but causes more copying. If capacity is reduced after deletions, immediate shrinking can cause oscillation: alternating insertion and deletion repeatedly triggers allocation. Practical implementations use hysteresis, such as shrinking only when utilization falls below a sufficiently lower threshold.

2.2 Advantages and limitations

Dynamic arrays provide fast indexing, excellent locality, compact storage, and compatibility with vectorized operations. They are often the default representation for numerical tensors, feature vectors, and batches of records.

Their limitations are relocation cost, difficulty inserting in the middle, and possible allocation failure when a larger contiguous block cannot be obtained even though sufficient total free memory exists. References or pointers to elements may also become invalid after reallocation, depending on the programming language and implementation.

3. Linked Structures

A linked structure stores each element in a node containing a payload and one or more links. The nodes need not be adjacent in memory. This representation makes local insertion and deletion inexpensive after the relevant position has been located, but it sacrifices direct indexing and often weakens locality.

3.1 Singly linked lists

A singly linked node contains a payload and a next reference. With a head reference, insertion at the front is O(1). Appending is O(1) if a tail reference is maintained; otherwise it is O(n). Deleting the first node is constant-time, while deleting a specified node generally requires access to its predecessor.

A singly linked list is appropriate when traversal is predominantly forward and memory overhead must be lower than that of a doubly linked list. It is not appropriate for frequent reverse traversal or random indexing.

3.2 Doubly linked lists

A doubly linked node contains next and previous references. Given a direct reference to a node, insertion or deletion can be performed in constant time by changing a bounded number of links. The additional reference increases memory use and creates more opportunities for structural inconsistency.

3.3 Sentinel nodes and invariants

A sentinel is a non-data node representing a boundary. A doubly linked list can use a head sentinel and a tail sentinel, with an empty-list invariant in which the sentinels point to one another. Sentinels eliminate many special cases involving null references and make insertion and deletion operations more uniform.

Correct implementations should state invariants explicitly. For a doubly linked list, if node x has successor y, then y.prev must equal x. After every mutation, the forward and backward traversals should describe the same sequence. In systems programming, violating these invariants can lead to memory corruption; in managed languages, it can cause unreachable objects, leaks, or retained memory.

3.4 Allocation and fragmentation

Linked nodes are commonly allocated individually. This can produce external fragmentation, in which free memory is divided into separated regions, and internal fragmentation, in which allocated blocks contain unused padding or allocator overhead. Allocation and deallocation also impose latency and may contend for locks in multithreaded allocators.

A node pool or arena allocates a large region and serves nodes from it. Pool allocation can improve locality and make deallocation inexpensive, especially when many nodes have the same lifetime. Its disadvantage is coarse reclamation: memory may remain occupied until the entire arena is released.

4. Deques

A deque, or double-ended queue, supports insertion and deletion at both the front and the rear. Its abstract operations are push-front, push-back, pop-front, and pop-back. A deque does not require efficient random indexing, although some implementations provide it.

A linked deque typically uses a doubly linked list with front and rear references. Each end operation is O(1), but each node carries link overhead and may be allocated separately.

An array-based deque commonly uses a circular buffer. It offers compact storage and locality while retaining constant-time end operations. This design is usually preferable when the maximum or approximate size is known and predictable latency matters.

5. Circular Buffers

A circular buffer uses a fixed-capacity array and interprets the end of the array as adjacent to its beginning. It is particularly useful for streaming data, producer-consumer pipelines, logging, audio processing, and reinforcement-learning experience replay.

Let C be the capacity, h the head index, and t the tail index. A common representation reserves one slot and defines:

The buffer is empty when h = t. It is full when next(t) = h. Under this convention, the usable capacity is C − 1. The modulo operation is applied to indices, not to the stored values.

The buffer is empty when q = 0 and full when q = C. The count-based design uses all C slots but requires count updates and, in concurrent systems, careful synchronization.

5.1 Worked example

Consider a circular buffer of capacity C = 8 using the one-empty-slot convention. Its usable capacity is 7. If h = 5 and t = 2, the occupied positions are 5, 6, 7, 0, and 1, so five elements are stored. The next insertion position is 2. Since next(2) = (2 + 1) mod 8 = 3, the buffer is not full. The example demonstrates that numerical ordering of indices does not represent logical ordering after wraparound.

5.2 Concurrency considerations

A single-producer, single-consumer ring buffer can often use separate head and tail variables with carefully chosen memory-ordering operations. Multiple producers or consumers require stronger coordination, such as atomic compare-and-swap, sequence numbers, or locks. Correctness depends not only on the data structure but also on the language memory model. A volatile variable alone does not generally provide atomicity or establish all required ordering guarantees.

6. Skip Lists

A skip list is a layered probabilistic linked structure that supports expected logarithmic search, insertion, and deletion. The bottom level contains all keys in sorted order. Higher levels contain selected subsets of lower-level nodes and act as express lanes.

During search, the algorithm begins at the highest level and moves forward while the next key is less than the target. When moving forward would overshoot the target, it descends one level. The process continues until the bottom level is reached.

If each node independently receives a higher level with probability p, where 0 < p < 1, then the expected number of nodes at level i is approximately np^i for n bottom-level nodes. The expected total number of node occurrences is:

This geometric-series result assumes independent promotion and an effectively unbounded level sequence. In an implementation, the maximum level is capped, so the actual total is no greater than the corresponding truncated sum.

For common choices such as p = 1/2, skip lists have expected O(log n) search, insertion, and deletion time. Their worst-case time is O(n) because an unfavorable random structure is possible. Randomization should therefore be considered when strict worst-case latency is required.

Skip lists are attractive in ordered indexes and in-memory databases because they are simpler to implement than balanced trees and support efficient incremental updates. They still incur pointer overhead and may have poorer locality than array-based indexes. A node can also store multiple forward references, making memory consumption dependent on the random height distribution.

7. Memory-Efficient Representations

Memory efficiency is not equivalent to minimizing the number of abstract objects. It requires analyzing payload, metadata, alignment, references, and access behavior.

7.1 Struct-of-arrays and array-of-structs

In an array-of-structs layout, all fields for one record are stored together. This is useful when algorithms consume most fields of each record. In a struct-of-arrays layout, each field has its own contiguous array. This can improve locality and vectorization when an operation processes one field across many records.

For example, a model-serving pipeline that filters records using only timestamps and scores may benefit from separate timestamp and score arrays. A routine that always consumes every attribute of one record may benefit from an array of structs.

7.2 Index-based linking

Instead of storing machine pointers, a node can store an integer index into a contiguous node pool. This reduces representation size on some systems, makes serialization easier, and improves relocatability. It also permits compact handles, generation counters, and bounds checking. The trade-off is an additional array lookup and a limit imposed by the index width.

7.3 Intrusive structures

In an intrusive linked structure, link fields are embedded in the application object rather than in a separate wrapper node. This eliminates one allocation and can reduce overhead, but an object must be designed to participate in the structure. If an object must belong to several structures simultaneously, it needs separate link fields for each role.

7.4 Compressed and packed representations

Packed bitsets, delta encoding, variable-length integers, and compressed sparse formats can reduce memory bandwidth. However, decoding may increase CPU cost and complicate random access. The correct choice depends on whether the workload is memory-bandwidth-bound, latency-sensitive, or computation-bound.

8. Comparative Design Analysis

Structure	Indexing	End insertion/deletion	Middle update after location	Locality	Typical concern
Dynamic array	O(1)	Amortized O(1) at rear	O(n) for shifts	Strong	Resizing and relocation
Singly linked list	O(n)	O(1) with suitable end reference	O(1) with predecessor	Weak to moderate	Pointer and allocation overhead
Doubly linked list	O(n)	O(1) at both ends	O(1) with node reference	Weak to moderate	Two links per node
Circular buffer	Usually O(1) indexing	O(1) at supported ends	Not intended	Strong	Fixed capacity or resizing policy
Skip list	Expected O(log n)	Expected O(log n)	Expected O(log n) search/update	Moderate to weak	Probabilistic worst case

The table describes asymptotic behavior under conventional assumptions. Actual performance depends on element size, cache hierarchy, allocator behavior, concurrency, and the ratio of reads to updates.

9. Application Case: A Streaming Feature Pipeline

Background. Consider an illustrative real-time anomaly-detection service receiving sensor records from industrial equipment. The service computes rolling features, retains a recent history, and forwards batches to an inference engine.

Problem. The system must accept records continuously, discard the oldest records when the history limit is reached, and provide low-latency access to the newest window. A naive linked list introduces allocation activity for every record and causes poor cache behavior during feature computation. A naive dynamic array that shifts elements on every deletion is also inefficient.

Analysis. The workload is a bounded FIFO stream. Records arrive at one end and expire at the other. Feature computation scans a recent window sequentially, so locality is valuable. The system also has a predictable upper bound on the window size.

Approach. Use a fixed-capacity circular buffer for the raw records. Maintain head, tail, and count using a clear invariant. Store frequently scanned numeric fields in separate contiguous arrays or a struct-of-arrays layout. If records must be indexed by equipment identifier, maintain a separate hash table rather than forcing the buffer to support arbitrary search. For concurrent ingestion and inference, use a single-producer/single-consumer design where the architecture permits it; otherwise introduce explicit synchronization and benchmark its cost.

Outcome. The circular buffer avoids per-record allocation and shifting. Sequential feature extraction benefits from contiguous memory, while wraparound is handled by index arithmetic. A bounded buffer also supplies a clear overload policy: reject, overwrite the oldest record, or apply backpressure. That policy must be selected explicitly because it affects model quality and operational safety.

Learning points. The best structure follows the access pattern, not the apparent generality of the data. Separating responsibilities—buffering, indexing, and feature storage—often produces a better design than demanding that one structure solve every problem.

10. Selection Framework and Best Practices

Best practices include documenting invariants, separating logical size from capacity, using pool allocation for homogeneous short-lived nodes, avoiding premature linked-list use, benchmarking cache-sensitive workloads, and testing boundary conditions such as empty, full, wrapped, and single-element states. Instrumentation should measure throughput, tail latency, allocation count, memory footprint, and cache behavior—not only asymptotic operation counts.

In AI/ML systems, data structure design also affects reproducibility and governance. A bounded replay buffer that silently overwrites old experiences changes the training distribution. A concurrent queue with weak ordering may produce nondeterministic batches. Systems should document retention, ordering, eviction, and synchronization semantics, particularly when data provenance or auditability matters.

11. Challenges and Contemporary Directions

Modern systems increasingly combine compact representations with specialized memory management. Slab allocators, region-based memory, cache-conscious indexes, and persistent memory all challenge the assumption that ordinary heap allocation is adequate. GPU and accelerator workflows favor contiguous, regular layouts because irregular pointer chasing is difficult to execute efficiently in parallel.

Persistent and concurrent skip lists remain active research areas, especially for ordered key-value stores. Hybrid structures combine arrays for dense portions and links for sparse portions. Learned indexes may replace some conventional search structures by predicting the position of keys, but they do not eliminate the need for robust fallback structures and careful handling of distribution shifts.

No representation is universally optimal. A design that minimizes bytes may increase CPU time; a design that maximizes throughput may increase tail latency; and a design optimized for a static batch may be unsuitable for a continuously mutating stream. Evaluation must therefore be application-driven.

Chapter Summary

Dynamic arrays provide compact storage, direct indexing, and strong locality, but resizing and middle updates can be expensive. Geometric growth makes append operations amortized constant-time, although individual expansions remain linear. Linked lists make local structural updates inexpensive after a node has been located, but they sacrifice indexing, increase pointer overhead, and often suffer from poor locality and allocation fragmentation.

Deques support operations at both ends. Circular buffers implement bounded queues and deques efficiently through modular index arithmetic, with either a reserved slot or an explicit count to distinguish full and empty states. Skip lists use probabilistic multi-level links to obtain expected logarithmic ordered operations, at the cost of pointer overhead and nonconstant worst-case behavior.

Memory-efficient design requires attention to layout, alignment, allocation, indexing, and access patterns. Array-of-structs, struct-of-arrays, intrusive nodes, index-based links, pools, and packed representations each serve different workloads. In advanced systems, asymptotic complexity must be combined with locality, fragmentation, concurrency, capacity policy, and application semantics. The central design principle is to choose a representation that matches the dominant operations and the performance guarantees the application actually requires.

Key Terms

Dynamic array: A resizable contiguous array with separate logical size and physical capacity.

Capacity: The number of elements a representation can hold before resizing is required.

Amortized analysis: Analysis of average cost over a sequence of operations rather than of one operation alone.

Spatial locality: The tendency to access addresses near recently accessed addresses.

Doubly linked list: A linked structure whose nodes contain forward and backward links.

Head index: An index identifying the front or next removal position in a buffer.

Tail index: An index identifying the rear or next insertion position in a buffer.

Fragmentation: Inefficient use of memory caused by unusable gaps or allocation padding.

Memory pool: A preallocated region from which similarly sized objects are served.

Struct-of-arrays: A layout storing each record field in a separate contiguous array.

Intrusive structure: A structure whose link fields are embedded in application objects.

Invariant: A condition that must remain true before and after each valid operation.

Review Questions

Short Answer Questions

Long Answer Questions

Analytical / Application Questions

Multiple Choice Questions with Answers

Question 1

Which operation on a dynamic array is generally O(1) because the element address can be computed directly from its index?

Question 2

For a dynamic array that doubles capacity whenever it becomes full, the amortized cost of appending one element is:

Question 3

Using a circular buffer of capacity 8 with one slot reserved to distinguish full from empty, the usable capacity is:

Question 4

In a circular buffer, the next index after i in a buffer of capacity C is commonly computed as:

Question 5

What is the principal locality advantage of a dynamic array over a separately allocated linked list?

Question 6

Which structure is specifically designed to support insertion and deletion at both the front and rear?

Question 7

With promotion probability p in a skip list, the expected total number of node occurrences across all levels is approximately:

Question 8

Question 9

Which layout is usually preferable when an operation processes one field across many records?

Question 10

In the illustrative streaming feature pipeline, why is a circular buffer appropriate?

Correct Answer: B. The workload is a bounded FIFO stream with sequential scanning

Chapter 2 Advanced Sequential and Linked Structures

Advanced Sequential and Linked Structures

Introduction