Dynamic Array

Data Structures

avgO(n)worstO(n)spaceO(n)

An array holding 6 values in 8 slots

1 / 33

Code

class DynamicArray {  data: number[] = new Array(8);  size = 0;  insert(index: number, value: number) {    if (this.size === this.data.length) this.grow();    for (let k = this.size; k > index; k--) {      this.data[k] = this.data[k - 1];    }    this.data[index] = value;    this.size++;  }  delete(index: number) {    for (let k = index; k < this.size - 1; k++) {      this.data[k] = this.data[k + 1];    }    this.size--;  }  search(value: number) {    for (let k = 0; k < this.size; k++) {      if (this.data[k] === value) return k;    }    return -1;  }  private grow() {    const bigger = new Array(this.data.length * 2);    for (let k = 0; k < this.size; k++) bigger[k] = this.data[k];    this.data = bigger;  }}

structure DynamicArray  data ← array of capacity 8  size ← 0  procedure insert(index, value)    if size = capacity then grow()    for k ← size down to index + 1 do      data[k] ← data[k − 1]    ▷ shift right    end for    data[index] ← value    size ← size + 1  end procedure  procedure delete(index)    for k ← index to size − 2 do      data[k] ← data[k + 1]    ▷ shift left    end for    size ← size − 1  end procedure  procedure search(value)    for k ← 0 to size − 1 do      if data[k] = value then return k    end for    return −1  end procedure  procedure grow()    bigger ← array of capacity 2 × capacity    copy data[0..size) into bigger    data ← bigger  end procedureend structure

Variables

size=6capacity=8

Counters

shifts: 0
resizes: 0

Starting contents6 values

Operations5 / 40

1. insert(50 @ 2)
2. delete(@ 0)
3. insert(31 @ 6)
4. insert(74 @ 1)
5. search(23)

How it works

A contiguous block of slots with a size and a capacity. Inserting or deleting in the middle shifts every later element one slot over, and a full array doubles its capacity. That keeps appends at amortised O(1), while edits in the middle cost O(n).

Complexity

Best: O(1)
Average: O(n)
Worst: O(n)
Space: O(n)

Dynamic Array

How it works

Complexity

Search algorithms