Removing An Element In A Circular Arrays

Table of contents
1.
2.
3.
4.
5.
6.
7.
8.

Introduction
Moving a cursor forward and backward
Iteration over the elements in a circular array
Linearizing a circular array
Resizing a circular array
Inserting an element in a circular array
Removing an element in a circular array
Questions to ponder

Introduction
In a ``normal'' linear array, the first available slot is at index 0, the second one at index 1, and so on until the last one at index a rr.length - 1 (where a rr is a reference to the array in question). We cannot start before the first slot at index 0, and we must stop at the last slot at index a rr.length - 1 — any attempt to access a slot at i ndex < 0 or at i ndex >= arr.length will cause an
ArrayIndexOutOfBoundsException to be thrown.
We iterate over the elements the array in the usual way by advancing a cursor from the first slot to the last. We iterate backwards in a similar way. for (int i = 0; i < size; i++) visit(arr[i]); for (int i = size - 1; i >= 0; i--) visit(arr[i]); where s ize ≤ a rr.length is the number of elements in the linear array.
In a circular array (also called circular buffer), the end of the array wraps around to the start of the array, just like in musical chairs. Simply watch the second hand of a watch go from 0 to 5 9 , and then wrap around to 0 again, and you see a circular array at work. You should note that we create the perception of a circular array — the underlying data is still kept in a linear array with a start (at index 0 ) and an end (at index a rr.length - 1 ). We implement the circularity by manipulating the indices such that when we advance past the end of the underlying array, the cursor wraps around to the beginning again. Similarly, when we go past the beginning going backwards, the cursor wraps around to the end of the array. Basically, we ``fake'' the concept of a circular array on top of a ``normal'' linear array. The following shows a linear array with a capacity of 8, and with 6 elements in it. The start index is assumed to be 0 . The next available slot is at index s ize or 6 , given by s tart + size = 0 + 6 =
6 . The last element is in the slot at index s ize - 1 or 5 , given by s tart + size - 1 = 0 + 6 1 = 5.
0
1
2
3
4
5
6
7
---------------------------------------capacity = 8
| 5 | 7 | 9 | 15 | -4 | 17 |
|
| size =6
---------------------------------------^-- nextAvailPos = size

In an equivalent circular array of the same capacity and with the same elements, the first element may start at any index, not necessarily at index 0 . For example, the following circular arrays are both equivalent to each other, and to the linear array shown above.
0
1
2
3
4
5
6
7
---------------------------------------capacity = 8
| 5 | 7 | 9 | 15 | -4 | 17 |
|
| size =6
---------------------------------------^-- start
^-- nextAvailPos
0
1
2
3
4
5
6
7
---------------------------------------capacity = 8
|
| 5 | 7 | 9 | 15 | -4 | 17|
|
size
=6
---------------------------------------^-- start
^-- nextAvailPos
0
1
2
3
4
5
6
7
---------------------------------------| 15| -4 | 17 |
|
|5
|7|9|
---------------------------------------nextAvailPos --^
^-- start

Back to Table of contents

capacity = 8 size =6

Moving a cursor forward and backward
Before going to iteration, let's take a look at how to advance an cursor (in both directions) in linear and circular arrays. In a linear array, moving an cursor i forward and backward by unit stride are simply:
Forward

Backward

i++, or i = i + 1, or i += 1

i--, or i = i - 1, or i -= 1

With the understanding that i < 0 and i ≥ a rr.length are invalid indices.
In a circular array, moving moving an cursor i forward (or advancing the cursor) is accomplished by first advancing it normally, and then wrapping it if necessary. i++; if (i == arr.length) i = 0;

It can also be done using modular arithmetic, by using the

Show More

Essay about Focal Length and Lens

lab 1 Essay

San Tutorial Essay

Reflex and Special Senses Essay

978 1 4020 5233 0 SolutionsManual Essay

Request To Establish A Code For Sodium Tetradecyl Sulfate

AP Stats Vocab List 2 Essay

Cognitive Radio And Networking Research At Virginia Tech