Before talking about algorithm itself, we need to talk about data structures that typically uses for algorithms. Some of algorithms even works based on a specific data structure that optimizes the algorithm. In this chapter, I’ll explain the most common data structures only.

Array and list

Array

To store a number of data, there should be some data structure that can give a specific data you want anytime and store a data in to the storage either. To acheive this property, there is the easiest data structure known as an array. Like the name itself, it stores data in an array of storage. Pros of this algorithm is that you can get a data anytime from an array in a constant time because all you need is an index. In mathmatical format, it usually written as $a[0]$ or $a_0$. However, there is a big disadvantange for this. If you want to use an array, you need to know exact size of data you need. Otherwise, you may can access to the data where you didn’t meant to. Therefore, it has a big disadvantage known as the fixed-size. However, it can extend the array by making a new array and copy every element in side of the array. Therefore, complexity of an array is like follow.

Time complexity	Array
Search/Change	$O(1)$
Add (Front)	$O(n)$
Add (Random)	$O(n)$
Add (Back)	$O(n)$
Delete (Front)	$O(n)$
Delete (Random)	$O(n)$
Delete (Back)	$O(n)$
Merge	$O(n)$
Space complexity	$O(n)$

Notice that adding and delete will change the size of the array. Merge means that merging two array into a single array. It will be assumed to have the same size of two arrays.

List 1

To avoid this fixed-size problem, there is an alternative structure known as a list. A list consists of nodes. Each node has a data and a pointer to the next node. Therefore, it can access to next node from any node. However, it has a slow search algorithm because it can access only the next node. Therefore, it takes a linear time to read an array.

Time complexity	List 1
Search/Change	$O(n)$
Add (Front)	$O(1)$
Add (Random)	$O(n)$
Add (Back)	$O(n)$
Delete (Front)	$O(1)$
Delete (Random)	$O(n)$
Delete (Back)	$O(n)$
Merge	$O(n)$
Space complexity	$O(n)$

One other problem is that it can only add the new data without overhead at the front of the list. Therefore, there is another ways to make a list.

List 2

What if we make a pointer to denotes the last point of the list at the same time? It will gives an advantages that makes accessable at the end of the list. Therefore, it will give better performance when it works for the end of the list. At the same time, it has an advantage to merge two lists because it can connect the end point of a list to another list.

Time complexity	List 2
Search/Change	$O(n)$
Add (Front)	$O(1)$
Add (Random)	$O(n)$
Add (Back)	$O(1)$
Delete (Front)	$O(1)$
Delete (Random)	$O(n)$
Delete (Back)	$O(1)$
Merge	$O(1)$
Space complexity	$O(n)$

However, it still has $O(n)$ complexity for read/change operation. Therefore, it usually doesn’t be used in actual implementation however the notation of the list is typically used for many other data structures.

Other lists

There are another way to implement the list. Followings are the common thing that could be tried.

Double sizing array

Double sizing array works like an ordinary array but it increases its size by double when it requires a bigger size. It gives a nice performance because it gives a constant complexity for adding and deleting data at the back of the array. Notice that this is amortized analysis. Therefore, it sometimes takes long to add elements.

Time complexity	Vector
Search/Change	$O(1)$
Add (Front)	$O(n)$
Add (Random)	$O(n)$
Add (Back)	Amortized $O(1)$
Delete (Front)	$O(n)$
Delete (Random)	$O(n)$
Delete (Back)	Amortized $O(1)$
Merge	$O(n)$
Space complexity	$O(n)$

Circular array

To access the data, we can use virtual indexing map instead of accessing data by index directly. In other world, just use $a[f(i)]$ instead of $a[i]$ when accessing array $a$ at index $i$. Please notice that $f$ is a virtual map function. There are many potential for this virtual map. However, let’s just think about one of the simplest one. Let’s use $f(i) = (i + from) \mod size$. Notice that $from$ is a constant that can changes. In such a case, we can easily remove and insert the data at the front and the end like list 2 above. In this case, complexity works like below.

Time complexity	Array
Search/Change	$O(1)$
Add (Front)	$O(1)$
Add (Random)	$O(n)$
Add (Back)	$O(1)$
Delete (Front)	$O(1)$
Delete (Random)	$O(n)$
Delete (Back)	$O(1)$
Merge	$O(n)$
Space complexity	$O(n)$

