Arrays, Linked Structures and Linear ADTs

Introduction

Linear data structures organize elements in a sequence in which each element has at most one predecessor and one successor, except at the ends. They are foundational to software systems because many application tasks—storing records, processing requests, maintaining browser history, buffering network data, and implementing caches—can be expressed as operations on ordered collections.

This chapter examines arrays, dynamic arrays, matrices, linked lists, stacks, queues, deques, and circular buffers. The central design question is not which structure is universally best, but which representation provides the required balance of access speed, insertion and deletion cost, memory usage, locality, and implementation complexity.

Learning Objectives

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

• Explain the representation and operation costs of arrays and linked structures.
• Implement and analyse dynamic arrays, matrices, linked lists, stacks, queues, deques, and circular buffers.
• Distinguish abstract data types from their concrete implementations.
• Compare traversal, insertion, deletion, caching, and memory-locality behaviour.
• Select suitable linear structures for full-stack applications.
• Identify correctness, performance, concurrency, and security concerns in implementations.

1. Abstract Data Types and Representations

An abstract data type (ADT) specifies values and permitted operations without prescribing how those operations are implemented. A stack ADT, for example, supports push, pop, peek, and isEmpty. It may be implemented using an array or a linked list.

A data structure is the concrete representation and algorithms used to implement an ADT. This distinction matters because two implementations can provide the same logical behaviour but have different time, memory, and locality characteristics.

For an input size n, asymptotic notation describes how resource use grows as n becomes large. Big-O notation gives an upper-growth classification. For example, array indexing is O(1), while searching an unsorted sequence is O(n). These classifications do not eliminate the importance of constants, memory allocation, processor caches, and workload patterns.

Core operation vocabulary

• Access: retrieve an element by position or key.
• Traversal: visit elements in sequence.
• Search: locate an element satisfying a condition.
• Insertion: add an element while preserving required order.
• Deletion: remove an element and restore structural validity.
• Capacity: allocated storage available in a structure.
• Size: number of elements currently stored.
• In-place operation: operation using only constant auxiliary memory, apart from the structure itself.

2. Arrays

An array stores elements in contiguous memory locations. If each element occupies w bytes and the first element begins at address b, the address of element i is:

Here, i is a zero-based index, b is the base address, and w is the element size in bytes. This formula assumes fixed-size elements and contiguous storage. Because the address can be calculated directly, random access is O(1).

A fixed-size array has a predetermined capacity. Its size cannot exceed that capacity without allocating another region and copying elements. Arrays are efficient for traversal because adjacent elements are usually located in adjacent cache lines. This property is called spatial locality.

Array operation costs

If insertion is performed at position p in an array containing n elements, the number of shifted elements is generally n − p. In the worst case, insertion at the beginning shifts n elements. Deletion at position p usually shifts n − p − 1 elements.

Ordered and unordered arrays

If order is irrelevant, deleting an element can be made O(1) by replacing it with the final element and reducing the logical size. This changes the order of the collection. If order is part of the data contract, shifting is required and deletion remains O(n).

3. Dynamic Arrays

A dynamic array combines an array representation with automatic resizing. It stores both a size and a capacity. When the array is full, it allocates a larger block, copies existing elements, and releases or abandons the old block.

A common policy doubles capacity. If the old capacity is c, the new capacity is 2c. The exact growth factor is an engineering choice: larger factors reduce resizing frequency but may waste more memory.

Appending is O(1) when capacity remains. A resize costs O(n) because n elements are copied. Nevertheless, append has amortized O(1) cost under geometric growth. Over many appends, the total copying work is proportional to the number of inserted elements rather than n for every operation.

Suppose capacities are 1, 2, 4, 8, and so on. Before reaching capacity 2^k, the total number of copied elements is:

Thus, for m appends, copying is O(m), and the average copying work per append is O(1). This is an amortized guarantee, not a claim that every append is constant time. A particular append that triggers resizing is O(n).

Implementation concerns

A robust dynamic array should:

1. Track size separately from capacity.
2. Check index bounds.
3. Define behaviour for null or invalid values.
4. Avoid integer overflow when calculating new capacity.
5. Copy elements safely, especially when objects require reference management.
6. Consider shrinking when utilization becomes very low, while avoiding repeated grow-shrink oscillation.

