CODEWITHSUNDEEP
algorithmqueueimplementationabstract-data-type
NoName
NoName

Reputation: 10334

How to create a simple circular array?

According to my textbook, realizations of Queue ADT can be done:

How do you create a simple circular array? I'm not sure if it's widely used. Is it just a linked list where the last item points back to the first item?

Upvotes: 3

Views: 3669

Answers (2)

Eric
Eric

Reputation: 24944

For Java (and similar in many other languages), there are 2 choices:

  • Fixed size, with Object[] as internal storage.
    Methods: size() / rotate() / get(index) / set(index, value)
  • Flexible size, with ArrayList<T> as internal storage.
    In additional to what fixed size version can do, it also could add(value) / add(index, value) / remove(index) / remove(value) / indexOf(index) / lastIndexOf(index).

Tips:

  • Linked list is not a good choice, due to slow accessing elements via index.
  • Both choices use a int head to point to the circular index.
    Need to maintain it, and convert between it and the internal structure's real index in various operations.

Upvotes: 0

CR Drost
CR Drost

Reputation: 9817

There are several examples of ring buffers and design tradeoffs associated with them on Wikipedia.

The simplest example would in TypeScript be:

class RingBuffer<T> {
  private backing: Array<T>;
  private size: number;
  private start: number;
  get length(): number {
    return this.size;
  }
  constructor(private maxSize: number) {
    this.backing = [];
    this.start = 0;
    this.size = 0;
  }
  public push(...ts: Array<T>): number {
    if (this.size + ts.length > this.maxSize) {
      throw new Error('Ring overflow error.');
    }
    for (const t of ts) {
      this.backing[(this.start + this.size) % this.maxSize] = t;
      this.size++;
    }
    return this.size;
  }
  public shift() {
    if (this.size === 0) {
      throw new Error('No such element.');
    }
    this.size--;
    const val = this.backing[this.start];
    this.start = (this.start + 1) % this.maxSize;
    return val;
  }
  public pop() {
    if (this.size === 0) {
      throw new Error('No such element.');
    }
    this.size--;
    return this.backing[(this.start + this.size) % this.maxSize];
  }
}

The basic idea is that it is a fixed-size array which uses a little bit of pointer math to loop back around to the beginning as you try to fill it up more and more; it may or may not do bounds checking the way that the above does.

Upvotes: 4

Related Questions