Comparison

Complexity

DSA means the Double sizing array and CA means Circular array.

Time complexity	Array	List 1	List 2	DSA	CA
Search/Change	$O(1)$	$O(n)$	$O(n)$	$O(1)$	$O(1)$
Add (Front)	$O(n)$	$O(1)$	$O(1)$	$O(n)$	$O(1)$
Add (Random)	$O(n)$	$O(n)$	$O(n)$	$O(n)$	$O(n)$
Add (Back)	$O(n)$	$O(n)$	$O(1)$	Amortized $O(1)$	$O(1)$
Delete (Front)	$O(n)$	$O(1)$	$O(1)$	$O(n)$	$O(1)$
Delete (Random)	$O(n)$	$O(n)$	$O(n)$	$O(n)$	$O(n)$
Delete (Back)	$O(n)$	$O(n)$	$O(1)$	Amortized $O(1)$	$O(1)$
Merge	$O(n)$	$O(n)$	$O(1)$	$O(n)$	$O(n)$
Space complexity	$O(n)$	$O(n)$	$O(n)$	$O(n)$	$O(n)$

Example code

Here is the simple example of arrays.

#include <iostream>
#include <chrono>
#include <vector>

using namespace std;

template<typename T>
class linearArray;

template<typename T>
class circularArray;

template<typename T>
using array = circularArray<T>;

template<typename T>
class linearArray{
private:
    int _size;
    int _capacity;
    T* _data;
public: 
    linearArray(int capacity);

    ~linearArray();

    bool get(int idx, T& ret);        

    int capacity();

    int size();

    bool insert(int idx, T data);

    bool set(int idx, T data);

    bool erase(int idx);
};

template<typename T>
class circularArray{
private:
    int _size;
    int _capacity;
    T* _data;
    int _from;
    inline int vmap(int idx);
    void _push(int from, int to, bool left);
public: 
    circularArray(int capacity);

    ~circularArray();

    bool get(int idx, T& ret);
    
    int capacity();

    int size();

    bool insert(int idx, T data);

    bool set(int idx, T data);

    bool erase(int idx);
};

template<typename T>
linearArray<T>::linearArray(int capacity){
    _data = new T[capacity];
    _capacity = capacity;
    _size = 0;
}

template<typename T>
linearArray<T>::~linearArray(){
    delete[] _data;
}

template<typename T>
bool linearArray<T>::get(int idx, T& ret){
    if((0 <= idx) && (idx < _capacity)){
        ret = _data[idx];
        return true;
    } 
    return false;
}

template<typename T>
int linearArray<T>::capacity(){
    return _capacity;
}


template<typename T>
int linearArray<T>::size(){
    return _size;
}

template<typename T>
bool linearArray<T>::insert(int idx, T data){
    if(_size >= _capacity || idx >= _size + 1)
        return false;
    for(int i = _size - 1; i >= idx; --i)
        _data[i + 1] = _data[i];
    _data[idx] = data;
    ++_size;
    return true;
}

template<typename T>
bool linearArray<T>::set(int idx, T data){
    if(_size >= _capacity || idx >= _size + 1)
        return false;
    _data[idx] = data;
    return true;
}

template<typename T>
bool linearArray<T>::erase(int idx){
    if(_size == 0 || idx >= _size)
        return false;
    for(int i = idx; i < _size - 1; ++i)
        _data[i] = _data[i + 1];
    --_size;
    return true;
}


template<typename T>
inline int circularArray<T>::vmap(int idx){
    return (idx + _from + _capacity) % _capacity;
}

template<typename T>
void circularArray<T>::_push(int from, int to, bool left){
    if(from == to) return;
    //push array[from:to] to left if  is true, right if  is false
    //It assumed to be circular
    int _from = vmap(from);
    int _to = vmap(to);
    if(left){
        if(_from < _to){
            if(_from == 0)
                _data[_capacity - 1] = _data[0];
            else
                _data[_from - 1] = _data[_from];
            for(int i = _from + 1; i < _to; ++i)
                _data[i - 1] = _data[i];
            return;
        }
        //if(_from > _to)
        for(int i = _from; i < _capacity; ++i)
            _data[i - 1] = _data[i];
        if(_to != 0)
            _data[_capacity - 1] = _data[0];
        for(int i = 1; i < _to; ++i)
            _data[i - 1] = _data[i];
    
    }
    else{
        if(_from < _to){
            if(_to == _capacity)
                _data[0] = _data[_capacity - 1];
            else
                _data[_to] = _data[_to - 1];
            for(int i = _to - 2; i >= _from; --i)
                _data[i + 1] = _data[i];
            return;
        }
        //if(_from > _to)
        for(int i = _to - 1; i >= 0; --i)
            _data[i + 1] = _data[i];
        if(_to != 0)
            _data[0] = _data[_capacity - 1];
        for(int i = _capacity - 2; i >= _from; --i)
            _data[i + 1] = _data[i];
        return;


        for(int i = to - 1; i >= from; --i)
            _data[vmap(i + 1)] = _data[vmap(i)];
    }
}

template<typename T>
circularArray<T>::circularArray(int capacity){
    _data = new T[capacity];
    _capacity = capacity;
    _size = 0;
    _from = 0;
}

template<typename T>
circularArray<T>::~circularArray(){
    delete[] _data;
}

template<typename T>
bool circularArray<T>::get(int idx, T& ret){
    if((0 <= idx) && (idx < _capacity)){
        ret = _data[vmap(idx)];
        return true;
    } 
    return false;
}

template<typename T>
int circularArray<T>::capacity(){
    return _capacity;
}

template<typename T>
int circularArray<T>::size(){
    return _size;
}

template<typename T>
bool circularArray<T>::insert(int idx, T data){
    if(_size >= _capacity || idx >= _size + 1)
        return false;

    int mid = _size/2;
    if(idx < mid){
        _push(0,idx + 1, true);
        _from = (_from + _capacity - 1) % _capacity;
        _data[vmap(idx)] = data;
        ++_size;
        return true;
    }
    _push(idx, _size, false);
    _data[vmap(idx)] = data;
    ++_size;
    return true;
}

template<typename T>
bool circularArray<T>::set(int idx, T data){
    if(_size >= _capacity || idx >= _size + 1)
        return false;

    _data[vmap(idx)] = data;
    return true;
}

template<typename T>
bool circularArray<T>::erase(int idx){
    if(_size == 0 || idx >= _size)
        return false;
    
    int mid = _size/2;
    if(idx < mid){
        _push(0, idx, false);
        _from = (_from + 1) % _capacity;
        --_size;
        return true;
    }

    _push(idx + 1, _size, true);
    --_size;
    return true;
}