A common shrinking rule reduces capacity when size is at most one-quarter of capacity, then halves capacity. Such hysteresis prevents frequent resizing near a boundary.

4. Matrices and Multidimensional Arrays

A matrix is a rectangular arrangement of values with rows and columns. In row-major storage, the elements of each row are consecutive. For a matrix with r rows and c columns, zero-based element A[i][j] can be mapped to a one-dimensional array using:

Here, i is the row index, j is the column index, c is the number of columns, and offset is the zero-based linear position. The formula assumes row-major layout and valid indices 0 ≤ i < r and 0 ≤ j < c.

Column-major layout instead stores complete columns consecutively. The choice affects locality. In row-major storage, traversing rows from left to right is generally cache-friendly, whereas traversing columns may cause more cache misses.

Dense and sparse matrices

A dense matrix stores most positions explicitly. A sparse matrix contains many zero or absent values; storing every position may waste memory. Sparse representations commonly store only nonzero entries as triples such as (row, column, value), or use compressed-row structures. The appropriate representation depends on the proportion and distribution of nonzero values and on the operations required.

Matrices appear in image processing, recommendation systems, scientific computing, game engines, and machine-learning pipelines. In a web application, a matrix may represent permissions, adjacency relationships, or a batch of feature vectors, although large numerical workloads are often delegated to specialized libraries.

5. Linked Structures

A linked structure stores elements in nodes. Each node contains a value and one or more references to other nodes. Nodes need not occupy contiguous memory.

A singly linked node contains a value and a next reference. A doubly linked node contains next and previous references. A list usually maintains a head reference and may maintain a tail reference and a size counter.

Singly linked lists

A singly linked list supports insertion at the head in O(1). If a tail reference is maintained, insertion at the tail is also O(1). Access by index is O(n), because the list must be traversed from the head. Searching is O(n).

Deletion at the head is O(1). Deletion after a known predecessor is O(1), but finding that predecessor may require O(n) traversal. This distinction is important: the local pointer update is constant time, while locating the update position is not.

Doubly linked lists

A doubly linked list permits traversal in both directions. If a node to delete is already known, deletion is O(1): its predecessor’s next reference and successor’s previous reference are updated. The additional reference increases memory usage and creates more pointer-update cases, so implementations must carefully handle empty lists, single-element lists, and end nodes.

Sentinel nodes

A sentinel, or dummy, head and tail node can simplify boundary cases. Instead of treating the first and last real nodes as special, every insertion occurs between two nodes. Sentinels do not represent user data; they are structural markers.

Linked-list locality and allocation

Linked nodes provide flexible growth and avoid shifting elements, but their scattered allocation reduces spatial locality. Each node reference may require an additional memory access, and allocation overhead can be significant. Consequently, a linked list may be slower than a dynamic array even when both have an O(n) operation, especially for traversal.

6. Stacks

A stack is a last-in, first-out (LIFO) ADT. Its primary operations are:

• push(x): place x on the top.
• pop(): remove and return the top item.
• peek(): return the top item without removing it.
• isEmpty(): test whether no item is present.

A stack can be implemented by adding and removing at one end of an array or linked list. With a dynamic array, push and pop at the end are amortized O(1). With a linked list, push and pop at the head are worst-case O(1).

Stacks are used for function-call management, expression evaluation, undo operations, depth-first search, syntax parsing, and browser navigation. A web server may use a stack while parsing nested tokens, but unbounded user-controlled nesting can create resource-exhaustion risks.

Example: balanced delimiters

To check whether a string contains balanced parentheses, brackets, and braces, scan from left to right. Push opening delimiters. For a closing delimiter, the stack must be nonempty and its top must be the corresponding opener; otherwise the string is invalid. At the end, the stack must be empty. The algorithm runs in O(n) time and uses O(n) auxiliary space in the worst case.

7. Queues

A queue is a first-in, first-out (FIFO) ADT. Its operations commonly include enqueue, dequeue, front, and isEmpty. Queues model waiting lines, job scheduling, breadth-first search, event processing, and message delivery.

A naive array queue that removes from index 0 shifts every remaining element and therefore has O(n) dequeue cost. A better array implementation maintains front and rear indices, or uses a circular buffer. A linked queue maintains head and tail references, allowing enqueue at the tail and dequeue at the head in O(1).

