Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

Data access functions: Set, Get, InsertAt, RemoveAt

Dynamic array data structure encapsulates underlying storage, but the interface must provide access functions to work with it. We can also add range check to the access functions.

Range check

There is no much to say about the range check. Algorithm checks, whether index is inside the 0..size-1 range and if not, throws an exception.

Get and set

After we ensured, that index is inside of the proper range, write a value to the storage or read a value from the storage.

InsertAt

This operation may require array expanding, so algorithm invokes ensure capacity method first, which should ensure size + 1 minimal capacity. Then shift all elements from i to size - 1, where i is the insertion position, one element right. Note, that if new element is inserted after the last element in the array, then no shifting required. After shifting, put the value to i-th element and increase size by one.

insert at example, pic. 1
insert at example, pic. 2
insert at example, pic. 3

RemoveAt

Shift all elements from i to size - 1, where i is the removal position, one element left. Then decrease size by 1 and invoke pack opeartion. Packing is done, if there are too few elements left after removal.

remove at example, pic. 1
remove at example, pic. 2
remove at example, pic. 3

Code snippets

Java 

public class DynamicArray {

     

 

      private void rangeCheck(int index) {

            if (index < 0 || index >= size)

                  throw new IndexOutOfBoundsException("Index: " + index + ", Size: "

                             + size);

      }

     

      public void set(int index, int value)

      {

            rangeCheck(index);

            storage[index] = value;

      }

     

      public int get(int index)

      {

            rangeCheck(index);

            return storage[index];

      }

 

      public void removeAt(int index) {

            rangeCheck(index);

            int moveCount = size - index - 1;

            if (moveCount > 0)

                  System.arraycopy(storage, index + 1, storage, index, moveCount);

            size--;

            pack();

      }

 

      public void insertAt(int index, int value) {

            if (index < 0 || index > size)

                  throw new IndexOutOfBoundsException("Index: " + index + ", Size: "

                             + size);

            ensureCapacity(size + 1);

            int moveCount = size - index;

            if (moveCount > 0)

                  System.arraycopy(storage, index, storage, index + 1, moveCount);

            storage[index] = value;

            size++;

      }

}

C++

#include <cstring>

#include <exception>

 

void DynamicArray::rangeCheck(int index) {

      if (index < 0 || index >= size)

            throw "Index out of bounds!";

}

 

void DynamicArray::set(int index, int value) {

      rangeCheck(index);

      storage[index] = value;

}

 

int DynamicArray::get(int index) {

      rangeCheck(index);

      return storage[index];

}

 

void DynamicArray::removeAt(int index) {

      rangeCheck(index);

      int moveCount = size - index - 1;

      if (moveCount > 0)

            memmove(storage + index, storage + (index + 1), sizeof(int) * moveCount);

      size--;

      pack();

}

 

void DynamicArray::insertAt(int index, int value) {

      if (index < 0 || index > size)

            throw "Index out of bounds!";

      ensureCapacity(size + 1);

      int moveCount = size - index;

      if (moveCount != 0)

            memmove(storage + index + 1, storage + index, sizeof(int) * moveCount);

      storage[index] = value;

      size++;

}

Contribute to AlgoList

Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.


Every dollar helps!

Leave a reply

Your name (optional):
Your e-mail (optional):
Message: