We use arrays all the time in programming. But did you ever wonder what goes on under the hood and how they work?

What is an array?

An array is a contiguous area of memory consisting of equal-size elements indexed by contiguous integers. Which is just a fancy way of all an an array’s elements are stored together right beside each other in memory.

What is so about them?

Arrays are great at random access. Meaning you can easily access any element at any time so long as you know the index of the element you want.

What are some it’s weaknesses?

While most people don’t have to worry about this, arrays can be a little wasteful on space. If you create a large array and don’t use most of it’s elements, you are wasting space. That’s one down side.

The other is arrays suffer from the same thing linked lists do. They aren’t great at doing this in the middle.

common-array-times.PNG

Whenever you need to add or remove elements in the middle of an array you need to shuffle everything around to make sure you don’t have any gaps.

How to arrays resize themselves?

When you create an array you, usually need to give it a default size. For the Java ArrayList this size is 10.

Once you approach that limit, the array needs to make itself bigger. Usually by doubling itself in size.

resize.PNG

Once it doubles in size, it creates a new array, copies the old values over, and gets rid of the old one.

An example

Here are some common array operations

Get(i) return element at location i
Set(i, value) Sets element i to value
PushBack(value) Adds value to the end
Remove(i) Removes element at location i
Size(i) the number of elements

And here is an examples of how an array works, minus all the error checking for array size and bounds.

Initialization

initialize.PNG
When you create an array, you often specify some default or initial capacity. You also want to track its size, along with the data contained in the array itself.

Get / Set

Getting and setting are the easiest operations to do on an array. All you are doing is access your internal data store and then returning (or setting) whatever element lies there. Normally you would do some bounds checking here too but I have left those out for clarity.

get-set.PNG

PushBack

This is where things get slightly more interesting for an array. So long as your array hasn’t reached it’s limit, all you need do is set your new value to the array index at position size and you are done.

pushback.PNG

But if you are at your limit, this is where we double our array size, copy the old data over, and double our capactity.

Remove

And remove is kind of neat. Here you are removing an element at a specific position, and to do that you need to jump into your array at the position of the element you want to remove, and then slide all the other elements above it down (while not forgetting to decrease your array size)

remove.PNG

So what is better? An linked list or an array?

Linked lists are pretty similar to arrays in that they both have similar operations, and both could be used internally for implementing Stacks and Queues.

Where linked lists win is resource management (they use less) and are better in that they don’t need to rebuild themselves from scratch every time an element in the middle is inserted or removed.

Arrays when when it comes to random access. They are just faster at access elements in the middle of themselves, while linked lists need to iterate through each node until they find the one they are looking for.

So that’s a quick run down on arrays, and how the compare to linked lists.

Happy coding.

Full listing

Source

public class DynamicArray<E> {

    private Object[] data;
    private int size; // number of elements
    private int initialCapacity;

    public DynamicArray(int initialCapacity) {
        this.initialCapacity = initialCapacity;
        data = new Object[initialCapacity];
    }

    public void set(int i, E e) {
        data[i] = e;
        size++;
    }

    public E get(int i) {
        return (E)data[i];
    }

    public void pushBack(E e) {

        if (size == initialCapacity) {
            Object[] newData = new Object[initialCapacity * 2];
            for (int i = 0; i < initialCapacity; i++) {
                newData[i] = data[i];
            }
            data = newData;
            initialCapacity = initialCapacity * 2;
        }

        data[size] = e;
        size++;
    }

    public int size() {
        return size;
    }
    public int capacity() { return initialCapacity; }

    public void remove(int i) {
        for (int j = i; j < size - 1; j++) {
            data[j] = data[j + 1];
        }
        size--;
    }
}

Tests

import junit.framework.Assert;
import org.junit.Before;
import org.junit.Test;

public class DynamicArrayTests {

    private DynamicArray array;

    @Before
    public void setUp() throws Exception {
        array = new DynamicArray<String>(2);
    }

    @Test
    public void InitialState() throws Exception {
        Assert.assertEquals(0, array.size());
    }

    @Test
    public void GetAndSet() throws Exception {
        array.set(0, "a");
        Assert.assertEquals(1, array.size());
        Assert.assertEquals("a", array.get(0));
    }

    @Test
    public void PushBack() throws Exception {
        array.pushBack("a");
        array.pushBack("b");
        Assert.assertEquals(2, array.size());
        Assert.assertEquals("a", array.get(0));
        Assert.assertEquals("b", array.get(1));
    }

    @Test
    public void PushBeyondCurrentSize() throws Exception {
        array.pushBack("a");
        array.pushBack("b");
        array.pushBack("c");
        Assert.assertEquals(3, array.size());
        Assert.assertEquals(4, array.capacity());
        Assert.assertEquals("a", array.get(0));
        Assert.assertEquals("b", array.get(1));
        Assert.assertEquals("c", array.get(2));
    }

    @Test
    public void Remove() throws Exception {
        array.pushBack("a");
        array.pushBack("b");
        array.pushBack("c");

        array.remove(1);

        Assert.assertEquals("a", array.get(0));
        Assert.assertEquals("c", array.get(1));
    }
}

Links that help
http://ridiculousfish.com/blog/posts/array.html

Advertisements