Queues used in distributed systems require additional concerns: message acknowledgement, retry policy, ordering guarantees, back-pressure, visibility timeouts, and failure handling. The abstract FIFO property alone does not define these operational behaviours.

8. Deques

A deque, pronounced “deck,” supports insertion and deletion at both ends. Operations include addFirst, addLast, removeFirst, removeLast, and inspection of either end.

A deque can be implemented with a doubly linked list or a circular array. A doubly linked implementation provides O(1) end operations when endpoint references are maintained. A circular array provides compact storage and strong locality, but must distinguish full and empty states using size, a reserved slot, or separate index rules.

Deques support sliding-window algorithms, task schedulers, palindrome testing, browser navigation, and algorithms requiring both stack-like and queue-like behaviour.

9. Circular Buffers

A circular buffer is a fixed-capacity array whose logical end wraps to the beginning. It is particularly useful for streams, audio samples, logging, and producer-consumer pipelines.

Let capacity be C, with 0 ≤ size ≤ C. The next physical position is computed as:

The modulo operation is valid when C > 0. A buffer can maintain head, tail, and size. Enqueue writes at tail, advances tail, and increases size. Dequeue reads at head, advances head, and decreases size. Both operations are O(1).

An alternative representation leaves one slot unused. In that design, empty means head = tail, while full means next(tail) = head. The usable capacity is then C − 1. Mixing these conventions is a common source of bugs.

A circular buffer must define overflow behaviour: reject new data, overwrite the oldest data, block the producer, or expand dynamically. The correct choice depends on the application. Overwriting may be appropriate for telemetry where only the newest samples matter, but unacceptable for financial transactions.

10. Comparing Arrays and Linked Structures

The phrase “linked lists are better for insertion” is incomplete. Insertion is O(1) only after the insertion location or predecessor is known. If locating that position requires traversal, the overall operation can still be O(n). Similarly, dynamic arrays may outperform linked lists for many workloads because contiguous traversal benefits from caching and prefetching.

Caching and locality

Modern processors retrieve memory in cache lines rather than individual bytes. Sequential array traversal often uses each fetched line efficiently. Linked traversal may jump between unrelated addresses, producing cache misses and pointer-chasing delays. Arrays also use fewer allocations and may be friendlier to garbage collectors.

Locality is not an asymptotic complexity measure. Two O(n) algorithms can have very different real performance. Benchmarking should use representative data sizes, access patterns, language runtime conditions, and memory pressure.

11. Full-Stack Development Applications

Front end

Dynamic arrays underlie JavaScript arrays and many collection abstractions. They support rendering lists, storing form fields, and managing client-side state. Repeated insertion at the beginning can be expensive; a deque-like design or batched updates may be preferable.

Stacks support navigation history and nested UI state. Queues support event processing and asynchronous work. A debouncing or buffering component may use a circular buffer to retain recent events.

Back end

A request-processing service may use a queue between HTTP handlers and worker processes. A stack may support recursive parsing of JSON-like structures or route evaluation. Linked structures are useful when stable node references or frequent local removals are required, although many production systems prefer arrays or library collections for locality and simplicity.

Databases and caching

An LRU cache combines a hash map for O(1) average key lookup with a doubly linked list for O(1) promotion and eviction when the relevant node is already known. The map locates a cache entry; the list records recency order. In a concurrent implementation, synchronization must protect both structures so that they cannot disagree.

Streaming and real-time systems

Circular buffers provide bounded memory for logs, sensor readings, WebSocket messages, and media frames. Bounded buffers also enable back-pressure: producers must slow down or handle rejection when consumers cannot keep pace.

12. Worked Example: Designing a Request Buffer

Assume a service receives bursts of events and processes them with one worker. The requirements are FIFO ordering, bounded memory, O(1) insertion and removal, and explicit handling when the buffer is full.

A circular buffer with capacity C is appropriate. It stores head, tail, and size. Initially, head = 0, tail = 0, and size = 0. To enqueue x:

1. If size = C, apply the selected overflow policy.
2. Store x at position tail.
3. Set tail to (tail + 1) mod C.
4. Increase size by one.

To dequeue:

1. If size = 0, report that the buffer is empty.
2. Read the item at head.
3. Set head to (head + 1) mod C.
4. Decrease size by one.
5. Return the saved item.

