1. Arrays

An array is a structure of fixed-size, which can hold items of the same data type. Arrays are indexed, meaning that random access is possible. An array is usually presented as a native data structure in many programming languages. However, one shall not confuse array with the list like data structures in languages like python. Let us see arrays are presented in C++;

// simple declaration
int array[] = {1, 2, 3, 4, 5 };
// in pointer form (refers to an object stored in heap)
int * array = new int[5];

However, we are accustomed to the more friendly vector data structure to which we can push without worrying about the size. Let us see how we can implement one of our own list like data structures that will resize on its own.

using namespace std;

class DynamicArray
{
private:
    int size_;
    int max_;
    int *arrayholder_;

public:
    DynamicArray()
    {
        this->size_ = 0;
        this->max_ = 5;
        this->arrayholder_ = new int[5];
    }

    ~DynamicArray()
    {
        delete[] this->arrayholder_;
    }

    int size()
    {
        return this->size_;
    }

    int& operator[](int i) 
    {
        assert(i < this->size_);
        return this->arrayholder_[i];
    }

    void add(int n)
    {
        if (this->max_ < this->size_ + 1)
        {
            this->max_ *= 2;
            int *tmp_ = new int[this->max_];

            for (size_t i = 0; i < this->size_; i++)
            {
                tmp_[i] = this->arrayholder_[i];

            }
            delete[] this->arrayholder_;
            this->arrayholder_ = tmp_;
            this->arrayholder_[this->size_] = n;
            this->size_ += 1;
        }
        else 
        {
            this->arrayholder_[this->size_] = n;
            this->size_ += 1;
        }
    }
};

int main(int argc, char **argv)
{
    DynamicArray darray;
    vector<int> varray;

    for (size_t i = 0; i <= 15; i++)
    {
        darray.add(i);
    }
    return 0;
}

We can see that the above DynamicArray has an initial size of 5. Also in the add function, we can see that if we have reached the max capacity, the array size is doubled and copied. This is how vector data structure works in reality. Usually, the base size is around 30. Knowing this could come in handle in an interview.

One more thing to note is that we are using both constructors and destructors. This is because we have a pointer to memory that we allocate as the array expands. This allocated memory must be released to avoid overflows. The beauty of this implementation is that the user does not have to know anything about the ugly pointers. Overloading the operator[] allows indexed access like a native array. Having this knowledge, let us move on to our next data structure, linked lists.

2. Linked Lists

A linked list is a sequential structure that consists of a sequence of items in linear order which are linked to each other. You are only required to know one end of the chain to traverse through this data structure. In a scenario where the size changes frequency, using an array might not be advantageous unless data is accessed randomly (expansions can cause higher copy times and use more memory unless you implement a shrink operation). So a linked list can be considered as a data structure that supports frequent size variations and sequential access.

Let us have a look at our implementation.

using namespace std;

template <typename T>
class Node
{
    public:
    T value;
    Node *next;
    Node *previous;

    Node(T value)
    {
        this->value = value;
    }
};

template <typename T>
class LinkedList
{
    private:
    int size_;
    Node<T> *head_ = NULL;
    Node<T> *tail_ = NULL;
    Node<T> *itr_ = NULL;

    public:
    LinkedList()
    {
        this->size_ = 0;
    }

    void append(T value)
    {
        if (this->head_ == NULL)
        {
            this->head_ = new Node<T>(value);
            this->tail_ = this->head_;
        }
        else
        {
            this->tail_->next = new Node<T>(value);
            this->tail_->next->previous = this->tail_;
            this->tail_ = this->tail_->next;
        }
        this->size_ += 1;
    }

    void prepend(T value)
    {
        if (this->head_ == NULL)
        {
            this->head_ = new Node<T>(value);
            this->tail_ = this->head_;
        }
        else
        {
            this->head_->previous = new Node<T>(value);
            this->head_->previous->next = this->head_;
            this->head_ = this->head_->previous;
        }
        this->size_ += 1;
    }

    Node<T> * iterate()
    {
        if (this->itr_ == NULL) 
        {
            this->itr_ = this->head_;
        } 
        else 
        {
            this->itr_ = this->itr_->next;
        }
        return this->itr_;
    }

    T ptr()
    {
        return this->itr_->value;
    }

    void resetIterator()
    {
        this->tail_ = NULL;
    }
};


