Dynamic Array

It has been a long time since my last article about algorithms and data structures. This time I would like to continue on solving our problem mentioned in my previous Linked List article.

If you still remember, the problem that we were trying to solve was to speed up the search for each permutation in the dictionary. We realized that if the words are sorted we can perform a binary search to make it faster to search but a binary search doesn’t work on a linked list because we don’t have direct access to the middle of the list.

This is where another data structure, usually called a dynamic array is useful. The idea behind it is very simple.

We start with an array with a certain initial size and every time an element is added we check if there is enough space to store it. If not, we create a new array a bit bigger, copy everything from the old array to the new one and we dispose of the old one. Since we’re using Kotlin, this is done automatically by the garbage collector as soon as we stop referencing it.

Since we’re creating a new class DynamicArray we can go ahead and also create a class SinglyLinkedList, just to have all our functions encapsulated into a class.

Having two implementations of a list, would be good if we could abstract the basic operations into a List interface so that it’s easier to change implementations while we’re testing things around.

The magic behind this data structure is basically this:

class DynamicArray<E> : List<E> {
    private var elements: Array<Any?> = emptyArray()
    private var size: Int = 0

    override fun add(e: E) {
        ensureCapacity(size + 1)
        elements[size++] = e as Any
    }

    private fun ensureCapacity(capacity: Int) {
        if (elements.size < capacity) {
            grow(capacity)
        }
    }

    private fun grow(capacity: Int) {
        val newElements: Array<Any?> = if (size == 0) {
            Array(2) { null }
        } else {
            Array((capacity * 1.5).toInt()) { null }
        }

        for (i in 0 until size) {
            newElements[i] = elements[i]
        }

        elements = newElements
    }

    // ...
}

Binary Search

Having direct access to the middle element we can create an extension function that allows us to do a binary search:

fun <T : Comparable<T>> DynamicArray<out T>.binarySearch(e: T): Int {
    var min = 0
    var max = size() - 1
    while (min <= max) {
        var mid = (min + max) / 2
        if (e < this[mid]) max = mid - 1
        else if (e > this[mid]) min = mid + 1
        else return mid
    }
    return -1
}

Finding all anagrams

Having the binary search function we can easily use it to find all anagrams. We’re even reusing our own DynamicArray to have a list of permutations!

        for (i in 0 until listOfPermutations.size()) {
            val word = listOfPermutations[i]
            if (dictionary.binarySearch(word) != -1) {
                println(word)
            }
        }

But what about sorting?

Of course we can only use this function if the list is sorted. So how do we sort our words?

The first algorithm that computer science students usually learn is bubble sort. But that’s the topic for the next article. If you would like to read it now, please click here.