Each operation performs a fixed number of index and assignment operations, so its time complexity is O(1). The memory complexity is O(C), where C is the fixed capacity. If events cannot be discarded, the service should block or apply back-pressure rather than overwrite data.

13. Illustrative Case Study: Full-Stack Notification Service

Background. An illustrative notification service receives account alerts from an API, processes them asynchronously, and displays recent delivery status in a web dashboard.

Problem. The initial implementation used a normal array and removed the first element after processing. As the queue grew, each removal shifted all remaining elements. Dashboard updates also retained every historical event, causing unnecessary memory growth.

Analysis. The queue required FIFO behaviour and bounded buffering. The dashboard required only the most recent 1,000 events. The array’s front-removal cost was O(n), and unlimited history created avoidable memory pressure.

Approach. The service replaced the processing queue with a circular buffer and defined a policy to reject or delay producers when full. The dashboard used a bounded deque: new events were added at the back and the oldest event was removed from the front when the limit was exceeded. A map keyed by notification identifier provided direct lookup for status updates. In production, access to these structures was coordinated because workers and status updates could run concurrently.

Outcome. Queue insertion and removal became O(1), memory use became predictable, and the dashboard maintained a fixed history limit. The design also made overload behaviour explicit rather than allowing silent memory growth.

Learning points. Data-structure selection must begin with operation requirements. A structure’s average or amortized complexity must be interpreted alongside locality, capacity, concurrency, and data-loss policies.

14. Correctness, Security, and Professional Practice

Linear structures can fail through off-by-one errors, stale references, incorrect empty/full detection, and inconsistent size counters. Testing should include empty, singleton, full, boundary-index, repeated-grow, repeated-shrink, and wraparound cases.

In security-sensitive software, attacker-controlled input can cause excessive allocation, deep nesting, queue flooding, or denial of service. Systems should impose limits on collection size, nesting depth, request rate, and buffer occupancy. Sensitive data should be removed or overwritten according to the language and threat model; merely deleting a reference does not guarantee immediate physical erasure from memory.

Concurrent access introduces races. A queue that updates head, tail, and size through separate unsynchronized operations can become corrupted. Use appropriate locks, atomic operations, ownership rules, or established concurrent-collection libraries. Lock-free structures require careful memory-order reasoning and are not automatically safer or faster.

Garbage-collected languages reduce manual deallocation errors but do not eliminate memory leaks: retaining references in arrays, caches, listeners, or queues can keep unreachable application objects alive. Resource limits and eviction policies remain necessary.

15. Contemporary Directions

Modern runtimes often optimize arrays internally, but performance depends on element types and access patterns. Homogeneous numeric arrays may use compact typed storage, while collections containing unrelated types may require boxed values or less predictable representations. Persistent data structures provide versions that share unchanged structure, supporting immutable application state, undo functionality, and concurrent reasoning, though updates may involve additional allocation.

High-performance systems increasingly use contiguous buffers, batch processing, and specialized memory layouts because locality and vectorization matter. In full-stack development, the practical trend is to use well-tested standard collections unless a measured workload justifies a custom representation.

Chapter Summary

Arrays provide constant-time indexed access and strong memory locality, but insertion and deletion away from the end require shifting. Dynamic arrays offer flexible growth and amortized constant-time append through geometric resizing, although individual resize operations are expensive. Matrices require careful attention to row-major or column-major layout and benefit from access patterns that match storage order.

Linked lists support local insertion and deletion with pointer updates, but indexed access, allocation overhead, and poor locality can reduce practical performance. Stacks implement LIFO behaviour, queues implement FIFO behaviour, and deques support both ends. Circular buffers provide bounded, O(1) queue-like operations with predictable memory use and explicit overflow policies.

The best structure depends on the complete workload: access patterns, ordering requirements, memory limits, locality, concurrency, and failure behaviour. In full-stack systems, these structures appear in user interfaces, parsers, request queues, caches, streaming components, and background workers. Correct boundary handling, capacity management, testing, and security limits are as important as asymptotic complexity.

Key Terms

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

Array: A contiguous indexed collection of elements.

Capacity: The number of elements a representation can store before expansion.

Circular buffer: A bounded array structure whose indices wrap around.

Deque: A double-ended queue supporting operations at both ends.