int main(int argc, char **argv)
{
    LinkedList<int> llist;
    llist.append(10);
    llist.append(12);
    llist.append(14);
    llist.append(16);
    llist.prepend(5);
    llist.prepend(4);
    llist.prepend(3);
    llist.prepend(2);
    llist.prepend(1);

    cout << "Printing Linked List" << endl;

    while(llist.iterate() != NULL)
    {
        cout << llist.ptr() << "\t";
    }
    cout << endl;

    return 0;
}

Here we are using a support structure called a Node. This Node will carry pointers to next item and the previous item. Usually having the next item is sufficient. But having both next and previous can increase append and prepend performance as we have O(1) access to both ends. Appending means we will update the tail pointer’s next element followed by updating tail to be the added item. Conversely, prepending would create a new element and set its next item to be the current head. Note that I have not included memory cleanup operations since we aren’t dealing with explicit deletions and to make code more simple. However, one must have them in a separate destructor to avoid memory leaks. Also, we are using a simple iterator just to print items.

3. Stacks

A stack is a LIFO (Last In First Out — the element placed at last can be accessed at first) structure. Although this data structure has a different behaviour, this can be considered as a derivation of the linked list with only a head or access to the top element.

#include <iostream>

using namespace std;

template <typename T>
class Node
{
public:
    T value;
    Node *next;

    Node(T value)
    {
        this->value = value;
    }
};

template <typename T>
class Stack
{
private:
    int size_;
    Node<T> *top_ = NULL;
    Node<T> *itr_ = NULL;

public:
    Stack()
    {
        this->size_ = 0;
    }

    void push(T value)
    {
        if (this->top_ == NULL)
        {
            this->top_ = new Node<T>(value);
        }
        else
        {
            Node<T> *tmp = new Node<T>(value);
            tmp->next = this->top_;
            this->top_ = tmp;
        }
        this->size_ += 1;
    }

    Node<T> *pop()
    {
        Node<T> *tmp = this->top_;

        this->top_ = this->top_->next;
        this->size_ -= 1;        return tmp;
    }

    Node<T> *peek()
    {
        return this->top_;
    }

    int size()
    {
        return this->size_;
    }

    Node<T> *iterate()
    {
        if (this->itr_ == NULL)
        {
            this->itr_ = this->top_;
        }
        else
        {
            this->itr_ = this->itr_->next;
        }
        return this->itr_;
    }

    T ptr()
    {
        return this->itr_->value;
    }

    void resetIterator()
    {
        this->itr_ = NULL;
    }
};

int main(int argc, char **argv)
{
    Stack<int> stk1;
    stk1.push(10);
    stk1.push(12);
    stk1.push(14);
    stk1.push(16);
    stk1.push(5);
    stk1.push(4);
    stk1.push(3);
    stk1.push(2);
    stk1.push(1);

    cout << "Printing Stack" << endl;

    while (stk1.iterate() != NULL)
    {
        cout << stk1.ptr() << "\t";
    }
    cout << endl;    return 0;
}

Note that the Node has only a reference to the next item. Adding an item would update the top of the data structure. Furthermore, removal and retrieval are done from the top as well. For this, we use pop() and top() methods respectively.

4. Queues

A queue is a FIFO ( First In First Out — the element placed at first can be accessed at first ) structure. This can be considered as the reverse scenario of the stack. In simpler terms, it is a linked list where we add from one end read from the other end. This emulates the real-world line-up at a driveway. Here we can think of a Node structure as follows.

template <typename T>
class Node
{
    public:
    T value;
    Node *next;
    Node *previous;

    Node(T value)
    {
        this->value = value;
    }
};

The main data structure would be;

template <typename T>
class Queue
{
    private:
    int size_;
    Node<T> *head_ = NULL;
    Node<T> *tail_ = NULL;

    public:
    Queue()
    {
        this->size_ = 0;
    }

    void enqueue(T value)
    {
        if (this->head_ == NULL)
        {
            this->head_ = new Node<T>(value);
            this->tail_ = this->head_;
        }
        else
        {
            this->tail_->next = new Node<T>(value);
            this->tail_->next->previous = this->tail_;
            this->tail_ = this->tail_->next;
        }
        this->size_ += 1;
    }

    Node<T> dequeue()
    {
        Node<T> *tmp = this->tail_;

        this->tail_ = this->tail->previous;
        this->tail_->next = NULL;        this->size_ -= 1;        return tmp;
    }
};

Final Thoughts

We have implemented 4 common data structures using the C++ programming language. I will present the remaining implementations in a future article.

Hope you all found these C++ implementations of arrays, linked lists, stacks and queues useful.

Data Structures in C++

1. Arrays

2. Linked Lists

3. Stacks

4. Queues

Final Thoughts