Circular Arrays

Abstract

A Circular Array is a regular Array List with an implementation that mimics the boundary properties of a Linked List. It treats the underlying linear array as a continuous ring by tracking head and tail indices.

• Head/Tail Indices: Instead of starting at index 0, the first element sits at the head index and the last sits at the tail index.
• Contiguity: Elements remain contiguous in logical sequence, even when wrapping across physical array boundaries.

---

Wrapping Logic

• Add to End: Increment tail. If it hits the physical end of the array, it wraps back to index 0.
• Add to Front: Decrement head. If it hits -1, it wraps to the final index ($\text{capacity}-1$).

---

System Representations

There are two primary ways to conceptualize a Circular Array. Both are equally valid and describe the same underlying logic.

1. The Physical (Linear) View

This representation illustrates how data literally sits in computer memory addresses. The head and tail indices move across the flat array, wrapping around upon hitting boundaries.

• Wrap to Front: If tail reaches capacity, it wraps to index 0.
• Wrap to Back: If head drops below 0, it wraps to index $\text{capacity}-1$.

2. The Logical (Circular) View

Since operational focus centers on an element’s location relative to head and tail, it is often visualized as a continuous ring structure.

---

Insertion and Resizing

When the backing array becomes fully saturated, it must be resized. Similar to a standard Array List, the engine doubles array capacity and copies existing entries.

During a resize operation, the circular layout must be “unrolled” so the new array begins with the head element aligned at physical index 0.

Algorithm 13 Circular Array Operations

procedure CheckSize(array, head, tail, n)

if $n == array.\text{length}$ then

$newArray \gets \text{Allocate empty array of length } 2 \cdot array.\text{length}$

for $i \gets 0 \text{ to } n - 1$ do

$newArray[i] \gets array[(head + i) \pmod{array.\text{length}}]$

$array \gets newArray$

$head \gets 0$

$tail \gets n - 1$

procedure InsertFront(element, array, head, n)

CheckSize(array, head, tail, n)

$head \gets head - 1$

if $head == -1$ then

$head \gets array.\text{length} - 1$

$array[head] \gets element$

$n \gets n + 1$

procedure InsertBack(element, array, tail, n)

CheckSize(array, head, tail, n)

$tail \gets tail + 1$

if $tail == array.\text{length}$ then

$tail \gets 0$

$array[tail] \gets element$

$n \gets n + 1$

---

Removal Operations

• Remove Front: Erase the element at head and increment the head index (wrapping if necessary).
• Remove Back: Erase the element at tail and decrement the tail index (wrapping if necessary).

Algorithm 14 Circular Array Removal

procedure RemoveFront(array, head, n)

$head \gets (head + 1) \pmod{array.\text{length}}$

$n \gets n - 1$

procedure RemoveBack(array, tail, n)

$tail \gets tail - 1$

if $tail == -1$ then

$tail \gets array.\text{length} - 1$

$n \gets n - 1$

Memory Cleanup Considerations

Explicitly clearing unlinked array slots during removal is usually unnecessary because values are overwritten by future insertions. However, if the array stores raw pointers in non-garbage-collected environments, elements must be explicitly deallocated to prevent memory leaks.

---

Finding and Random Access

Unlike a Linked List, a Circular Array retains $O(1)$ Random Access capabilities. To access logical element $i$, calculate its physical index via modular arithmetic:

$\text{Physical Index}=(head+i)(\mathrm{mod}array.\text{length})$

Modulo Omission Optimization

Modulo arithmetic can be bypassed whenever $(head+i)<array.\text{length}$, speeding up raw index calculations.

---

Performance Summary

• Random Access: $O(1)$ achieved via modular offset arithmetic.
• Insert/Remove Front: $O(1)$ requiring zero data shifting.
• Insert/Remove Back: $O(1)$ direct index pointer adjustment.
• Resize Complexity: $O(n)$ occurring infrequently (amortized $O(1)$).

Conclusion: Circular Arrays provide the efficient boundary manipulation of a Linked List while retaining the constant-time random access of an Array List. This makes them ideal for backing Deques and Queues.

---

Related Notes

• Array Lists
• Linked List
• Deques
• Queues