Dynamic array: An array abstraction that automatically resizes as needed.

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

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

Linked list: A sequence of nodes connected by references.

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

Matrix: A rectangular, indexed arrangement of values.

Node: A record containing a value and one or more links.

Queue: A FIFO abstract data type.

Sentinel: A dummy structural node used to simplify boundary handling.

Size: The number of logical elements currently stored.

Spatial locality: Efficient reuse of data located near recently accessed data.

Stack: A LIFO abstract data type.

Traversal: Visiting the elements of a structure according to a defined order.

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

Back-pressure: A mechanism that slows or limits producers when consumers cannot keep up.

Review Questions

Short Answer Questions

1. Why can an array provide O(1) indexed access?
2. Distinguish capacity from size in a dynamic array.
3. Why is deleting a known node from a doubly linked list O(1)?
4. What ordering principle does a queue implement?
5. State two ways a circular buffer can distinguish an empty state from a full state.

Long Answer Questions

1. Compare dynamic arrays and linked lists in terms of access, insertion, deletion, memory overhead, and locality.
2. Explain amortized O(1) append in a geometrically growing dynamic array.
3. Describe the implementation of a queue using a circular array, including wraparound and overflow.
4. Explain how an LRU cache can combine a hash map and a doubly linked list.
5. Discuss the correctness and security risks of unbounded stacks and queues in web services.

Analytical / Application Questions

1. A workload performs millions of sequential reads and occasional appends. Should it normally use a dynamic array or a linked list? Justify your decision using locality and operation costs.
2. Design a bounded event buffer for a real-time dashboard. Specify the structure, overflow policy, and behaviour when the consumer is slower than the producer.
3. A program repeatedly inserts and removes items at both ends but rarely accesses the middle. Compare a circular-array deque with a doubly linked deque and recommend one under a tight memory budget.

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 while preserving order

D. Searching an unsorted array

Correct Answer: A. Accessing an element by index

Question 2

Why does a dynamic array achieve amortized O(1) append under geometric growth?

A. Every append copies all elements

B. The total number of copied elements over many resizes is proportional to the number of appends

C. Resizing never requires allocation

D. Insertion always occurs at index zero

Correct Answer: B. The total number of copied elements over many resizes is proportional to the number of appends

Question 3

Which ordering principle characterizes a stack?

A. FIFO

B. Random order

C. LIFO

D. Priority order only

Correct Answer: C. LIFO

Question 4

What is the main advantage of maintaining both head and tail references in a linked queue?

A. Indexed access becomes O(1)

B. Enqueue and dequeue can both be O(1)

C. Nodes become contiguous

D. The queue cannot become empty

Correct Answer: B. Enqueue and dequeue can both be O(1)

Question 5

In a row-major matrix with c columns, what is the linear offset of element A[i][j] using zero-based indices?

A. i + j × c

B. i × c + j

C. i × j + c

D. c × c + i + j

Correct Answer: B. i × c + j

Question 6

What does a circular buffer use to move from position i to the next position in a capacity-C buffer?

A. i + C

B. i − C

C. (i + 1) mod C

D. i × C

Correct Answer: C. (i + 1) mod C

Question 7

Why can a linked list be slower than a dynamic array for traversal even when both traversals are O(n)?

A. Linked lists cannot be traversed

B. Linked lists always sort elements

C. Linked nodes may have poor spatial locality and incur pointer-chasing costs

D. Dynamic arrays use no memory

Correct Answer: C. Linked nodes may have poor spatial locality and incur pointer-chasing costs

Question 8

Which combination is commonly used to implement an LRU cache efficiently?

A. A stack and a matrix

B. A hash map and a doubly linked list

C. Two fixed arrays without indexes

D. A queue and a binary tree only

Correct Answer: B. A hash map and a doubly linked list

Question 9

A deque is best defined as an ADT that supports:

A. Insertion and deletion only in the middle

B. Access only by sorted key

C. Insertion and deletion at both ends

D. Only last-in, first-out removal

Correct Answer: C. Insertion and deletion at both ends

Question 10

What is a major security risk of an unbounded request queue exposed to users?

A. Improved cache locality

B. Denial of service through excessive memory consumption

C. Guaranteed FIFO violation

D. Automatic data encryption

Correct Answer: B. Denial of service through excessive memory consumption