int main(){
    cout << "====================\n";
    cout << "    Basic array   \n";
    cout << "====================\n";
    {
        linearArray<int> lst1(10);
        for(int i = 0; i < 20; ++i){
            cout << lst1.insert(i, i) << " ";
        }cout << "\n";
        cout << "====================\n";
        for(int i = 0; i < lst1.size(); ++i){
            int data = -1;
            lst1.get(i, data);
            cout << data << " ";
        }cout << "\n";
        cout << "====================\n";
        cout << lst1.erase(0) << " ";
        cout << lst1.erase(0) << "\n";
        cout << "====================\n";
        for(int i = 0; i < lst1.size(); ++i){
            int data = -1;
            lst1.get(i, data);
            cout << data << " ";
        }cout << "\n";
        cout << "====================\n";
        cout << lst1.erase(5) << "\n";
        cout << "====================\n";
        for(int i = 0; i < lst1.size(); ++i){
            int data = -1;
            lst1.get(i, data);
            cout << data << " ";
        }cout << "\n";
        cout << "====================\n";
        cout << lst1.erase(6) << " ";
        cout << "\n";
        cout << "====================\n";
        for(int i = 0; i < lst1.size(); ++i){
            int data = -1;
            lst1.get(i, data);
            cout << data << " ";
        }cout << "\n";
        cout << "====================\n";
        cout << lst1.erase(5) << " ";
        cout << lst1.insert(0,11) << " ";
        cout << lst1.insert(0,12) << " ";
        cout << lst1.insert(0,13) << " ";
        cout << lst1.insert(0,14) << " ";
        cout << lst1.erase(9) << " ";
        cout << lst1.insert(6,13) << " ";
        cout << "\n";
        cout << "====================\n";
        for(int i = 0; i < lst1.size(); ++i){
            int data = -1;
            lst1.get(i, data);
            cout << data << " ";
        }cout << "\n";
    }

    cout << "====================\n";
    cout << "    Circular array   \n";
    cout << "====================\n";
    
    {    
        circularArray<int> lst2(10);
        for(int i = 0; i < 20; ++i){
            cout << lst2.insert(i, i) << " ";
        }cout << "\n";
        cout << "====================\n";
        for(int i = 0; i < lst2.size(); ++i){
            int data = -1;
            lst2.get(i, data);
            cout << data << " ";
        }cout << "\n";
        cout << "====================\n";
        cout << lst2.erase(0) << " ";
        cout << lst2.erase(0) << "\n";
        cout << "====================\n";
        for(int i = 0; i < lst2.size(); ++i){
            int data = -1;
            lst2.get(i, data);
            cout << data << " ";
        }cout << "\n";
        cout << "====================\n";
        cout << lst2.erase(5) << "\n";
        cout << "====================\n";
        for(int i = 0; i < lst2.size(); ++i){
            int data = -1;
            lst2.get(i, data);
            cout << data << " ";
        }cout << "\n";
        cout << "====================\n";
        cout << lst2.erase(6) << " ";
        cout << "\n";
        cout << "====================\n";
        for(int i = 0; i < lst2.size(); ++i){
            int data = -1;
            lst2.get(i, data);
            cout << data << " ";
        }cout << "\n";
        cout << "====================\n";
        cout << lst2.erase(5) << " ";
        cout << lst2.insert(0,11) << " ";
        cout << lst2.insert(0,12) << " ";
        cout << lst2.insert(0,13) << " ";
        cout << lst2.insert(0,14) << " ";
        cout << lst2.erase(9) << " ";
        cout << lst2.insert(6,13) << " ";
        cout << "\n";
        cout << "====================\n";
        for(int i = 0; i < lst2.size(); ++i){
            int data = -1;
            lst2.get(i, data);
            cout << data << " ";
        }cout << "\n";
    }

    cout << "====================\n";
    cout << "    Performance    \n";
    cout << "====================\n";
    
    cout << "    Insert first    \n";
    {
        linearArray<int> array(10000);
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.insert(0,10);
        }
        auto to = std::chrono::system_clock::now();
        cout << " Regular array  : " << (to - from).count()   << "\n";
    }
    {
        circularArray<int> array(10000);
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.insert(0,10);
        }
        auto to = std::chrono::system_clock::now();
        cout << " Circular array : " << (to - from).count()   << "\n";
    }
    {
        std::vector<int> array(10000);
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.insert(array.begin(),10);
        }
        auto to = std::chrono::system_clock::now();
        cout << " std::vector : " << (to - from).count()   << "\n";
    }

    cout << "====================\n";
    cout << "    Erase first    \n";
    {
        linearArray<int> array(10000);
        for(int i = 0; i < 10000; ++i){
            array.insert(i,10);
        }
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.erase(0);
        }
        auto to = std::chrono::system_clock::now();
        cout << " Regular array  : " << (to - from).count()   << "\n";
    }
    {
        circularArray<int> array(10000);
        for(int i = 0; i < 10000; ++i){
            array.insert(i,10);
        }
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.erase(0);
        }
        auto to = std::chrono::system_clock::now();
        cout << " Circular array : " << (to - from).count()   << "\n";
    }
    {
        std::vector<int> array(10000);
        for(int i = 0; i < 10000; ++i){
            array.insert(array.begin()+i,10);
        }
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.erase(array.begin());
        }
        auto to = std::chrono::system_clock::now();
        cout << " std::vector : " << (to - from).count()   << "\n";
    }
    

    cout << "====================\n";
    cout << "    Insert middle    \n";
    {
        linearArray<int> array(10000);
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.insert(i/2,i);
        }
        auto to = std::chrono::system_clock::now();
        cout << " Regular array  : " << (to - from).count()   << "\n";
    }
    {
        circularArray<int> array(10000);
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.insert(i/2,i);
        }
        auto to = std::chrono::system_clock::now();
        cout << " Circular array : " << (to - from).count()   << "\n";
    }
    {
        std::vector<int> array(10000);
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.insert(array.begin()+i/2,i);
        }
        auto to = std::chrono::system_clock::now();
        cout << " std::vector : " << (to - from).count()   << "\n";
    }

    cout << "====================\n";
    cout << "    Erase  middle    \n";
    {
        linearArray<int> array(10000);
        for(int i = 0; i < 10000; ++i){
            array.insert(i,i);
        }
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.erase(i/2);
        }
        auto to = std::chrono::system_clock::now();
        cout << " Regular array  : " << (to - from).count()   << "\n";
    }
    {
        circularArray<int> array(10000);
        for(int i = 0; i < 10000; ++i){
            array.insert(i,i);
        }
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.erase(i/2);
        }
        auto to = std::chrono::system_clock::now();
        cout << " Circular array : " << (to - from).count()   << "\n";
    }
    {
        std::vector<int> array(10000);
        for(int i = 0; i < 10000; ++i){
            array.insert(array.begin()+i,i);
        }
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.erase(array.begin()+i/2);
        }
        auto to = std::chrono::system_clock::now();
        cout << " std::vector : " << (to - from).count()   << "\n";
    }
    

    cout << "====================\n";
    cout << "    Insert random    \n";
    {
        linearArray<int> array(10000);
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.insert(rand()%(i + 1),i);
        }
        auto to = std::chrono::system_clock::now();
        cout << " Regular array  : " << (to - from).count()   << "\n";
    }
    {
        circularArray<int> array(10000);
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.insert(rand()%(i + 1),i);
        }
        auto to = std::chrono::system_clock::now();
        cout << " Circular array : " << (to - from).count()   << "\n";
    }
    {
        std::vector<int> array(10000);
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.insert(array.begin()+rand()%(i + 1),i);
        }
        auto to = std::chrono::system_clock::now();
        cout << " std::vector : " << (to - from).count()   << "\n";
    }

    cout << "====================\n";
    cout << "    Erase  random    \n";
    {
        linearArray<int> array(10000);
        for(int i = 0; i < 10000; ++i){
            array.insert(i,i);
        }
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.erase(rand()%(10000 - i));
        }
        auto to = std::chrono::system_clock::now();
        cout << " Regular array  : " << (to - from).count()   << "\n";
    }
    {
        circularArray<int> array(10000);
        for(int i = 0; i < 10000; ++i){
            array.insert(i,i);
        }
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.erase(rand()%(10000 - i));
        }
        auto to = std::chrono::system_clock::now();
        cout << " Circular array : " << (to - from).count()   << "\n";
    }
    {
        std::vector<int> array(10000);
        for(int i = 0; i < 10000; ++i){
            array.insert(array.begin()+i,i);
        }
        auto from = std::chrono::system_clock::now();
        for(int i = 0; i < 10000; ++i){
            array.erase(array.begin()+rand()%(10000 - i));
        }
        auto to = std::chrono::system_clock::now();
        cout << " std::vector : " << (to - from).count()   << "\n";
    }
    return 0;
}

Performance

Performance depends on the experiment environment. I tested in my raspberry PI and results looks like as belows.

Without compiler optimization option

Time consumption	Basic array	Circular array	std::vector	Basic/Circular	std/circular
Insert first	5.43E+08	730299	80218289	743.5641	109.8431
Erase first	5.07E+08	249735	77053027	2030.535	308.5392
Insert middle	2.72E+08	2.63E+08	64868023	1.03441	0.246638
Erase middle	3.69E+08	93046427	60962537	3.963127	0.655184
Insert random	2.69E+08	1.32E+08	67554999	2.028211	0.510193
Erase random	2.79E+08	1.34E+08	61448193	2.081033	0.457566

With compiler optimization option

Time consumption	Basic array	Circular array	std::vector	Basic/Circular	std/circular
Insert first	69745452	243124	72715663	286.8719	299.0888
Erase first	19728613	352	70335698	56047.2	199817.3
Insert middle	28044463	33800611	58150249	0.829703	1.72039
Erase middle	13088558	7911878	58191397	1.654292	7.354941
Insert random	29029662	11617777	59405666	2.498728	5.113342
Erase random	9968517	11553333	57890608	0.862826	5.010728